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