P13269 [GCJ 2014 Finals] ARAM

League of Legends 是 Riot Games 的商标。Riot Games 并未参与也未支持 Google Code Jam。

在游戏 *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}$ 局游戏，并始终采用最优策略（即期望胜率最大化），那么你预期能赢下多少比例的游戏？

第一行是测试用例数 $\mathrm{T}$。接下来的 $\mathrm{T}$ 个测试用例格式如下： 每个测试用例的第一行包含三个空格分隔的整数：$\mathrm{N}, \mathrm{R}, \mathrm{G}$。 第二行包含 $\mathrm{N}$ 个用空格分隔的实数 $\mathrm{P}_i$，表示使用第 $i$ 个英雄时的胜率（$0 \leq \mathrm{P}_i \leq 1$）。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你在使用最优策略、打 $10^{100}$ 局游戏后预期获胜的比例。 输出结果要求与正确答案的绝对误差或相对误差不超过 $10^{-10}$。

## 限制条件 - $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 完成