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
-
2445 Solvers
-
152 Solvers
-
Find best placement for ordered dominoes (harder)
309 Solvers
-
541 Solvers
-
62 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!