回分類題庫
g006: F.奇幻之樹
關鍵字: NPSC 2005 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 78 Times / 66 Users | Submit : 125 Times / 66 Users | Accepted rate : 100%
題目加入時間 : 2011-12-06 10:01

Content: 简体中文

很久很久以前有個地方叫做奇幻村,奇幻村裡面的東西都很神祕,裡面有奇怪的房間、奇怪的石像、奇怪的各種顏色的光、奇怪的會講話的動物、奇怪的會施法術的人、和各種奇怪的自然現象。例如在奇幻村裡東西水會往高處流,太陽和月亮會隨機出現,東西會從一個地方消失又從另一個地方冒出來,魚在陸地上游泳狗在天空中飛等等。最有趣的是有一棵從上往下長的樹,它的根部是吊在空中的,但是枝幹卻往下長,從一開始的主幹開始分為兩個支幹,這兩個支幹又各分為兩個支幹,然後再各自分叉,這樣一直一直這樣長下去,伸到看不見的地洞裡去。更奇怪的是這棵樹在每個分叉的地方都會有一個凹洞,每個洞裡都很神奇的刻著一個分數,而且這些分數的排列方式竟然還是有規律可循的!我們來看看下面這個示意圖:

 

我們可以這樣想像:一開始有兩個不在樹上的假想分數 0/1 和 1/0 ,把這兩個數的分母和分子相加可以得到 1/1 = (0+1)/(1+0) ,也就是這棵樹的樹根。接下來在 0/1 1/1 1/0 這三個分數之中,每兩個相鄰的分數就插入一個新的分數,讓分母和分子分別等於相鄰的兩個分數的分母和與分子和,就可以得到次高的兩個分叉點的分數,也就是 1/2 = (0+1)/(1+1) ,2/1 = (1+1)/(1+0) ,接下來又可以把 0/1 1/2 1/1 2/1 1/0 這串分數中每兩個相鄰的數字再插入一個分數,分母和分子分別等於左右兩個相鄰分數的分母和與分子和,就可以得到第三高的四個分叉點 1/3 、2/3 、3/2 、3/1 。對於每一個新插入的分數,都可以視為它是從它左右相鄰的兩個分數之中,在樹上位置較低的那個分數所分叉下來的。這顆奇妙的樹就循著這樣的規則一直無窮盡的伸展下去,誰也不知道它的盡頭。

奇幻村的居民發現這棵奇幻的樹有一些相當奇妙的性質,例如我們如果從任意一個樹洞沿著支幹往上走,最後一定可以回到它的根部,如果一路上遇到的第一個小於它的數字是 m/n ,第一個大於它的數字是 m'/n' ,那麼這個數的值就剛好會是 (m'+m)/(n'+n) !還有一個更神奇的性質是,這棵樹如果無窮無盡的長下去,我們可以知道世界上所有的最簡分數都會出現在這棵樹的某個樹洞裡,而且恰好只會出現一次。於是奇幻村的居民突然開始好奇應該要怎麼走才能到達刻著某個特定數字的樹洞呢?例如說我想走到記著 5/7 的那個樹洞,那麼我應該從根部 1/1 開始,往左走一步到第一個分叉點,再往右走一步到第一個分叉點,再往右走一步到下一個分叉點,然後再往左走到再下一個分叉點(如圖所示)。我們可以把這樣的走法記成「LRRL」這樣一個字串,也就是「左右右左」的意思。現在假設這棵樹真的是沒有盡頭的,你能告訴奇幻村的居民要怎麼走才能到達刻著某個特定最簡分數的的樹洞嗎?

Input:

輸入的測試檔案包含了很多筆測試資料,每一筆測試資料都占了單獨的一行,行中有以空白分隔的兩個數字m n (1 ≤ m, n ≤ 30000, m/n 是最簡分數),代表奇幻村的居民想要知道記載 m/n 的樹洞該如何到達。如果讀到一行m = n = 0,就代表整個測試檔案已經結束了,不需要對這筆資料作出任何輸出。

Output:

對於每一筆輸入檔中的測試資料,都應該有一行對應的輸出,這行輸出包含了一個只由大寫英文字母L和R組成的字串,而且中間不應該有任何除了這兩個字母之外的字元。這行字串代表從根部 1/1 開始應該要怎樣走才能夠走到欲求樹洞的路徑,L代表往左下走到下一個最近的分叉點,R則代表往右下走到下一個最近的分叉點。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5 7
4 9
1321 25555
0 0

Sample Output :

LRRL
LLRRR
LLLLLLLLLLLLLLLLLLLRRLRRRRRRRRLRRLLRLLL

Hint :

如果我們把這棵樹”壓扁”來看的話,你能看出任意三個相鄰的數字之間大小的順序關係嗎?

Author :

NPSC 2005 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum