Connection Status:
Competition Arena > CalkinWilf

CalkinWilf

TCO19 SRM 751 · 2019-01-09 · by misof

TCO19 SRM 751 · 2019-01-09 · by misof · Simple Math, Simple Search, Iteration
Class Name: CalkinWilf
Return Type: int[]
Method Name: findRational
Arg Types: (string)
Problem Statement

Problem Statement

The Calkin-Wilf tree is a rooted tree that contains each positive rational number exactly once. The definition of the tree is really simple:

  • The root of the tree contains the value 1/1.
  • Each node in the tree has one left child and one right child.
  • If a node contains the fraction a/b, its left child contains the fraction a/(a+b) and its right child contains the fraction (a+b)/b.

Here is an ASCII art drawing of the first few levels of the tree: 

                ____________1/1____________
               /                           \
        ____1/2____                     ____2/1____
       /           \                   /           \
    1/3             3/2             2/3             3/1
   /   \           /   \           /   \           /   \
1/4     4/3     3/5     5/2     2/5     5/3     3/4     4/1

You are given the String path that describes a path down the tree. We start in the root and we read the characters of path one at a time. Here, 'L' means "go to the left child" and 'R' means "go to the right child".

Find the fraction a/b that will be written in the last node we visit. Return the int[] {a, b}.

Notes

  • The return value should be a int[] with two elements. Element 0 should be the numerator and element 1 should be the denominator of the fraction.

Constraints

  • path will contain between 0 and 30 characters, inclusive.
  • Each character in path will be either 'L' or 'R'.
Examples
0)
""
Returns: {1, 1 }

If the path is empty, we end where we started: in the root.

1)
"R"
Returns: {2, 1 }

Taking a single step right takes us to the node with the value 2/1.

2)
"LRR"
Returns: {5, 2 }

This time we go 1/1 -> left to 1/2 -> right to 3/2 -> right to 5/2.

3)
"LRLRLRLRLRLRLRLRLRLRLRLRLRLRLR"
Returns: {2178309, 1346269 }

This is one possible longest valid input.

4)
"RLLRRRLLRRLRRR"
Returns: {497, 134 }

Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CalkinWilf with a public method vector<int> findRational(string path) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous