AT_abc342_f [ABC342F] Black Jack

题目描述

你和庄家进行一场游戏。游戏使用一个有 $D$ 面的骰子，每一面等概率出现，且有两个初始为 $0$ 的变量 $x$ 和 $y$，规则如下：

• 你可以任意次数掷骰子，并将掷出的点数加到 $x$ 上。每次操作后，你可以选择是否继续操作。
• 然后，庄家会在 $y < L$ 的条件下，不断掷骰子，并将点数加到 $y$ 上，直到 $y \geq L$。
• 如果 $x > N$，你输。否则，如果 $y > N$ 或 $x > y$，你赢；否则你输。

请在你采取最优策略以最大化胜率的情况下，求出你的最大胜率。

输入格式

输入以以下格式从标准输入读入。

$N$ $L$ $D$

输出格式

请输出答案。当你输出的值与真值的绝对误差或相对误差不超过 $10^{-6}$ 时，将被判定为正确。

输入输出样例 #1

输入 #1

3 2 2

输出 #1

0.468750000000000

输入输出样例 #2

输入 #2

200000 200000 200000

输出 #2

0.999986408692793

说明/提示

限制

• 输入均为整数
• $1 \leq L \leq N \leq 2 \times 10^5$
• $1 \leq D \leq N$

样例解释 1

可以证明，当 $x \leq 2$ 时，继续操作是最优策略。

由 ChatGPT 4.1 翻译