Problem 1897. GJam 2014 China Rd A: Rational Number Tree
This Challenge is derived from GJam 2014 China Rational Number Tree.
The Goal is to determine the tree node if given [P,Q] or provide the [P,Q] if given a node. This is the small Challenge with a Max of 16 Tree levels. The large Challenge is 64 Tree levels.
Consider an infinite complete binary tree where the root node is 1/1 and the left and right childs of node P/Q are P/(P+Q) and (P+Q)/Q, respectively.
The Tree looks like:
1/1 ______|______ | | 1/2 2/1 ___|___ ___|___ | | | | 1/3 3/2 2/3 3/1
The nodes are 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1,...
Input: [N] or [P,Q] where N is an integer node or [P,Q] are terms of a Node
Output: [P,Q] or [N] depends on Input type
Examples:
[Input] [Output] [2] [1 2] [1 2] [2] [5] [3 2] [3 2] [5]
Contest Performance: Best Delta Time of 14 minutes with 1193 out of 3058 completing in less than 3 hours.
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers10
Suggested Problems
-
Remove all the words that end with "ain"
2165 Solvers
-
Determine if a Given Number is a Triangle Number
367 Solvers
-
1878 Solvers
-
Back to basics 25 - Valid variable names
321 Solvers
-
Penny flipping - calculate winning probability (easy)
180 Solvers
More from this Author294
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!