2011年8月26日 星期五

542 - France '98



世界盃足球賽已經進行到最後16強,其賽程表如下:

 1 Brazil -----+
               +-- ? --+
 2 Chile ------+       |
                       +-- ? --+
 3 Nigeria ----+       |       |
               +-- ? --+       |
 4 Denmark ----+               |
                               +-- ? --+
 5 Holland ----+               |       |
               +-- ? --+       |       |
 6 Yugoslavia -+       |       |       |
                       +-- ? --+       |
 7 Argentina --+       |               |
               +-- ? --+               |
 8 England ----+                       |
                                       +-- 世界杯冠軍
 9 Italy ------+                       |
               +-- ? --+               |
10 Norway -----+       |               |
                       +-- ? --+       |
11 France -----+       |       |       |
               +-- ? --+       |       |
12 Paraguay ---+               |       |
                               +-- ? --+
13 Germany ----+               |
               +-- ? --+       |
14 Mexico -----+       |       |
                       +-- ? --+
15 Romania ----+       |
               +-- ? --+
16 Croatia ----+
對於所有A vs. B 的對戰組合中,給定A贏B的機率,可以算出每一隊贏得世界盃冠軍的機率,例如德國贏墨西哥的機率為80%,羅馬尼亞贏克羅埃西亞的機率為60%,德國贏羅馬尼亞的機率為70%,德國贏克羅埃西亞的機率為90%,則德國贏得半準決賽的機率為 80% * (70% * 60% + 90% * 40%) = 62.4%。

請你寫一個程式計算這16隊贏得世界盃冠軍的機率為何。

Input

輸入僅包含一組測試資料。
前16列為參賽國家的名稱,同上面的賽程表。接下來有一個16 x 16 矩陣P,每個矩陣元素pij分別表示國家#i 贏國家#j的百分比勝率,例如上表中Brazil表示#1,Germany表示#13,則 p1, 13 = 55表示Brazil贏Germany的機率為55%。對於所有i, j,pij + pji = 100成立。

Output

請輸出16列,其格式為"XXXXXXXXXX p=Y.YY%"表示每一隊的勝率,其中XXXXXXXXXX表示隊名,以十個字元寬向左對齊,Y.YY表示勝率,請輸出到小數點後兩位。每一列的輸出順序比照輸入資料國家的順序。

Sample Input 

Brazil
Chile
Nigeria
Denmark
Holland
Yugoslavia
Argentina
England
Italy
Norway
France
Paraguay
Germany
Mexico
Romania
Croatia
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

Sample Output 

Brazil     p=8.54%
Chile      p=1.60%
Nigeria    p=8.06%
Denmark    p=2.79%
Holland    p=4.51%
Yugoslavia p=7.50%
Argentina  p=8.38%
England    p=1.56%
Italy      p=9.05%
Norway     p=3.23%
France     p=13.72%
Paraguay   p=3.09%
Germany    p=13.79%
Mexico     p=3.11%
Romania    p=5.53%
Croatia    p=5.53%


原文出處

沒有留言:

張貼留言