NWERC11B  Bird tree
Bird tree
The Bird tree^{1} is an infinite binary tree, whose first 5 levels look as follows:
It can be defined as follows:
This is a corecursive definition in which both occurrences of bird refer to the full (infinite) tree. The expression bird + 1 means that 1 is added to every fraction in the tree, and 1∕bird means that every fraction in the tree is inverted (so ^{a}∕_{b} becomes ^{b}∕_{a}).
Surprisingly, the tree contains every positive rational number exactly once, so every reduced fraction is at a unique place in the tree. Hence, we can also describe a rational number by giving directions (L for left subtree, R for right subtree) in the Bird tree. For example, ^{2}∕_{5} is represented by LRR. Given a reduced fraction, return a string consisting of L’s and R’s: the directions to locate this fraction from the top of the tree.
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
 one line with two integers a and b (1 ≤ a,b ≤ 10^{9}), separated by a ’/’. These represent the numerator and denominator of a reduced fraction. The integers a and b are not both equal to 1, and they satisfy gcd(a,b) = 1.
For every test case the length of the string with directions will be at most 10 000.
Output
Per test case:
 one line with the string representation of the location of this fraction in the Bird tree.
Sample in and output
Input 
Output 
3 1/2 2/5 7/3 
L LRR RLLR 
^{1}Hinze, R. (2009). The Bird tree. J. Funct. Program., 19:491–508.
Copyright notice
This problem text is copyright by the NWERC 2011 jury. It is licensed under the Creative Commons AttributionShare Alike license version 3.0; The complete license text can be found at: http://creativecommons.org/licenses/bysa/3.0/legalcode
hide comments
kelvin_chui:
20151205 16:19:27
Is there any special case needed to check? I got correct results for all numbers in the given diagram, but wrong answer when I submitted it. 

miodziu:
20150724 10:05:05
hint: https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree 

soursugar:
20150525 09:45:48
the figure doesn't seem to follow the recursive defn. e.g.: 1/((1/3)+1) is 3/4.


Bhavik:
20140111 18:58:30
very good problem 

Agnisnato Datta:
20130607 05:43:23
nice prob...try to concentrate on fig


Paul Draper:
20121120 02:11:43
Nice one, Jeroen! Thanks for the visual. 

rohitjv:
20120723 03:46:55
yeah...took a lot of time to understand


Ajey Golsangi:
20120225 09:56:17
This one took a lot of time. 

Santiago Palacio:
20120112 18:56:45
Agree with bond, understanding it was the most difficult thing. 

Devil D:
20111231 11:44:57
At Last got it 
Added by:  Jeroen Bransen 
Date:  20111102 
Time limit:  0.448s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  NWERC 2011 Jury 