问题陈述
你应该玩石头剪刀布游戏。包括你在内,还有$N$玩家。
该游戏由多轮组成。随着回合的进行,剩余玩家的数量会减少。在每一轮中,剩下的每个玩家将独立选择任意形状。如果其他人都出示剪刀,则出示石头的人获胜。同样的道理,布赢石头,剪刀赢布。由于本游戏的特殊规则,不存在平局的情况:如果按照正常的石头剪刀布游戏规则打平,则编程竞赛评分最高的玩家(与本轮无关!)将是本轮的唯一获胜者。因此,每轮都有一些玩家获胜,而其他玩家则失败。失败者退出游戏,获胜者进入新一轮。他们重复这个过程,直到只有一名玩家成为获胜者。
每个玩家的编号从 $1$ 到 $N$。你的电话号码是 1 美元。你知道其他$N-1$玩家倾向于展示哪种形状,也就是说,你知道每个玩家展示石头、剪刀、布的概率。第 $i$ 个玩家以 $r_i$% 的概率展示石头,以 $p_i$% 的概率展示布,以 $s_i$% 的概率展示剪刀。编号为$i$的选手的编程竞赛评分为$a_i$。没有两个球员的评分相同。您的任务是计算当您根据每个玩家的倾向和评分采取最佳策略时赢得游戏的概率。
输入
输入由单个测试用例组成,格式如下。
$N$ $a_1$ $a_2\r_2\p_2\s_2$ $\vdots$ $a_N \ r_N \ p_N \ s_N$
第一行由单个整数 $N \ (2 \le N \le 14)$ 组成。 第二行由单个整数 $a_1 \ (1 \le a_1 \le N)$ 组成。 第 $(i+1)$ 行由四个整数 $a_i$、$r_i$、$p_i$ 和 $s_i$ 组成($1 \le a_i \le N$、$0 \le r_i、p_i、s_i \le 100$、$r_i + p_i + s_i = 100$),其中 $i = 2、\ldots、N$。 保证 $a_1, \ldots, a_N$ 成对不同。
输出
在一行中打印赢得比赛的概率。如果您的答案的绝对或相对误差不超过 $10^{-6}$,则您的答案将被接受。
示例输入 1
2 2 1 40 40 20
样本输入 1 的输出
0.8
由于您的评分高于其他玩家,因此如果您在第一轮获胜或平局,您将赢得比赛。
示例输入 2
2 1 2 50 50 0
样本输入 2 的输出
0.5
你必须在第一轮获胜。
示例输入 3
3 2 1 50 0 50 3 0 0 100
样本输入 3 的输出
1
在第一轮中,你的最佳策略是展示岩石。本轮您将以 50% 的胜率赢得比赛。剩下的 50%,你和第二个玩家进入第二轮,你必须拿出石头才能赢得比赛。
示例输入 4
3 2 3 40 40 20 1 30 10 60
样本输入 4 的输出
0.27
示例输入 5
4 4 1 34 33 33 2 33 34 33 3 33 33 34
样本输入 5 的输出
0.6591870816