축구 토너먼트

$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$이다.