UOJ Logo

NOI.AC

1S 512MB

#2099. 淘汰赛制

Statistics

【问题描述】

淘汰赛制是一种极其残酷的比赛制度。$2^n$名选手分别标号$1,2,3,……,2^n$,他们将要参加n轮的激烈角逐。每一轮中,将所有参加该轮的选手按标号从小到大排序后,第$1$位与第$2$位比赛,第$3$位与第$4$位比赛,第$5$位与第$6$位比赛……只有每场比赛的胜者才有机会参加下一轮的比赛(不会有平局)。这样,每轮将淘汰一半的选手。$n$轮过后,只剩下一名选手,该选手即为最终的冠军。 现在一年一度的泉州五中高一九班“五中素质人”大赛已拉开帷幕。已知每位选手分别与其他选手比赛获胜的概率(比如$F$小$X$对$Y$小$C$肯定是稳稳地晋级),请你预测一下谁夺冠的概率最大。

【输入文件】

第一行是一个整数$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$