十九世紀的時候,Moriz Stern (1858) 與 Achille Brocot (1860) 發明了「一棵樹」。據說,經由一些簡單的規則而產生的這一棵樹上,可以包含零以上所有的有理數。這棵樹看起來大致像這樣:
首先,他們在第一列放兩個「分數」(也許有些人會認為有的不能算是分數,但我們在這裡先把它們當作是分數來看待),第一個是 0/1,代表 0;第二個是 1/0,代表無窮大。接著他們一列一列地產生這棵樹,當他們要產生第 k+1 列的時候,就先把前 k 列所有的分數按照大小排成一列(假設有 n 個),在這些數之間會有 n-1 個間隔,那麼第 k+1 列就準備產生 n-1 個數,其值的分子恰好是左右兩個數的分子的和、分母是左右兩個數的分母的和。
例如,第四列的第二個分數是2/3,而它的2就是左邊1/2的1和右邊1/1的分子1相加的結果;而2/3的3,則是1/2的2加上1/1的分母1而得。
隨便跟你說我要某列的某個數,你能不能算出來呢?
輸入檔中有許多組輸入,每組輸入佔一行,包含了兩個用空白隔開的整數,依序代表要求的那個數所在的列號與它是在該列的第幾個(列號與第幾個都是從 1 開始數的)。你可以假設列號不會超過 30。最後以兩個零“0 0”為檔案結束,不須處理這組輸入。
對每一組輸入輸出一行,其中包含所要求的那個數。格式是分子、斜線、分母,中間不要有空白。
原TIOJ1101 / NPSC2006決賽(prob D)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |