一年一度的大学体育球锦标赛即将来临,出于商标原因,我们将其称为“第三个月疯狂”。共有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 轮中的获胜者。