103425: [Atcoder]ABC342 F - Black Jack

Problem Statement

You will play a game against a dealer. The game uses a $D$-sided die (dice) that shows an integer from $1$ to $D$ with equal probability, and two variables $x$ and $y$ initialized to $0$. The game proceeds as follows:

• You may perform the following operation any number of times: roll the die and add the result to $x$. You can choose whether to continue rolling or not after each roll.

• Then, the dealer will repeat the following operation as long as $y < L$: roll the die and add the result to $y$.

• If $x > N$, you lose. Otherwise, you win if $y > N$ or $x > y$ and lose if neither is satisfied.

Determine the probability of your winning when you act in a way that maximizes the probability of winning.

Constraints

• All inputs are integers.
• $1 \leq L \leq N \leq 2 \times 10^5$
• $1 \leq D \leq N$

Input

The input is given from Standard Input in the following format:

$N$ $L$ $D$

Output

Print the answer. Your output will be considered correct if its absolute or relative error from the true value is at most $10^{-6}$.

Sample Input 1

3 2 2

Sample Output 1

0.468750000000000

It can be proved that the optimal strategy is to continue rolling as long as $x$ is not greater than $2$.

Sample Input 2

200000 200000 200000

Sample Output 2

0.999986408692793

问题描述

你将与庄家进行一场比赛。 游戏使用一个D面骰子（骰子），其等概率显示1到D之间的整数，以及两个初始化为0的变量x和y。游戏进行如下：

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

• 然后，庄家将在y小于L的情况下重复执行以下操作：掷骰子并将结果加到y。

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

当你以最大化获胜概率的方式行动时，确定获胜的概率。

约束条件

• 所有输入都是整数。
• 1≤L≤N≤2×10⁵
• 1≤D≤N

输入

输入通过标准输入给出，格式如下：

N L D

输出

打印答案。如果你的输出与真实值的绝对误差或相对误差不超过10^-6，则将被视为正确。

样例输入1

3 2 2

样例输出1

0.468750000000000

可以证明，最佳策略是在x不大于2的情况下继续掷骰。

样例输入2

200000 200000 200000

样例输出2

0.999986408692793