← 返回题目
题库练习 淘汰赛制
← 上一题 下一题 →

A1834 | 淘汰赛制

来源NOI / 2010
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

淘汰赛制是一种极其残酷的比赛制度。$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
C++ 编辑器
输入
输出