Description

你是“冗余缩减与多余消减部”的负责人。目前，部门内部对于自身是否存在过多的“繁文缛节”（低效）意见不一。他们请求你组建一个“繁文缛节委员会”，对这个问题进行投票。

部门共有 $\mathbf{N}$ 名成员。对于每一位成员，你都知道他投“同意”票的概率 $\mathbf{P}_{\mathbf{i}}$。如果某位成员没有投“同意”，则必然投“反对”；不会有人弃权。

你必须恰好选择 $\mathbf{K}$ 名成员组成该委员会。部门规定 $\mathbf{K}$ 必须是偶数，以便允许投票出现平局，因为平局被视为健康官僚体系的一部分。

如果你选择委员会成员，使得平局出现的概率最大，这个最大概率是多少？

Input Format

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

Output Format

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

3
2 2
0.50 0.50
4 2
0.00 0.00 1.00 1.00
3 2
0.75 1.00 0.50

Case #1: 0.5
Case #2: 1.0
Case #3: 0.5

Hint

样例解释

在样例第 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 完成。