CF105B Dark Assembly

黑暗议会是冥界的一个管理机构。这里坐着最重要的议员，他们为玩家做出最关键的决策。例如，若要扩展商店的商品范围或提升角色的某些属性，都需要黑暗议会的批准。 黑暗议会由 $n$ 名议员组成。每位议员有两个属性：等级和对玩家的忠诚度。等级是一个正整数，反映了议员的实力。忠诚度表示议员在投票时做出正面决策的概率，以百分比表示，精确到 $10\%$。 议员通过投票来做决策。每位议员会根据自己的忠诚度做出正面或负面决策。如果有超过一半的议员做出正面决策，玩家的提案就会被批准。 如果投票后玩家的提案未获批准，玩家可以对黑暗议会的决定提出上诉。为此，玩家需要杀死所有投了反对票的议员（杀死议员没什么大不了的，他们会复活，并且之后对玩家更加敌视）。玩家能够杀死某一组议员的概率为 $A/(A+B)$，其中 $A$ 是玩家所有角色的等级之和，$B$ 是这组议员的等级之和。如果玩家杀死了所有不受欢迎的议员，那么他的提案就会被批准。 议员们非常喜欢糖果。通过给他们糖果可以贿赂他们。每获得一颗糖果，议员对玩家的忠诚度提升 $10\%$。需要注意的是，忠诚度不能超过 $100\%$。玩家最多可以带 $k$ 颗糖果进入议会。糖果必须在投票开始前分配给议员。 请你计算，在最优分配糖果的情况下，黑暗议会批准玩家提案的最大概率。

第一行包含三个整数 $n$、$k$ 和 $A$（$1 \leq n, k \leq 8$，$1 \leq A \leq 9999$）。 接下来 $n$ 行，每行包含两个整数 $b_i$ 和 $l_i$，分别表示第 $i$ 位议员的等级和忠诚度。 所有议员的等级为 $1$ 到 $9999$ 之间的整数（含 $1$ 和 $9999$）。所有议员的忠诚度为 $0$ 到 $100$ 之间的整数，且都能被 $10$ 整除。

输出一个实数，表示在最优分配糖果的情况下，黑暗议会批准玩家提案的最大概率，精确到 $10^{-6}$。

在第一个样例中，最优的糖果分配方式是将糖果分给前三位议员，这样可以确保获得最多的正面投票。 在第二个样例中，玩家应将所有三颗糖果都分给第五位议员。 由 ChatGPT 4.1 翻译