← 返回题目列表

Codeforces · 859/D

D. 第三个月的疯狂

中文机器翻译题面 查看原题

一年一度的大学体育球锦标赛即将来临,出于商标原因,我们将其称为“第三个月疯狂”。共有2N支队伍参加比赛,编号从1到2N。锦标赛持续N轮,每轮淘汰一半队伍。第一轮由 2N - 1 场比赛组成,编号从 1 开始。第 i 场比赛中,2·i - 1 队将对阵 2·i 队。失败者被淘汰,获胜者晋级下一轮(没有平局)。随后的每一轮比赛场数为上一轮的一半,并且在第 i 场比赛中,上一轮比赛 2·i - 1 的获胜者将与上一轮比赛 2·i 的获胜者进行比赛。

每年办公室都会有一个池子,看看谁能创造出最好的支架。括号是每场比赛的一组获胜者预测。对于第一轮的比赛,您可以预测任何一方获胜,但对于后面几轮的比赛,您预测的获胜者也必须被预测为上一轮的获胜者。请注意,支架是在实际进行任何游戏之前完全构建的。第一轮正确预测得 1 分,后续每一轮正确预测得分是前一轮的两倍,因此最后一局正确预测得 2N - 1 分。

对于联盟中的每对球队,您已经估计了每支球队在对阵时获胜的概率。现在您想要构造一个具有最大可能期望分数的括号。

输入

输入将从包含 N (2 ≤ N ≤ 6) 的行开始。

接下来是 2N 行,每行有 2N 个整数。第 i 行的第 j 列表示 i 队击败 j 队的概率,除非 i = j,否则该值为 0。可以保证第 j 行的第 i 列加上第 i 行的第 j 列正好是 100。

输出

打印所有可能的括号中可能的最大预期分数。您的答案必须正确,绝对或相对误差在 10 - 9 之间。

正式来说,让您的答案为 a,陪审团的答案为 b。如果 $${ \frac { | 则您的答案将被认为是正确的a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 9 }$$。

示例

输入 #1

2
0 40 100 100
60 0 40 40
0 60 0 45
0 60 55 0

输出 #1

1.75

输入 #2

3
0 0 100 0 100 0 0 0
100 0 100 0 0 0 100 100
0 0 0 100 100 0 0 0
100 100 0 0 0 0 100 100
0 100 0 100 0 0 100 0
100 100 100 100 100 0 0 0
100 0 100 0 0 100 0 0
100 0 100 0 100 100 100 0

输出 #2

12

输入 #3

2
0 21 41 26
79 0 97 33
59 3 0 91
74 67 9 0

输出 #3

3.141592

注意

在第一个示例中,您应该预测第 1 队和第 4 队将在第 1 轮中获胜,并且预测第 1 队将在第 2 轮中获胜。回想一下,您在第 2 轮中预测的获胜者也必须被预测为第 1 轮中的获胜者。