축구 토너먼트

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

요약

각 팀의 맞대결 승률이 주어질 때, 2^n개 팀이 겨루는 단일 토너먼트에서 우승 확률이 가장 높은 팀을 찾는다.

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

문제

$2^n$ 개의 팀이 참가하는 싱글 엘리미네이션(단판 토너먼트) 축구 대회를 생각하자. 팀에는 $1, 2, \ldots, 2^n$ 번의 번호가 매겨져 있다. 각 라운드에서는 아직 탈락하지 않은 모든 팀을 번호가 커지는 순서로 나열한 뒤, 첫 번째 팀과 두 번째 팀이, 세 번째 팀과 네 번째 팀이, 이런 식으로 맞붙는다. 각 경기의 승자는 다음 라운드로 진출하고 패자는 탈락한다. $n$ 번의 라운드가 끝나면 한 번도 지지 않은 팀 하나만 남으며, 그 팀이 우승한다.

행렬 $P = [p_{ij}]$ 가 주어진다. 여기서 $p_{ij}$ 는 한 경기에서 팀 $i$ 가 팀 $j$ 를 이길 확률이다. 우승할 확률이 가장 높은 팀을 구하여라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ ( $1 \le n \le 7$ ) 하나가 적힌 줄로 시작한다. 이어지는 $2^n$ 개의 줄에는 각각 $2^n$ 개의 실수가 주어지며, $i$ 번째 줄의 $j$ 번째 값이 $p_{ij}$ 이다. 이 행렬은 모든 $i \ne j$ 에 대해 $p_{ij} = 1.0 - p_{ji}$ 를, 모든 $i$ 에 대해 $p_{ii} = 0.0$ 을 만족한다. $-1$ 하나만 적힌 줄이 입력의 끝을 나타낸다.

행렬의 각 값은 부동소수점 수이므로, 반올림 오차를 피하려면 double(배정밀도)을 사용하는 것이 좋다.

출력

각 테스트 케이스마다 우승할 확률이 가장 높은 팀의 번호를 한 줄에 출력한다. 우승 확률이 가장 높은 두 팀의 확률 차이는 항상 $0.01$ 이상임이 보장된다.

힌트

$n = 2$ 인 네 팀 예제(첫 번째 테스트 케이스의 행렬)를 생각해 보자. 첫 라운드에서 팀 1과 팀 2가, 팀 3과 팀 4가 맞붙고, 두 승자가 결승에서 만난다. 팀 2가 우승할 확률은 다음과 같다.

$p_{21}\,p_{34}\,p_{23} + p_{21}\,p_{43}\,p_{24} = 0.9 \cdot 0.6 \cdot 0.4 + 0.9 \cdot 0.4 \cdot 0.5 = 0.396.$

그다음으로 우승 가능성이 높은 팀은 팀 3이며, 그 확률은 $0.372$ 이다.

예제4

예제 1

입력

2
0.0 0.1 0.2 0.3
0.9 0.0 0.4 0.5
0.8 0.6 0.0 0.6
0.7 0.5 0.4 0.0
-1

예상 출력

예제 2
입력
```
1
0.0 0.3
0.7 0.0
-1
```
예상 출력
```
2
```
예제 3
입력
```
1
0.0 0.9
0.1 0.0
-1
```
예상 출력
```
1
```

예제 4

입력

2
0.0 0.1 0.2 0.3
0.9 0.0 0.4 0.5
0.8 0.6 0.0 0.6
0.7 0.5 0.4 0.0
1
0.0 0.8
0.2 0.0
-1

예상 출력

2
1