## NWERC11B - Bird tree

no tags

### Bird tree

The Bird tree1 is an infinite binary tree, whose first 5 levels look as follows: It can be defined as follows: This is a co-recursive 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 ab becomes ba).

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, 25 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 ≤ 109), 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```

1Hinze, R. (2009). The Bird tree. J. Funct. Program., 19:491–508.

 < Previous 1 2 Next > kelvin_chui: 2015-12-05 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: 2015-07-24 10:05:05 hint: https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree soursugar: 2015-05-25 09:45:48 the figure doesn't seem to follow the recursive defn. e.g.: 1/((1/3)+1) is 3/4. follow the figure or the recursive defn? Bhavik: 2014-01-11 18:58:30 very good problem Agnisnato Datta: 2013-06-07 05:43:23 nice prob...try to concentrate on fig Paul Draper: 2012-11-20 02:11:43 Nice one, Jeroen! Thanks for the visual. rohitjv: 2012-07-23 03:46:55 yeah...took a lot of time to understand Ajey Golsangi: 2012-02-25 09:56:17 This one took a lot of time. Santiago Palacio: 2012-01-12 18:56:45 Agree with bond, understanding it was the most difficult thing. Devil D: 2011-12-31 11:44:57 At Last got it