Score: $550$ points

问题描述

你将与庄家进行一场游戏。该游戏使用一个 $D$ 面骰子（dice），每次投掷都会以相等的概率显示出从 $1$ 到 $D$ 的整数，同时有两个变量 $x$ 和 $y$ 初始化为 $0$。游戏按以下步骤进行：

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

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

• 若 $x > N$，你输掉游戏。否则，若满足 $y > N$ 或 $x > y$，则你赢得游戏；若两者都不满足，则你输掉游戏。

确定当你采取最大化获胜概率的行动时，你的获胜概率是多少。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:37:06