프랑스 월드컵 '98

면접 대비

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

요약

16개 팀의 모든 맞대결 승률과 고정된 대진표가 주어질 때, 각 팀이 단일 토너먼트에서 우승할 확률을 계산한다.

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

문제

프랑스에서 열린 월드컵 축구 대회의 1라운드가 막 끝나고 16개국이 남았습니다. 이제 아래의 싱글 엘리미네이션 토너먼트로 우승국이 결정됩니다.

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

이 16개국 사이에서 벌어질 수 있는 모든 경기 A 대 B에 대해, A가 B를 이길 확률이 주어집니다. 위 대진표와 이 확률만 있으면 각 국가가 월드컵에서 우승할 확률을 계산할 수 있습니다. 예를 들어 독일이 멕시코를 이길 확률이 80%, 루마니아가 크로아티아를 이길 확률이 60%, 독일이 루마니아를 이길 확률이 70%, 독일이 크로아티아를 이길 확률이 90%라고 하면, 독일이 준결승(4강)에 오를 확률은 $80\% \times (70\% \times 60\% + 90\% \times 40\%) = 62.4\%$ 입니다.

16개국이 각각 월드컵에서 우승할 확률을 계산하는 프로그램을 작성하세요.

입력

입력은 하나의 테스트 케이스로 이루어집니다.

첫 16개 줄에는 위 대진표에서 위에서 아래로의 순서대로 16개국의 이름이 한 줄에 하나씩 주어집니다.

이어서 $16 \times 16$ 정수 행렬 $P$ 가 주어집니다. 원소 $p_{ij}$ 는 국가 # $i$ 가 국가 # $j$ 를 직접 대결에서 이길 확률(퍼센트)입니다. 국가 # $i$ 는 목록에서 위에서 $i$ 번째 국가를 뜻합니다. 위 대진표에서 Brazil이 #1, Germany가 #13이므로, $p_{1,13} = 55$ 는 Brazil과 Germany의 경기에서 Brazil이 55% 확률로 이긴다는 뜻입니다.

경기는 무승부로 끝나지 않으므로, 모든 $i, j$ 에 대해 $p_{ij} + p_{ji} = 100$ 입니다.

출력

입력과 같은 순서로 각 국가마다 한 줄씩, 모두 16줄을 출력합니다. 각 줄의 형식은 <이름> p=Y.YY% 입니다. 국가 이름을 폭 10칸의 필드에 왼쪽 정렬하고, 공백 한 칸을 둔 뒤 p=, 그 국가의 우승 확률을 퍼센트로 소수점 아래 정확히 둘째 자리까지 쓴 값, %를 차례로 붙입니다.

예제1

예제 1

입력

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

예상 출력

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%