103425: [Atcoder]ABC342 F - Black Jack
Description
Score: $550$ points
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
Input
Output
问题描述
你将与庄家进行一场比赛。 游戏使用一个D面骰子（骰子），其等概率显示1到D之间的整数，以及两个初始化为0的变量x和y。游戏进行如下：
-
你可以任意多次执行以下操作：掷骰子并将结果加到x。每次掷骰后可以选择是否继续掷骰。
-
然后，庄家将在y小于L的情况下重复执行以下操作：掷骰子并将结果加到y。
-
如果x大于N，你输。否则，如果y大于N或x大于y，则你赢；如果两者都不满足，则你输。
当你以最大化获胜概率的方式行动时，确定获胜的概率。
约束条件
- 所有输入都是整数。
- 1≤L≤N≤2×105
- 1≤D≤N
输入
输入通过标准输入给出，格式如下：
N L D
输出
打印答案。如果你的输出与真实值的绝对误差或相对误差不超过10-6，则将被视为正确。
样例输入1
3 2 2
样例输出1
0.468750000000000
可以证明，最佳策略是在x不大于2的情况下继续掷骰。
样例输入2
200000 200000 200000
样例输出2
0.999986408692793