Description

你受邀参加了著名电视节目“你想成为百万富翁吗？”。当然你想！

游戏规则很简单：

• 在游戏开始前，主持人会转动幸运轮，决定每次下注获胜的概率 $P$。
• 你起始拥有 $X$ 美元。
• 游戏共进行 $M$ 轮下注。在每一轮中，你可以下注当前所拥有金额的任意部分，包括全部或不下注。下注金额可以不是整数。
• 如果你赢得本轮下注，你的总金额会增加你下注的金额；如果你输掉本轮下注，你的总金额会减少你下注的金额。
• 所有下注结束后，如果你累计金额达到 $1000000$ 或以上，你可以保留你的奖金（这时金额向下取整为整数美元）；否则你将一无所获。

给定 $M$、$P$ 和 $X$，请你计算在最优策略下（即最大化成为百万富翁概率的策略），你成为百万富翁的概率。

Input Format

输入的第一行是测试用例数 $N$。

接下来的 $N$ 行，每行格式为 “$M$ $P$ $X$”，其中：

• $M$ 为整数，表示下注轮数。
• $P$ 为实数，表示每轮下注获胜的概率。
• $X$ 为整数，表示初始金额（美元）。

Output Format

对于每个测试用例，输出一行，格式为 “Case #$X$: $Y$”，其中：

• $X$ 为测试用例编号，从 $1$ 开始。
• $Y$ 为成为百万富翁的概率，范围在 $0$ 到 $1$ 之间。

当你的答案的绝对误差或相对误差不超过 $10^{-6}$ 时，将被视为正确。

2
1 0.5 500000
3 0.75 600000

Case #1: 0.500000
Case #2: 0.843750

Hint

样例解释

在第一个样例中，唯一能达到 $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 翻译