世界杯预言

Time Limit: 1000MS

Memory Limit: 65535K

Description

为了争夺世界杯的门票,一场世界范围类的足球巡回淘汰赛正在进行。假设共有2^n队伍,标号为1~2^n。在每一轮的比赛中,所有还留在淘汰赛中队伍按初始顺序排列,然后第1支队伍和第2支队伍比,第3支队伍和第4支队伍比...经过n轮候仅有1支队伍保持不败,这就是冠军!

提供一个矩阵P=p[i,j],pij表示i队伍打败j队伍的概率,然后确定哪支队伍最有可能赢得冠军!

Input

多组测试数据,以EOF结束。

每个测试样列:以n开始(1<=n<=8)

下面是矩阵 P,满足条件pij=1.0-pji,pii=0;

Output

一个整数,表示哪支队伍最有可能获得最后的冠军!

Sample Input

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

Sample Output

2

Hint

假设开始n=2共4支队伍,一轮后剩下2支,win(1,2),win(3,4);第二轮后剩下一支队伍
win(win(1,2),win(3,4));

Source

have

提交代码