TopCoder

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

User's AC Ratio

95.0% (38/40)

Submission's AC Ratio

41.8% (118/282)

Tags

Description

一隻螞蟻在滾燙的鍋子上會做什麼事呢?廢話,那當然是逃生!小A在家裡沒事,而且閒得發荒,只好把家裡大大小小的鍋子搬出來,並且拿到瓦斯爐上加熱,再把這些鍋子放在地上,並用幾根筷子搭起來。小A回到他的秘密基地,弄出一隻螞蟻,把他丟到一個鍋子上,因為鍋子太燙了,所以螞蟻會沿著一根筷子爬到另一個鍋子,不過他當然不會留在這個鍋子上,他同樣會找一根筷子爬到另一個鍋子。如果一個鍋子沒有搭上任何筷子,基本上這隻螞蟻就死定了。螞蟻是很珍貴的,再加上小A先生是很有慈悲心的,他會把螞蟻抓起來,做下個實驗。螞蟻在熱鍋上行走是很辛苦的,我們決定在每個鍋子上灑鹽。

這一題要問的是,螞蟻停留在某一個鍋子上的機率是多少。
請假設,小A先生把螞蟻丟到任何一個鍋子的機率是相同的。
一隻螞蟻要沿著哪支筷子往下個鍋子前進的機率也是一樣的。
任兩個鍋子不會撘兩支以上的筷子。
還有,最重要的,螞蟻是很賣命演出的,請不要假設螞蟻會在筷子上避難。

Input Format

測資包含了很多組實驗。
每次實驗的第一行有兩個數字N,T,分別代表有幾個鍋子和這隻螞蟻要走幾步。一步的意思是從一個鍋子沿著一支筷子走到下一個鍋子。
再來一行有個數字C,代表小A先生搭了幾支筷子。
接下來會有C行,每行會有兩個數字s,t,代表這支筷子是搭哪兩個鍋子。
最後有個數字X,為我們要詢問你的問題:螞蟻走了T步後停在第X個鍋子上的機率是多少。
測資以 “0 0” 做結束。
注意,N<=100,所有鍋子編號由1~N。0<=T<=1,000,000,000。

Output Format

對於每組實驗輸出一個數字,也就是我們要求你解的機率,請輸出到小數第四位。

Sample Input 1

5 2
4
1 2
2 3
3 4
4 5
3
3 10
3
1 2
1 3
2 3
1
4 10
3
1 2
1 3
2 3
4
0 0

Sample Output 1

0.3000
0.3333
0.0000

Hints

如果你用long double獲得了WA,你可以試試把它改成double。

Problem Source

原TIOJ1136 / 96 TWN Practice Contest 1。Problem Setter: TimeString。

Subtasks

No. Testdata Range Score
1 0 25
2 1 25
3 2 25
4 3 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4