TopCoder

Thumb 273182be425dbb6f
AWfulsome
It's so $\huge{AW^{fulsome}}$

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

59.3% (35/59)

Description

  志明與春嬌一行人在南美亞馬遜叢林冒險旅途中得知有關於寶藏的消息,四處打聽下取得一些片斷的資訊(如下表):

  其中包括可以直接連接兩個村落間的路線(具有方向性)以及其對應的存活率。雖說尋寶之旅危機重重,佈滿了各式各樣的陷阱或猛獸,只有極小的存活率;但是,大家仍是一致決定勇敢地邁向尋寶之旅。身為其中一員的你,現在必須整合這些片斷資訊,為大家計算出可能的尋寶路徑中,會經過某一條路線的路徑佔所有可能路徑的存活率的比例。

  舉到來說,若輸入"A I 7",則表示想要計算“由A 村落出發且要經過編號為7 之D→F 路線到達目的地I 村落”的路徑佔所有可由A 村落到達I 村落路徑的存活率之比例。我們得到下列四種不同的走法:

走法1:A 村落→C 村落→D 村落→F 村落→I 村落
其存活率為:0.67 * 0.42 * 0.54 * 0.2 = 0.0303912

走法2:A 村落→D 村落→F 村落→I 村落
其存活率為: 0.5 * 0.54 * 0.2 = 0.054

走法3:A 村落→B 村落→F 村落→I 村落
其存活率為: 0.3 * 0.33 * 0.2 = 0.0198

走法4:A 村落→C 村落→G 村落→I 村落
其存活率為: 0.67 * 0.1 * 0.23 = 0.01541


因此,“A 村落出發且要經過編號7 之D→F 路線到達I 村落”的存活率佔所有可能路線的存活率的比例
=(走法1 的存活率+走法2 的存活率)/(走法1 的存活率+走法2 的存活率+走法3 的存活率+走法4 的存活率)
=(0.0303912 + 0.054)/(0.0303912 + 0.054 + 0.0198 + 0.01541)    
=0.70560496

Input Format

輸入檔可能包含多筆測試資料,每一筆佔一列。
每一筆測試資料包含二個字母與一個數字(以空格分開),第一個字母表示起點之村落,第二個字母表示目的地之村落,字母所表示的村落必須存在於路線表格中;第三個數字k 表示必經路線的編號(1<=k<=18)。
例如: A I 7
  表示以A 村落為起點,I 村落為終點,中間必須經過編號為7 之路線(D 村落→F 村落)。

Output Format

輸出存活率比例,小數點取至八位(四捨五入)。若起點到終點無路可通,或可通但路徑中不包含必經路線k,即答案為無解,則輸出“No solution”。

Sample Input

A I 7
B L 9
D L 6
G N 15

Sample Output

0.70560496
0.40579710
No solution
0.16663722

Hints

Problem Source

原TIOJ1124 / 93北市賽(prob 5)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144