Description

在游戏 League of Legends（英雄联盟）中，有一种叫做 “ARAM”（All Random, All Mid，全随机单中路） 的游戏模式。本题借鉴了这一设定，但无需了解英雄联盟也能理解题意。

每次开始 ARAM 游戏时，你会从 $\mathrm{N}$ 个“英雄”（champions）中等概率地随机获得一个。你使用某些英雄时更容易获胜，因此当运气不好时，你可能希望自己能抽到另一个英雄。幸运的是，游戏中提供了“重新抽取”（Reroll）的功能。

重新抽取的机制如下所述，但你不能随时使用它。重新抽取的能力可以看作是一种货币：在你开始第一个 ARAM 游戏之前，你拥有 $\mathrm{R}$ 个“重新抽取点数”（RD，Reroll Dollars）。你只有在手上至少有 $1$ RD 时，才可以使用重新抽取，每次消耗 $1$ RD。

每打完一局游戏，你会获得 $1 / \mathrm{G}$ 个 RD（其中 $\mathrm{G}$ 是一个整数），但你的 RD 总数永远不会超过 $\mathrm{R}$：即使你已经拥有 $\mathrm{R}$ 个 RD，打完一局之后你仍然只有 $\mathrm{R}$ 个。

如果你手上有至少 $1$ RD，并选择使用重新抽取，则你会消耗 $1$ RD，并重新从 $\mathrm{N}$ 个英雄中等概率地抽取一个（可能会重复拿到当前的英雄）。如果你不满意新的英雄，并且还有 $1$ RD 以上，你可以继续重新抽取。只要你还剩下 RD，就可以继续抽。

例如，如果 $\mathrm{R} = 2$ 且 $\mathrm{G} = 2$，你在第一局游戏使用了一次重新抽取，那么该局之后你将拥有 $1.5$ RD。下一局若未使用重新抽取，该局结束后你将拥有 $2.0$ RD。再下一局若也未使用，那么仍为 $2.0$（因为不能超过上限）。如果你在接下来的游戏中使用了两次重新抽取，那么该局结束后你将剩下 $0.5$ RD。

你将得到一份英雄列表，以及每个英雄的胜率。如果你要打 $10^{100}$ 局游戏，并始终采用最优策略（即期望胜率最大化），那么你预期能赢下多少比例的游戏？

Input Format

第一行是测试用例数 $\mathrm{T}$。接下来的 $\mathrm{T}$ 个测试用例格式如下：

每个测试用例的第一行包含三个空格分隔的整数：$\mathrm{N}, \mathrm{R}, \mathrm{G}$。

第二行包含 $\mathrm{N}$ 个用空格分隔的实数 $\mathrm{P}_i$，表示使用第 $i$ 个英雄时的胜率（$0 \leq \mathrm{P}_i \leq 1$）。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你在使用最优策略、打 $10^{100}$ 局游戏后预期获胜的比例。

输出结果要求与正确答案的绝对误差或相对误差不超过 $10^{-10}$。

3
2 1 1
1.0000 0.0000
3 1 1
1.0000 0.0000 0.5000
6 2 3
0.9000 0.6000 0.5000 0.1000 0.2000 0.8000

Case #1: 0.750000000000
Case #2: 0.666666666667
Case #3: 0.618728522337

Hint

限制条件

• $1 \leq \mathrm{T} \leq 100$
• $0.0 \leq \mathrm{P}_i \leq 1.0$，每个胜率值格式为 1 位整数 + 小数点 + 4 位数字

Small 数据集（22 分）

• 时间限制：60 3 秒
• $1 \leq \mathrm{N} \leq 1000$
• $1 \leq \mathrm{R} \leq 2$
• $1 \leq \mathrm{G} \leq 3$

Large 数据集（42 分）

• 时间限制：120 5 秒
• $1 \leq \mathrm{N} \leq 1000$
• $1 \leq \mathrm{R} \leq 20$
• $1 \leq \mathrm{G} \leq 20$

翻译由 ChatGPT-4o 完成