CalkinWilfReversed
TCO19 SRM 751 · 2019-01-09 · by misof
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
The depth of the root is 0. If a node has depth n, its children have depth n+1.
You are given the
Constraints
- a will be between 1 and 10^18, inclusive.
- b will be between 1 and 10^18, inclusive.
- a and b will be relatively prime. (I.e., their greatest common divisor will be 1.)
1 1 Returns: 0
The fraction 1/1 appears in the root of the tree, and by definition the depth of the root is 0.
4 3 Returns: 3
The fraction 4/3 can be found in the bottom level of the figure shown in the problem statement. The depth of its node is 3.
1 1234567890123 Returns: 1234567890122
The fraction 1/1234567890123 is in the leftmost branch of the tree, and its node is quite deep.
1234567 7654321 Returns: 8837
1234567890123 1 Returns: 1234567890122
Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CalkinWilfReversed with a public method long long getDepth(long long a, long long b) · 94 test cases · 2 s / 256 MB per case