P13199 [GCJ 2016 #2] Red Tape Committee

你是“冗余缩减与多余消减部”的负责人。目前，部门内部对于自身是否存在过多的“繁文缛节”（低效）意见不一。他们请求你组建一个“繁文缛节委员会”，对这个问题进行投票。 部门共有 $\mathbf{N}$ 名成员。对于每一位成员，你都知道他投“同意”票的概率 $\mathbf{P}_{\mathbf{i}}$。如果某位成员没有投“同意”，则必然投“反对”；不会有人弃权。 你必须恰好选择 $\mathbf{K}$ 名成员组成该委员会。部门规定 $\mathbf{K}$ 必须是偶数，以便允许投票出现平局，因为平局被视为健康官僚体系的一部分。 如果你选择委员会成员，使得平局出现的概率最大，这个最大概率是多少？

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组两行。第一行为两个整数 $\mathbf{N}$ 和 $\mathbf{K}$，分别表示部门成员数和委员会成员数。第二行为 $\mathbf{N}$ 个十进制小数 $\mathbf{P}_{\mathbf{i}}$，每个小数精确到小数点后两位，表示第 $i$ 位成员投“同意”票的概率。

对于每组测试用例，输出一行 `Case #x: y`，其中 $\mathrm{x}$ 是测试用例编号（从 1 开始），$\mathrm{y}$ 是一个浮点数，表示平局出现的最大概率。$\mathrm{y}$ 只要与正确答案的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

**样例解释** 在样例第 1 组中，你只能用这两名成员组建委员会。仅当两人投票不同，才会出现平局，这种情况发生的概率为一半。（不妨设定第一人的投票，第二人投相反的概率为 $0.5$。） 在样例第 2 组中，最优策略是选中一位“同意”概率为 $0.00$ 的成员和一位“同意”概率为 $1.00$ 的成员，这样必然平局。 在样例第 3 组中，假设你选择“同意”概率为 $0.50$ 和 $0.75$ 的两人。平局发生在第一个人投“同意”、第二个人投“反对”（概率 $0.5 \times 0.25 = 0.125$），或第一个人投“反对”、第二个人投“同意”（概率 $0.5 \times 0.75 = 0.375$）。总平局概率为 $0.125 + 0.375 = 0.5$。如果选 $0.50$ 和 $1.00$，平局概率也是 $0.5$，因为 $1.00$ 那个人一定投“同意”，$0.50$ 那个人必须投“反对”。如果选 $0.75$ 和 $1.00$，平局概率只有 $0.25$，因为 $1.00$ 那个人一定投“同意”，$0.75$ 那个人必须投“反对”。所以 $0.5$ 是最优解。 **限制条件** - $1 \leqslant \mathbf{T} \leqslant 100$。 - $2 \leqslant \mathbf{K} \leqslant \mathbf{N}$。 - $\mathbf{K}$ 为偶数。 - $0.00 \leqslant \mathbf{P}_{\mathbf{i}} \leqslant 1.00$。 **小数据集（5 分，测试集 1 - 可见）** - 时间限制：~~60~~ 15 秒。 - $2 \leqslant \mathbf{N} \leqslant 16$。 **大数据集（测试集 2 - 隐藏）** - 时间限制：~~120~~ 30 秒。 - $2 \leqslant \mathbf{N} \leqslant 200$。 翻译由 GPT4.1 完成。