프로그램 명: football
제한시간: 1 초

번호가 1,2,3,...,2^n 이 붙은 팀이 토너먼트 경기를 펼치고 있다. 토너먼트의 각 라운드에서 모든 팀은 증가하는 순으로 경기를 치른다. 즉 첫번째 팀은 두번째 팀과 경기를 한다. 3 번째 팀이 4 번째 팀과...

각 경기에서 이긴 사람이 다음 라운드로 진출한다. 진팀은 사라진다. n 라운드가 지난 후 오직 한 팀만이 우승자가 된다.

행렬 P=[pij] 가 주어진다. i 번째 팀이 j 번째 팀을 이길 확률이다. 이 확률로서 어떤 팀이 가장 우승 확률이 높은지를 알수 있다.

입력

n ( 1 <= n <= 7 ) 이 주어진다. 다음 2^n 라인에는 2^n 개의 수가 입력된다. 행렬 P 는 i 가 j 와 같지 않을 경우 pij = 1 - pji 가 성립하고 i = j 인 경우 pii=0 이다. 주어지는 숫자는 실수이고 , 프로그래밍시 float 타입보다 double 타입을 사용하는게 좋다네요.

출력

어떤 팀이 우승 확률이 가장 높은지 팀의 번호를 출력하는게 문제이다. 탑 두팀간의 우승 확률의 차이는 0.01 이상이다.

입출력 예

입력

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

출력

2

보충 설명

보기의 테스트 데이터인 경우 , 
P(2 wins)  = P(2 beats 1)P(3 beats 4)P(2 beats 3) + P(2 beats 1)P(4 beats 3)P(2 beats 4)
= p21p34p23 + p21p43p24
= 0.9 · 0.6 · 0.4 + 0.9 · 0.4 · 0.5 = 0.396.
다음으로 확률이 높은 팀은 3 번 팀으로 우승확률이 0.372 이다. 
출처:Stanford Local 2006
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]