NWERC11B - Bird tree

Bird tree

The Bird tree1 is an infinite binary tree, whose first 5 levels look as follows:

                                   1                                    ∕1                     1∕2                                  2∕1          2∕3                1∕3                3∕1                3∕2    3        3         1        2        5         4        4        5    ∕5       ∕4       ∕4       ∕5        ∕2       ∕1       ∕3        ∕3 5   4    4    5   2    1    3   3    8    7   5    7   7    5    7   8 ∕8   ∕7   ∕5  ∕7   ∕7   ∕5  ∕7   ∕8  ∕3   ∕3   ∕1  ∕2   ∕5   ∕4  ∕4   ∕5

It can be defined as follows:

bird =             1∕1          1∕ (bird + 1)  (1∕bird) + 1

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.

Copyright notice

This problem text is copyright by the NWERC 2011 jury. It is licensed under the Creative Commons Attribution-Share Alike license version 3.0; The complete license text can be found at: http://creativecommons.org/licenses/by-sa/3.0/legalcode


Added by:Jeroen Bransen
Date:2011-11-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NWERC 2011 Jury

hide comments
2011-11-28 11:45:25 Jeroen Bransen
The first step is L so we use:
1/(bird' + 1)

Then in the subtree bird' we use R, so for that we use the (1/bird) + 1 rule which gives us:

1/(((1/bird'')+1)+1)

Finally we are done so here for bird'' we fill in 1/1 and we end with:
1/(((1/(1/1))+1)+1)
which is 1/3.
2011-11-27 14:42:27 ulasuevoli
i have same doubt as Aseem Kumar ..
Clarify it
2011-11-27 12:29:19 Aseem Kumar
Can anyone explain how we obtained 1/3 in the LR. Should it not be (1/(1/2) + 1) =3/1 because its parent is 1/2 and using the R rule?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.