luogu#P1769. 淘汰赛制

淘汰赛制

题目描述

淘汰赛制是一种极其残酷的比赛制度。2n2^n 名选手分别标号 1,2,3,,2n1,2n1,2,3,\cdots,2^n-1,2^n,他们将要参加 nn 轮的激烈角逐。每一轮中,将所有参加该轮的选手按标号从小到大排序后,第 11 位与第 22 位比赛,第 33 位与第 44 位比赛,第 55 位与第 66 位比赛……只有每场比赛的胜者才有机会参加下一轮的比赛(不会有平局)。这样,每轮将淘汰一半的选手。nn 轮过后,只剩下一名选手,该选手即为最终的冠军。

现在已知每位选手分别与其他选手比赛获胜的概率,请你预测一下谁夺冠的概率最大。

输入格式

第一行是一个整数 n(1n10)n(1 \le n \le 10),表示总轮数。接下来 2n2^n 行,每行 2n2^n 个整数,第 ii 行第 jj 个是 pi,jp_{i,j}。(0pij1000 \le p_{i_j} \le 100pi,i=0p_{i,i}=0pi,j+pj,i=100p_{i,j}+p_{j,i}=100),表示第 ii 号选手与第 jj 号选手比赛获胜的概率。

输出格式

输出只有一个整数 cc,表示夺冠概率最大的选手编号(若有多位选手,输出编号最小者)。

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

 1

提示

  • 30%30\% 的数据满足 n3n \le 3
  • 100%100\% 的数据满足 n10n \le 10

_NOI导刊 2010 提高(01)