← 返回题目列表

Codeforces · 678/E

E. 另一场西斯锦标赛

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

西斯锦标赛的规则是众所周知的。 n 西斯参加锦标赛。锦标赛开始时会随机选择两名西斯参加第一场战斗。当其中一人失败时,他的位置将由下一个随机选择的之前没有参加过战斗的西斯取代。难道西斯锦标赛的每一场战斗都以一名对手的死亡而告终吗?当唯一的西斯还活着时,锦标赛结束。

绝地伊万意外出现在西斯锦标赛的参赛者名单中。然而,他在原力光明面的技能非常强大,因此他可以影响参加者的选择,无论是开始锦标赛还是在每场战斗后取代失败者的位置。他当然不会错过这个利用的机会。帮助他计算胜利的概率。

输入

第一行包含一个整数 n (1 ≤ n ≤ 18) — 西斯锦标赛的参与者人数。

接下来的 n 行每行包含 n 个实数,它们形成一个矩阵 pij (0 ≤ pij ≤ 1)。它的每个元素 pij 是第 i 个参与者在决斗中击败第 j 个参与者的概率。

主对角线 pii 上的元素等于 0。对于所有不同的 i、j,等式 pij + pji = 1 成立。所有概率的给出不超过六位小数。

绝地伊万是参与者名单中的第一名。

输出

输出一个实数——绝地伊万在锦标赛后存活的概率。答案的绝对或相对误差不得超过 10 - 6。

示例

输入 #1

3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0

输出 #1

0.680000000000000