题目名称 603. 网球赛
输入输出 elimination.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2011-11-04加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:24, 提交:55, 通过率:43.64%
Gravatar苏轼 100 0.149 s 8.24 MiB Pascal
Gravatarwangyucheng 100 0.151 s 10.19 MiB C++
Gravatardevil 100 0.168 s 8.48 MiB C++
GravatarEzoi_XY 100 0.169 s 10.44 MiB Pascal
Gravatarmildark 100 0.230 s 8.41 MiB C++
Gravatarcstdio 100 0.234 s 8.41 MiB C++
GravatarHouJikan 100 0.254 s 8.59 MiB C++
Gravatarmikumikumi 100 0.258 s 8.50 MiB C++
Gravatar张灵犀不和我一般见识真可怕呢(笑 100 0.282 s 8.50 MiB C++
GravatarDes. 100 0.305 s 30.80 MiB Pascal
本题关联比赛
20111104
20111104
关于 网球赛 的近10条评论(全部评论)
把概率加起来求最大有60分...
GravatarHakurou!
2016-08-25 09:50 2楼
一个错的DP方程居然过了6组……拜RP大神
Gravatarcstdio
2013-11-02 18:13 1楼

603. 网球赛

★☆   输入文件:elimination.in   输出文件:elimination.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

 

中国选手李娜获得了法网公开赛冠军,法网公开赛采用的是一种极其残酷的比赛制度:淘汰赛制。 2^n 名选手分别标号 1 , 2 , 3 ,…… 2^n-1 , 2^n ,他们将要参加 n 轮的激烈角逐。每一轮中,将所有参加该轮的选手按标号从小到大排序后,第 1 位与第 2 位比赛,第 3 位与第 4 位比赛,第 5 位与第 6 位比赛……只有每场比赛的胜者才有机会参加下一轮的比赛(不会有平局)。这样,每轮将淘汰一半的选手。 N 轮过后,只剩下一名选手,该选手即为最终的冠军。

现在中网马上就要开始了,已知参加法网的每位选手分别与其他选手比赛获胜的概率,请你预测一下谁夺冠的概率最大。

【输入格式】

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