← 返回题目列表

Codeforces · 105/B

B. 黑暗组装

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

黑暗议会是幽冥界的一个统治机构。这里坐着为玩家做出最重要决定的参议员。例如,要扩大店铺的范围,或者提高角色的某些特性,都需要黑暗议会的批准。

黑暗议会由 n 名参议员组成。他们每个人的特点都是他的水平和对玩家的忠诚度。等级是一个正整数,反映了参议员的实力。忠诚度是指在投票中做出积极决定的概率,以百分比来衡量,精确度高达 10%。

参议员通过投票做出决定。他们每个人都会根据自己的忠诚度做出积极或消极的决定。如果严格超过半数的参议员做出积极决定,玩家的提案就会获得批准。

如果玩家的提案在投票后未获批准,那么玩家可以对黑暗议会的决定提出上诉。为此,玩家需要杀死所有投票反对的参议员(杀死参议员并没有什么错,他们稍后会复活并且会对待玩家更糟糕)。玩家能够杀死某一组参议员的概率等于 A / (A + B),其中 A 是所有玩家角色的等级总和,B 是该组中所有参议员的等级总和。如果玩家杀死所有不受欢迎的参议员,那么他的提议就会获得批准。

参议员非常喜欢甜食。可以通过给他们糖果来贿赂他们。每收到一颗糖果,参议员对玩家的忠诚度就会提高 10%。值得一提的是,忠诚度不能超过100%。玩家最多可以带 k 块糖果到法庭。投票开始前应该给参议员糖果。

确定如果糖果以最佳方式分配给参议员,黑暗议会批准玩家提案的概率。

输入

第一行包含三个整数 n、k 和 A (1 ≤ n, k ≤ 8, 1 ≤ A ≤ 9999)。

接下来是 n 行。其中第 i 个包含两个数字——bi 和 li——第 i 个参议员的级别和忠诚度。

所有参议员的级别都是1到9999(含)之间的整数。所有参议员的忠诚度都是0到100(含)之间的整数,并且都可以被10整除。

输出

打印一个精度为 10 - 6 的实数 — 黑暗议会批准玩家关于在参议员中尽可能最佳地分配糖果的提议的最大可能概率。

示例

输入 #1

5 6 100
11 80
14 90
23 70
80 30
153 70

输出 #1

1.0000000000

输入 #2

5 3 100
11 80
14 90
23 70
80 30
153 70

输出 #2

0.9628442962

输入 #3

1 3 20
20 20

输出 #3

0.7500000000

注意

在第一个样本中,糖果分配的最佳方式是将它们送给前三名参议员。它确保了大多数选票。

第二个样本玩家应该将所有三颗糖果给第五个参议员。