Soccer

Interview

Time limit1sMemory limit128 MB

Summary

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

Level: Medium6 of 10
Topics: Dynamic programming, Probability, Implementation, Math
Solved: No attempts yet

Problem

Imagine a Soccer World Cup. After the group stage, 16 countries remain, and the champion is decided by the following single-elimination tournament. (The country names in the bracket below are only an example; the actual input may use different names.)

 1 Germany ----+
               +-- ? --+
 2 Sweden -----+       |
                       +-- ? --+
 3 Argentina --+       |       |
               +-- ? --+       |
 4 Mexico -----+               |
                               +-- ? --+
 5 Italy ------+               |       |
               +-- ? --+       |       |
 6 Australia --+       |       |       |
                       +-- ? --+       |
 7 Switzerl ---+       |               |
               +-- ? --+               |
 8 Ukraine ----+                       |
                                       +-- World Champion
 9 England ----+                       |
               +-- ? --+               |
10 Ecuador ----+       |               |
                       +-- ? --+       |
11 Portugal ---+       |       |       |
               +-- ? --+       |       |
12 Holland ----+               |       |
                               +-- ? --+
13 Brazil -----+               |
               +-- ? --+       |
14 Ghana ------+       |       |
                       +-- ? --+
15 Spain ------+       |
               +-- ? --+
16 France -----+

For every possible match A vs. B among these 16 nations you are given the probability that team A beats team B. Your task is to determine, for each nation, its probability of becoming world champion.

Input

The first line contains the number of scenarios. For each scenario, the first 16 lines give the names of the 16 countries, from top to bottom according to the structure above; each name is a single string of at most 10 letters. Next comes a $16 \times 16$ integer matrix $p$ , where element $p_{i,j}$ is the probability, in percent, that the $i$ -th country defeats the $j$ -th country in a direct match. For example, $p_{1,13} = 57$ means that in a match between Germany and Brazil, Germany wins with probability 57%. Matches never end in a draw, so $p_{i,j} + p_{j,i} = 100$ for all $i, j$ .

Output

For each scenario, the output begins with a line Scenario #i:, where $i$ is the scenario number starting from 1. Then print 16 lines, each of width 17: the country's name on the left and, on the right, its probability of becoming world champion in percent, rounded to two decimal places, with the gap between them filled by space characters. Keep the countries in the same order as the input. Separate consecutive scenarios with a single blank line.

Examples1

Example 1

Input

1
Germany
Sweden
Argentina
Mexico
Italy
Australia
Switzerl
Ukraine
England
Ecuador
Portugal
Holland
Brazil
Ghana
Spain
France
 50  67  55  70  65  77  75  72  62  75  65  63  57  80  56  68
 33  50  38  53  48  60  58  55  45  58  48  46  40  63  39  51
 45  62  50  65  60  72  70  67  57  70  60  58  52  75  51  63
 30  47  35  50  45  57  55  52  42  55  45  43  37  60  36  48
 35  52  40  55  50  62  60  57  47  60  50  48  42  65  41  53
 23  40  28  43  38  50  48  45  35  48  38  36  30  53  29  41
 25  42  30  45  40  52  50  47  37  50  40  38  32  55  31  43
 28  45  33  48  43  55  53  50  40  53  43  41  35  58  34  46
 38  55  43  58  53  65  63  60  50  63  53  51  45  68  44  56
 25  42  30  45  40  52  50  47  37  50  40  38  32  55  31  43
 35  52  40  55  50  62  60  57  47  60  50  48  42  65  41  53
 37  54  42  57  52  64  62  59  49  62  52  50  44  67  43  55
 43  60  48  63  58  70  68  65  55  68  58  56  50  73  49  61
 20  37  25  40  35  47  45  42  32  45  35  33  27  50  26  38
 44  61  49  64  59  71  69  66  56  69  59  57  51  74  50  62
 32  49  37  52  47  59  57  54  44  57  47  45  39  62  38  50

Expected output

Scenario #1:
Germany     17.69
Sweden       3.45
Argentina   12.32
Mexico       2.65
Italy        7.04
Australia    1.81
Switzerl     2.43
Ukraine      3.46
England      7.75
Ecuador      1.83
Portugal     5.19
Holland      6.36
Brazil      12.20
Ghana        0.89
Spain       11.47
France       3.46