TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

97.4% (37/38)

Submission's AC Ratio

60.8% (79/130)

Tags

Description

十九世紀的時候,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而得。

隨便跟你說我要某列的某個數,你能不能算出來呢?

Input Format

輸入檔中有許多組輸入,每組輸入佔一行,包含了兩個用空白隔開的整數,依序代表要求的那個數所在的列號與它是在該列的第幾個(列號與第幾個都是從 1 開始數的)。你可以假設列號不會超過 30。最後以兩個零“0 0”為檔案結束,不須處理這組輸入。

Output Format

對每一組輸入輸出一行,其中包含所要求的那個數。格式是分子、斜線、分母,中間不要有空白。

Sample Input 1

4 1
4 2
4 3
4 4
0 0

Sample Output 1

1/3
2/3
3/2
3/1

Hints

Problem Source

原TIOJ1101 / NPSC2006決賽(prob D)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1