Black Jack

题目描述

你将与庄家进行一场对局。该游戏使用一个 $D$ 面的骰子，骰子等概率显示从 $1$ 到 $D$ 的整数，且有两个变量 $x$ 和 $y$ 初始为 $0$ 。游戏按如下过程进行：

你可以执行以下操作任意多次：掷骰子并将结果加到 $x$ 上。在每次掷完后你可以选择是否继续掷骰子。

之后，庄家将重复以下操作只要 $y < L$ ：掷骰子并将结果加到 $y$ 上。

如果 $x > N$ ，你输。否则，如果 $y > N$ 或 $x > y$ 则你赢；如果两者都不满足则你输。

当你采取能够使获胜概率最大化的策略时，求你获胜的概率。

输入从标准输入给出，格式如下： $N$ $L$ $D$

输出答案。如果你的输出与真实值的绝对或相对误差不超过 $10^{-6}$ ，则认为是正确的。

3 2 2

0.468750000000000

200000 200000 200000

0.999986408692793

所有输入均为整数。 $1 \leq L \leq N \leq 2 \times 10^5$ $1 \leq D \leq N$ 可以证明最优策略是在 $x$ 不大于 $2$ 的情况下继续掷骰子。

标签: AtCoder|abc342F

AtCoder|abc342F