P13170 [GCJ 2017 #1C] Core Training

编写 Code Jam 题目很难，因此我们开发了一个 AI 来提出新点子。为了让 AI 尽可能有创造力，我们为它配备了 $N$ 个不同的“核心”，每个核心都有自己的“个性”。然而，就像人一样，这些核心可能会分心、损坏或拒绝工作；第 $i$ 个核心正常工作的概率为 $P_i$。只要至少有 $K$ 个核心正常工作，AI 就能正常运行。否则，它很可能会变得邪恶，把我们困在自己设计的恶魔谜题迷宫里。谁知道它会对 Code Jam 做些什么——也许会写出一堆难到爆炸的概率题！ 为了防止这种情况发生，我们计划训练一个或多个核心，使其更可靠。我们总共有 $U$ 个“训练单元”可以用来提升核心的可靠性。将 $X$ 个训练单元分配给第 $i$ 个核心，会使其成功概率增加 $X$。我们可以随意分配这些训练单元，也可以让一个或多个核心不分配任何训练单元。当然，核心的成功概率不能超过 $1$。 如果我们以最大化 AI 正常运行概率的方式分配训练单元，这个概率是多少？

输入的第一行包含测试用例数 $T$。接下来有 $T$ 组测试数据，每组包含三行。第一行包含两个整数 $N$ 和 $K$，分别表示核心总数和 AI 正常运行所需的最少正常核心数。第二行包含一个有理数 $U$，表示训练单元的数量。第三行包含 $N$ 个有理数 $P_i$，第 $i$ 个数表示第 $i$ 个核心正常工作的概率。所有概率均精确到小数点后四位。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是在最优分配训练单元后 AI 正常运行的概率。如果 $y$ 与正确答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

**样例解释** 注意，最后两个样例不会出现在小数据集 1 中。 在样例 1 中，我们有足够的训练单元，可以让所有核心的成功概率都变为 1，因此 AI 一定能正常运行。 在样例 2 中，两个核心都必须正常工作，AI 才能正常运行，因此必须给每个核心分配一些训练单元。最优方案是将每个核心都训练到 $0.5$。此时 AI 正常运行的概率为 $0.5 \times 0.5 = 0.25$。其他分配方式都不如这个好；比如把一个核心训练到 $0.9$，另一个训练到 $0.1$，成功概率只有 $0.9 \times 0.1 = 0.09$。 在样例 3 中，我们没有训练单元可用，且至少需要一个核心正常工作。可以先计算 AI 无法正常工作的概率，即所有核心都失效。两个核心都失效的概率为 $(1 - 0.9) \times (1 - 0.8) = 0.02$。因此至少有一个核心正常工作的概率，即 AI 正常运行的概率为 $1 - 0.02 = 0.98$。 在样例 4 中，最优策略是将所有训练单元都分配给第二个核心。这样至少有一个核心正常工作的概率为 $1 - (0.4 \times 0.6) = 0.76$。其他分配方式都不如这个好；比如全部分配给第一个核心只得到 $0.75$，平均分配给两个核心得到 $0.7525$。 **数据范围** - $1 \leq T \leq 100$。 - $1 \leq N \leq 50$。 - 对所有 $i$，$0.0000 \leq P_i \leq 1.0000$。 - $0.0000 \leq U \leq N - \sum P_i$。（不会有多于可用的训练单元。） **小数据集 1（15 分，测试集 1 - 可见）** - 时间限制：5 秒。 - $K = N$。（所有核心都必须正常工作，AI 才能正常运行。） **小数据集 2（28 分，测试集 2 - 可见）** - 时间限制：10 秒。 - $1 \leq K \leq N$。 由 ChatGPT 4.1 翻译