Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Forum Home ProblemSet Status Ranklist Contest LoginRegister Exam
Problem 1052. -- The Stern-Brocot Number System

The Stern-Brocot Number System

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 21  Solved: 13


The Stern-Brocot tree is a beautiful way for constructing the set of all non-negative fractions $ {m \over n}$ where m and n are relatively prime. The idea is to start with two fractions $ \left(\vphantom{ {0 \over 1}, {1 \over 0} }\right.$$ {0 \over 1}$,$ {1 \over 0}$$ \left.\vphantom{ {0 \over 1}, {1 \over 0} }\right)$ and then repeat the following operation as many times as desired:

Insert $ {{m+m'} \over {n+n'}}$ between two adjacent fractions $ {m \over n}$ and $ {m' \over n'}$ .

For example, the first step gives us one new entry between $ {0 \over 1}$ and $ {1 \over 0}$,

$\displaystyle {0 \over 1}$,$\displaystyle {1 \over 1}$,$\displaystyle {1 \over 0}$

and the next gives two more:

$\displaystyle {0 \over 1}$,$\displaystyle {1 \over 2}$,$\displaystyle {1 \over 1}$,$\displaystyle {2 \over 1}$,$\displaystyle {1 \over 0}$

The next gives four more:

$\displaystyle {0 \over 1}$,$\displaystyle {1 \over 3}$,$\displaystyle {1 \over 2}$,$\displaystyle {2 \over 3}$,$\displaystyle {1 \over 1}$,$\displaystyle {3 \over 2}$,$\displaystyle {2 \over 1}$,$\displaystyle {3 \over 1}$,$\displaystyle {1 \over 0}$

The entire array can be regarded as an infinite binary tree structure whose top levels look like this-

This construction preserves order, and thus we cannot possibly get the same fraction in two different places.

We can, in fact, regard the Stern-Brocot tree as a number system for representing rational numbers, because each positive, reduced fraction occurs exactly once. Let us use the letters ``L'' and ``R'' to stand for going down the left or right branch as we proceed from the root of the tree to a particular fraction; then a string of L's and R's uniquely identifies a place in the tree. For example, LRRL means that we go left from $ {1 \over 1}$ down to $ {1 \over 2}$, then right to $ {2 \over 3}$, then right to $ {3 \over 4}$, then left to $ {5 \over 7}$. We can consider LRRL to be a representation of $ {5 \over 7}$. Every positive fraction gets represented in this way as a unique string of L's and R's.

Well, almost every fraction. The fraction $ {1 \over 1}$ corresponds to the empty string. We will denote it by I, since that looks something like 1 and stands for ``identity."

In this problem, given a positive rational fraction, represent it in the Stern-Brocot number system.


The input file contains multiple test cases. Each test case consists of a line containing two positive integers m and n, where m and n are relatively prime. The input terminates with a test case containing two 1's for m and n, and this case must not be processed.


For each test case in the input file, output a line containing the representation of the given fraction in the Stern-Brocot number system.

Sample Input

5 7
878 323
1 1

Sample Output






한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin