OI题库

【题目描述】

 

中国选手李娜获得了法网公开赛冠军，法网公开赛采用的是一种极其残酷的比赛制度：淘汰赛制。 2^n 名选手分别标号 1 ， 2 ， 3 ，…… 2^n-1 ， 2^n ，他们将要参加 n 轮的激烈角逐。每一轮中，将所有参加该轮的选手按标号从小到大排序后，第 1 位与第 2 位比赛，第 3 位与第 4 位比赛，第 5 位与第 6 位比赛……只有每场比赛的胜者才有机会参加下一轮的比赛（不会有平局）。这样，每轮将淘汰一半的选手。 N 轮过后，只剩下一名选手，该选手即为最终的冠军。

现在中网马上就要开始了，已知参加法网的每位选手分别与其他选手比赛获胜的概率，请你预测一下谁夺冠的概率最大。

【输入格式】

第一行是一个整数 n （ 1<=n<=10 ），表示总轮数。接下来 2^n 行，每行 2^n 个整数，第 i 行第 j 个是 pij （ 0<=pij<=100 ， pii=0 ， pij+pji=100 ），表示第 i 号选手与第 j 号选手比赛获胜的概率。

【输出格式】

一个整数 c ，表示夺冠概率最大的选手编号（若有多位选手，输出编号最小者）。

【样例输入】

2
0 90 50 50
10 0 10 10
50 90 0 50
50 90 50 0
 

【样例输出】

1

提示

 

30% 的数据满足 n<=3

 

100% 的数据满足 n<=10