一隻螞蟻在滾燙的鍋子上會做什麼事呢?廢話,那當然是逃生!小A在家裡沒事,而且閒得發荒,只好把家裡大大小小的鍋子搬出來,並且拿到瓦斯爐上加熱,再把這些鍋子放在地上,並用幾根筷子搭起來。小A回到他的秘密基地,弄出一隻螞蟻,把他丟到一個鍋子上,因為鍋子太燙了,所以螞蟻會沿著一根筷子爬到另一個鍋子,不過他當然不會留在這個鍋子上,他同樣會找一根筷子爬到另一個鍋子。如果一個鍋子沒有搭上任何筷子,基本上這隻螞蟻就死定了。螞蟻是很珍貴的,再加上小A先生是很有慈悲心的,他會把螞蟻抓起來,做下個實驗。螞蟻在熱鍋上行走是很辛苦的,我們決定在每個鍋子上灑鹽。
這一題要問的是,螞蟻停留在某一個鍋子上的機率是多少。
請假設,小A先生把螞蟻丟到任何一個鍋子的機率是相同的。
一隻螞蟻要沿著哪支筷子往下個鍋子前進的機率也是一樣的。
任兩個鍋子不會撘兩支以上的筷子。
還有,最重要的,螞蟻是很賣命演出的,請不要假設螞蟻會在筷子上避難。
測資包含了很多組實驗。
每次實驗的第一行有兩個數字N,T,分別代表有幾個鍋子和這隻螞蟻要走幾步。一步的意思是從一個鍋子沿著一支筷子走到下一個鍋子。
再來一行有個數字C,代表小A先生搭了幾支筷子。
接下來會有C行,每行會有兩個數字s,t,代表這支筷子是搭哪兩個鍋子。
最後有個數字X,為我們要詢問你的問題:螞蟻走了T步後停在第X個鍋子上的機率是多少。
測資以 “0 0” 做結束。
注意,N<=100,所有鍋子編號由1~N。0<=T<=1,000,000,000。
對於每組實驗輸出一個數字,也就是我們要求你解的機率,請輸出到小數第四位。
如果你用long double獲得了WA,你可以試試把它改成double。
原TIOJ1136 / 96 TWN Practice Contest 1。Problem Setter: TimeString。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 25 |
2 | 1 | 25 |
3 | 2 | 25 |
4 | 3 | 25 |