淘汰赛制
题目描述
淘汰赛制是一种极其残酷的比赛制度。$2^n$ 名选手分别标号 $1,2,3,\cdots,2^n-1,2^n$,他们将要参加 $n$ 轮的激烈角逐。每一轮中,将所有参加该轮的选手按标号从小到大排序后,第 $1$ 位与第 $2$ 位比赛,第 $3$ 位与第 $4$ 位比赛,第 $5$ 位与第 $6$ 位比赛……只有每场比赛的胜者才有机会参加下一轮的比赛(不会有平局)。这样,每轮将淘汰一半的选手。$n$ 轮过后,只剩下一名选手,该选手即为最终的冠军。
现在已知每位选手分别与其他选手比赛获胜的概率,请你预测一下谁夺冠的概率最大。
输入输出格式
输入格式
第一行是一个整数 $n(1 \le n \le 10)$,表示总轮数。接下来 $2^n$ 行,每行 $2^n$ 个整数,第 $i$ 行第 $j$ 个是 $p_{i,j}$。($0 \le p_{i_j} \le 100$,$p_{i,i}=0$,$p_{i,j}+p_{j,i}=100$),表示第 $i$ 号选手与第 $j$ 号选手比赛获胜的概率。
输出格式
输出只有一个整数 $c$,表示夺冠概率最大的选手编号(若有多位选手,输出编号最小者)。
输入输出样例
输入样例 #1
2
0 90 50 50
10 0 10 10
50 90 0 50
50 90 50 0
输出样例 #1
1
说明
- $30\%$ 的数据满足 $n \le 3$;
- $100\%$ 的数据满足 $n \le 10$。
_NOI导刊 2010 提高(01)