P13298 [GCJ 2013 #3] Cheaters

你在本地赌场玩轮盘赌已经有一段时间了。轮盘赌是一种简单的赌场游戏，多个玩家可以在 $0$ 到 $36$（包含 $0$ 和 $36$）之间的一个或多个数字上下注。接下来，轮盘会朝一个方向旋转，球会朝相反方向滚动。轮盘上同样有 $0$ 到 $36$ 这些数字。有些真实的轮盘还会有一个标记为 $00$ 的格子，但本题的轮盘没有。最终，球会落在某个数字上。如果某玩家在该数字上下注，他将获得 $36$ 倍的投注金额（即该注盈利为投注金额的 $35$ 倍），所有压在其他数字上的注则全部输掉。 不幸的是，运气一直不在你这边，你已经输了一整晚。某一时刻，你开始怀疑这轮盘赌是否公平。经过一段时间的观察，你发现了一个必然让赌场赚钱的规律：球总是落在**总投注金额最少的数字**上！如果有多个数字并列总投注金额最少，则球会等概率落在这些数字中之一。 当然，你会把这种作弊行为报告给相关部门，但你首先想利用你发现的新规律把输掉的钱赢回来。为此，你会等到其他所有玩家下注结束后，再下注。遗憾的是，你剩下的资金有限，不能下注超过这个额度。你可以选择在零个或多个不同的数字上下注，每个数字上下注的金额可以不同且为任意正整数，只要所有下注的总和不超过你的预算即可。你想知道，在最优下注策略下，你**能获得的最大期望盈利**是多少？

第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据包含两行。第一行为两个整数：你剩余的资金 $B$，以及其他玩家已经下注的数字数量 $N$。第二行为 $N$ 个整数 $X_i$，表示其他玩家在这 $N$ 个不同数字上各自的总下注金额。

对于每个测试用例，输出一行 `"Case #x: "`，后接你在最优下注策略下能获得的最大期望盈利。只要你的答案与正确答案的绝对误差或相对误差不超过 $10^{-6}$，即被判为正确。

**样例说明** 在样例 $2$ 中，你可以在 $34$ 个未被下注的数字上各下注 $1$，这样无论球落在这 $34$ 个数字中的哪一个，你都能获得 $36$，总盈利为 $36 - 34 = 2$。在样例 $3$ 中，你可以在 $33$ 个未被下注的数字上各下注 $1$，此时以 $33/35$ 的概率赢得 $36$，期望盈利为 $33/35 \times 36 - 33$。 **限制条件** - $1 \leq T \leq 100$ - $1 \leq N \leq 37$ **小数据集（7 分，测试集 1 - 可见）** - $1 \leq B, X_i \leq 1,000$ **大数据集（10 分，测试集 2 - 隐藏）** - $1 \leq B, X_i \leq 10^{12}$ 翻译由 ChatGPT-4.1 完成。