France '98

Interview

Time limit1sMemory limit128 MB

Summary

Given win probabilities for every pair of 16 teams and a fixed bracket, compute each team's probability of winning the single-elimination tournament.

Level: Medium5 of 10
Topics: Dynamic programming, Probability, Implementation, Simulation
Solved: No attempts yet

Problem

The first round of the Soccer World Cup in France has just finished, and 16 nations remain. The champion is now decided by the following single-elimination tournament:

 1 Brazil --------+
                  +---+
 2 Chile ---------+   |
                      +---+
 3 Nigeria -------+   |   |
                  +---+   |
 4 Denmark -------+       |
                          +---+
 5 Holland -------+       |   |
                  +---+   |   |
 6 Yugoslavia ----+   |   |   |
                      +---+   |
 7 Argentina -----+   |       |
                  +---+       |
 8 England -------+           |
                              +-- World Champion
 9 Italy ---------+           |
                  +---+       |
10 Norway --------+   |       |
                      +---+   |
11 France --------+   |   |   |
                  +---+   |   |
12 Paraguay ------+       |   |
                          +---+
13 Germany -------+       |
                  +---+   |
14 Mexico --------+   |   |
                      +---+
15 Romania -------+   |
                  +---+
16 Croatia -------+

For every possible match A vs. B among these 16 nations you are given the probability that team A beats team B. Together with the bracket above, this is enough to compute the probability that any given nation wins the World Cup. For example, if Germany beats Mexico with probability 80%, Romania beats Croatia with 60%, Germany beats Romania with 70%, and Germany beats Croatia with 90%, then the probability that Germany reaches the semi-finals is $80\% \times (70\% \times 60\% + 90\% \times 40\%) = 62.4\%$ .

Write a program that computes each of the 16 nations' chances of becoming World Champion.

Input

The input consists of a single test case.

The first 16 lines list the names of the 16 nations, from top to bottom in the order shown in the bracket above (one name per line).

Then follows a $16 \times 16$ integer matrix $P$ . Element $p_{ij}$ is the probability, in percent, that nation # $i$ beats nation # $j$ in a direct match. Nation # $i$ is the $i$ -th nation from top to bottom in the list. In the bracket above Brazil is #1 and Germany is #13, so $p_{1,13} = 55$ would mean that in a match between Brazil and Germany, Brazil wins with probability 55%.

Matches never end in a draw, so $p_{ij} + p_{ji} = 100$ for all $i, j$ .

Output

Print 16 lines, one per nation, in the same order as the input. Each line has the form <name> p=Y.YY%: the nation's name left-justified in a field of width 10, then a single space, then p=, then the nation's chance of winning the cup as a percentage rounded to exactly two decimal places, then %.

Examples1

Example 1

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

Expected 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%