c025. 簡單暖身題 - 花中程式設計挑戰系統

Content

現在有 $N$ 個座位圍成一圈，座位從 $0$ 號開始順時鐘編號到 $N-1$ 。

最初喵咪坐在 $0$ 號座位，之後喵咪每次會以各 $\frac{1}{2}$ 的機率往左邊或右邊的座位移動，當喵咪全部座位都坐過以後他便不會再移動了。

求喵咪最後停在 $M$ 號座位的機率。

Input

輸入包含多筆測資 $(\le 1000)$ ，以 EOF (End-of-File) 結束。

每筆測資中輸入只有一行，包含兩個整數 $N$ , $M$ 。

Output

對每筆測資，請將答案化至最簡分數後，輸出答案的分子跟分母於一行並以空白隔開。若答案為 $0$ 則 $(分子, 分母) = (0, 1)$ 。

保證答案長度不會超過 4MB。

Sample Input

Sample Input 1:
3 1
5 0

Sample Output

Sample Output 1:
1 2
0 1

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (50%): 1.0s , <1M
公開測資點#1 (50%): 1.0s , <1M

Hint ：

第一筆測資中，如果第一步走到 $1$ ，那最後一定會停在 $2$ ，反之亦然。答案為 $\frac{1}{2}$ 。

第二筆測資中，無論如何走最後都不可能停在 $0$ 號座位，故機率為 $\frac{0}{1}$ 。

Tags:

math

出處:

[管理者：

SorahISA (SorahISA)

]

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