二十一点

题目描述

你将与庄家玩一个游戏。 游戏使用一个 $D$ 面的骰子(每次以等概率掷出 $1$ 到 $D$ 的整数),以及两个初始化为 $0$ 的变量 $x$ 和 $y$。游戏按如下流程进行：

你可以进行任意多次以下操作:掷骰子并将结果加到 $x$ 上。每次掷完后,你可以选择继续掷骰子还是停止。

然后,庄家会在 $y \lt L$ 期间重复以下操作:掷骰子并将结果加到 $y$ 上。

如果 $x \gt N$,你输。否则,如果 $y \gt N$ 或 $x \gt y$,你赢;如果两种情况都不满足,你输。

求当你采取使获胜概率最大化的行动方式时,你获胜的概率。

输入格式

输入按以下格式从标准输入给出：

$N$ $L$ $D$

输出格式

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

样例

3 2 2

0.468750000000000

可以证明,最优策略是只要 $x$ 不超过 $2$ 就继续掷骰子。

200000 200000 200000

0.999986408692793

数据范围

• 所有输入值均为整数。
• $1 \le L \le N \le 2 \times 10^5$
• $1 \le D \le N$