P13476 [GCJ 2008 APAC SemiFinal] Millionaire

你受邀参加了著名电视节目“你想成为百万富翁吗？”。当然你想！ 游戏规则很简单： - 在游戏开始前，主持人会转动幸运轮，决定每次下注获胜的概率 $P$。 - 你起始拥有 $X$ 美元。 - 游戏共进行 $M$ 轮下注。在每一轮中，你可以下注当前所拥有金额的任意部分，包括全部或不下注。下注金额可以不是整数。 - 如果你赢得本轮下注，你的总金额会增加你下注的金额；如果你输掉本轮下注，你的总金额会减少你下注的金额。 - 所有下注结束后，如果你累计金额达到 $1000000$ 或以上，你可以保留你的奖金（这时金额向下取整为整数美元）；否则你将一无所获。 给定 $M$、$P$ 和 $X$，请你计算在最优策略下（即最大化成为百万富翁概率的策略），你成为百万富翁的概率。

输入的第一行是测试用例数 $N$。 接下来的 $N$ 行，每行格式为 “$M$ $P$ $X$”，其中： - $M$ 为整数，表示下注轮数。 - $P$ 为实数，表示每轮下注获胜的概率。 - $X$ 为整数，表示初始金额（美元）。

对于每个测试用例，输出一行，格式为 “Case #$X$: $Y$”，其中： - $X$ 为测试用例编号，从 $1$ 开始。 - $Y$ 为成为百万富翁的概率，范围在 $0$ 到 $1$ 之间。 当你的答案的绝对误差或相对误差不超过 $10^{-6}$ 时，将被视为正确。

**样例解释** 在第一个样例中，唯一能达到 $1000000$ 的方式是在唯一一轮中押上全部金额。 在第二个样例中，你可以通过合理下注，即使输掉一轮也有机会成为百万富翁。以下是一种下注方式： - 第一轮你有 \$600000，下注 \$150000。 - 如果第一轮输了，你剩下 \$450000，下注 \$100000。 - 如果第一轮输了、第二轮赢了，你有 \$550000，下注 \$450000。 - 如果第一轮赢了，你有 \$750000，下注 \$250000。 - 如果第一轮赢了、第二轮输了，你有 \$500000，下注 \$500000。 **数据范围** - $1 \leq N \leq 100$ - $0 \leq P \leq 1.0$，小数点后最多 6 位 - $1 \leq X \leq 1000000$ **小数据集（13 分，测试点 1 - 可见）** - $1 \leq M \leq 5$ **大数据集（16 分，测试点 2 - 隐藏）** - $1 \leq M \leq 15$ 由 ChatGPT 4.1 翻译