P13386 [GCJ 2011 Finals] Google Royale

在访问 Theta VIII 星球时，你们的太空探险队被迫卷入了一本写得很烂的小说情节中，故事发生在一家名为 Google Royale 的游戏厅。为了逃离 Royale，你必须通过游戏赚到足够的钱，以 $V$ 美元买下这家酒店并离开。 你起始拥有 $A$ 美元，并将参与一轮又一轮的游戏，直到满足以下两个条件之一。如果你在任何一轮游戏结束后剩余的钱 $\leq 0$，你就输了；如果你在某一轮结束后拥有的钱 $\geq V$，你就可以买下酒店并离开。否则，你将继续开始新的一轮游戏。 每一轮游戏由一次或多次抛硬币组成。如果你在本轮开始时有 $X$ 美元，你可以选择在第一次抛硬币时下注任意整数 $B$，其中 $1 \leq B \leq \min(X, M)$。 以 $50\%$ 的概率，你赢得这次抛硬币，Royale 立即支付你 $B$ 美元。此时你拥有 $X+B$ 美元，本轮结束。 以 $50\%$ 的概率，你输掉这次抛硬币，欠 Royale $B$ 美元。你可以选择支付这 $B$ 美元并结束本轮。或者，如果 $2B \leq M$，你也可以选择暂缓支付，继续以 $2B$ 美元进行第二次抛硬币。如果你再次输掉，那么你欠 Royale $B+2B=3B$ 美元。你可以继续以此方式将下注翻倍为 $4B$、$8B$ 等，直到你赢得一次抛硬币、选择停止，或下一次下注将超过 $M$。即使本轮累计下注总额超过你当前拥有的钱 $X$，你也可以继续。 本轮结束后，你必须向 Royale 支付所有输掉抛硬币的下注金额，如果你赢了一次抛硬币，Royale 会支付你那次的金额。例如，如果你以 $1$ 美元开始下注，连续输掉三次抛硬币后第四次赢了，你将获得 $8-4-2-1=1$ 美元。如果你连续输掉三次后选择停止，你将损失 $4+2+1=7$ 美元。如果你支付后剩余的钱 $\leq 0$，你就破产了，输掉了游戏。 幸运的是，你带来了一个机器人助手，他能够计算出如果你采取最优策略，获胜的概率是多少。请你计算这个概率，以及在不降低获胜概率的前提下，你可以选择的最大初始下注金额。注意，你的下注金额不能超过 $M$！

第一行输入一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行，每行包含三个用空格分隔的整数：$A$、$M$ 和 $V$，含义如上所述。

对于每个测试用例，输出一行，格式为 “Case #$x$: $y$ $z$”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在采取最优策略时获胜的概率，$z$ 是在不降低获胜概率的前提下你可以选择的最大初始下注金额。$y$ 需要保证绝对误差或相对误差不超过 $10^{-6}$。

**数据范围** - $1 \leq T \leq 100$。 **小数据集（20 分，测试点 1 - 可见）** - $1 \leq M \leq 20$。 - $1 \leq A < V \leq 20$。 - 时间限制：6 秒。 **大数据集（40 分，测试点 2 - 隐藏）** - $1 \leq M \leq 10^{16}$。 - $1 \leq A < V \leq 10^{16}$。 - 时间限制：12 秒。 由 ChatGPT 4.1 翻译