a056. 彈珠台

Content

編寫一個程式來模擬彈珠台。對於這個問題，我們將使用非常簡單的彈珠台。
此彈珠台中有 N 行彈球針，第 k 行有 k 個彈球針。一行的第 i 個彈球針位於上一行的第 i 個彈球針與第 (i-1) 個彈球針之間，如下圖所示。
當球掉在彈球針上時，它將向左或向右移動。這種機率因彈球針而異。擊中 N 針後，球將落入 (N+1) 個桶子之一。
現在給出所有彈球針的機率分佈，請計算球落入 (N+1) 個桶中的每個桶的機率。

Input

輸入的第一行有 N 行。N ≤ 15

接下來 N×(N+1)/2 行具有兩個整數 a, b，以空格隔開，
表示球向左或向右移動的機率之比。機率比從上到下，從左到右給出。 0 ≤ a,b ≤ 2³¹-1，且保證a,b不全為0。

Output

請輸出 (N+1) 行
第 i 行以最簡分數 p/q 來顯示落入第 i 個桶子的機率。

Sample Input #1

Sample Output #1

2/15
7/10
1/6

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1M
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

Hint ：

為了避免溢位(overflow)，C/C++解題時請用 long long int 儲存，並將過程中每一個分數都化成最簡分數。

Tags:

出處:

judgegirl [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」