A Stern–Brocot-számrendszer

A Stern–Brocot-fa egy nagyon szép módja az összes nemnegatív m/n tört előállításának, ahol m és n relatív prímek. Az ötlet az, hogy kiindulunk két törtből (a 0/1 és az 1/0 törtekből), majd addig ismételgetjük az alábbi műveletet, amíg szükséges:

Szúrjuk be az (m + m')/(n + n') törtet bármely két szomszédos m/n és m'/n' tört közé!

Az első lépés például egy új törtet eredményez a 0/1 és az 1/0 között:

0/1, 1/1, 1/0

A következő lépés két újabb törtet ad:

0/1, 1/2, 1/1, 2/1, 1/0

A következő négy újabbat:

0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0

Ezután 8, 16 stb. törttel bővül a lista. A teljes tömb tekinthető egy végtelen bináris fának, amelynek a felső szintjei a következőképpen néznek ki:

A konstrukció megőrzi a nagyság szerinti sorrendet, és nem kaphatjuk meg ugyanazt a törtet két különböző helyen.

A Stern–Brocot-fa valójában tekinthető egy számrendszernek is, amellyel a racionális számokat lehet reprezentálni, mivel minden pozitív egyszerűsített tört pontosan egyszer fordul benne elő. Használjuk az L és R betűket a bal (left), illetve a jobb (right) ágon való továbblépésre, miközben a gyökértől egy konkrét tört felé haladunk! Ekkor egy L-ekből és R-ekből álló karaktersorozat egyértelműen azonosít egy csomópontot a fában. Az LRRL például azt jelenti, hogy balra lépünk az 1/1-ből az 1/2 felé, onnan jobbra a 2/3 felé, majd jobbra a 3/4 felé, végül balra az 5/7 felé. Az LRRL tehát az 5/7 reprezentációjának tekinthető. Minden pozitív tört ábrázolható ilyen módon egy L-ekből és R-ekből álló karaktersorozatként.

Akad azonban egy kis probléma: Az 1/1 törtnek az üres sztring felel meg, és ezt jelölnünk kell valahogy. Megállapodhatunk az I jelölésben, hiszen az majdnem úgy néz ki, mint az 1, és az angol „azonosság” (identity) szó rövidítése.

Ebben a feladatban egy adott pozitív racionális tört Stern–Brocot-számrendszerbeli reprezentációját kell meghatároznod.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egy sorból áll, amelyben két 32 bites pozitív egész szám, m és n szerepel, ahol m és n relatív prímek. A bemenet egy olyan tesztesettel zárul, amelyben m és n is 1; ezt az esetet nem kell feldolgozni.

A kimenet specifikációja

A bemeneten előforduló minden tesztesetre egy sort kell a kimenetre írni, amely az adott tört Stern–Brocot-számrendszerbeli reprezentációját tartalmazza.

Példa bemenet

1. 5 7
2. 878 323
3. 1 1

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. LRRL
2. RRLRRLRLLLLRLRRR

letöltés szöveges állományként