NG0FRCTN - Fractions on Tree
A fraction tree is an infinite binary tree defined as follows:
- Every node of tree contains a fraction.
- Root of tree contains the fraction 1/1.
- Any node with fraction i/j has two children : left child with fraction i/(i+j) and right child with fraction (i+j)/j.
For example, fraction tree up to 3 levels is as shown:
We number the nodes according to increasing levels (root is at level 1) and at any same level, nodes are numbered from left to right. So first node holds the fraction 1/1, second one holds 1/2, third one holds 2/1 fourth one holds 1/3 and so on.
Your task is simple. Given a number n, you are to find the fraction at the nth node.
Input
Every line of the input contains a single number n. You are to find the fraction at nth node of fraction tree. Input file terminates with a 0 which is not to be processed.
Output
For each input, print numerator and denominator of the lowest form of the fraction separated by a /. Output of each case to be done in separate lines.
Example
Input: 1 2 3 7 0 Output: 1/1 1/2 2/1 3/1
Constraints
1 <= number of test cases <= 30000, 1 <= N <= 10^10
hide comments
kumar_anubhav:
2020-08-05 13:21:31
cakewalk :) |
|
spoj2121:
2015-12-01 13:53:22
try for a O(T*logn) solution its is easy to implement
|
|
krish:
2015-04-22 12:57:01
10000000000
|
|
Francky:
2014-12-29 16:00:53
(29/12/2014) Image uploaded, and now visible. |
|
Martijn Muijsers:
2013-10-18 13:25:03
Tested all possible cases with Wolfram API, all correct. Getting wrong answer :S Could you possibly check 10287391? :) |
|
Sidharth Guglani:
2012-08-29 22:41:31
getting WA don't know why passing all the test cases on the forum.
|
|
Shubham:
2012-08-22 17:19:28
too tough in python :\
|
|
well i am lagging:
2012-02-06 18:01:18
image is not visible please fix the problem |
|
Santiago Palacio:
2012-01-09 22:02:33
Image is not really necessary, i believe. |
|
Ajey Golsangi:
2012-01-05 10:12:55
Image not visible. Please correct the problem. |
Added by: | Nikhil Garg |
Date: | 2009-12-19 |
Time limit: | 1.440s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | own |