축구

면접 대비

시간 제한1초메모리 제한128 MB

요약

16개 팀과 고정된 대진표, 두 팀의 승리 확률이 주어질 때 각 팀이 단일 토너먼트에서 우승할 확률을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 확률, 구현, 수학
정답자: 아직 제출이 없습니다

문제

어떤 축구 월드컵을 생각해 봅시다. 조별 예선을 마치고 16개국이 남았으며, 이제 다음과 같은 단판 승부 토너먼트로 우승국을 가립니다. (아래 대진표의 국가 이름은 예시일 뿐이며, 실제 입력에서는 다를 수 있습니다.)

 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 -----+

이 16개국 사이에서 벌어질 수 있는 모든 A 대 B 경기에 대해, A가 B를 이길 확률이 주어집니다. 각 국가가 월드컵에서 우승할 확률을 구하는 것이 목표입니다.

입력

첫째 줄에 시나리오의 수가 주어집니다. 각 시나리오에서는 먼저 위 구조의 위에서부터 아래 순서대로 16개국의 이름이 16줄에 걸쳐 주어집니다. 각 이름은 알파벳으로 이루어진 최대 10글자의 문자열입니다. 이어서 $16 \times 16$ 정수 행렬 $p$ 가 주어지며, 원소 $p_{i,j}$ 는 $i$ 번째 국가가 $j$ 번째 국가와의 직접 대결에서 이길 확률(퍼센트)입니다. 예를 들어 $p_{1,13} = 57$ 은 독일과 브라질의 경기에서 독일이 57% 확률로 이긴다는 뜻입니다. 경기는 무승부로 끝나지 않으므로 모든 $i, j$ 에 대해 $p_{i,j} + p_{j,i} = 100$ 입니다.

출력

각 시나리오의 출력은 Scenario #i: 형식의 줄로 시작합니다. 여기서 $i$ 는 1부터 시작하는 시나리오 번호입니다. 그다음 16줄을 출력하며, 각 줄의 너비는 17입니다. 왼쪽에는 국가 이름을, 오른쪽에는 그 국가가 우승할 확률(퍼센트)을 소수점 아래 둘째 자리까지 반올림하여 출력하고, 그 사이는 공백 문자로 채웁니다. 국가의 순서는 입력과 동일하게 유지합니다. 연속된 시나리오 사이는 빈 줄 하나로 구분합니다.

예제1

예제 1

입력

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

예상 출력

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