分数: 550 点
问题陈述
您将与荷官玩游戏。 游戏使用了一个 D单面骰子(骰子),显示一个整数 1 to D 具有相同的概率,并且有两个变量 x 和 y 初始化为 0。游戏进行如下:
-
您可以执行以下操作任意多次:掷骰子并将结果添加到 x。每次滚动后您可以选择是否继续滚动。
-
然后,庄家将重复以下操作,只要 y < L:掷骰子并将结果添加到 y.
-
If x > N,你输了。否则,如果 y > N or x > y 如果两者都不满足,则失败。
当您以最大化获胜概率的方式行事时,确定您获胜的概率。
约束
- 所有输入均为整数。
- 1 \leq L \leq N \leq 2 \times 10^5
- 1 \leq D \leq N
输入
输入由标准输入按以下格式给出:
N L D
输出
打印答案。如果您的输出与真实值的绝对或相对误差最多为 10^{-6}.
示例输入 1
3 2 2
示例输出 1
0.468750000000000
可以证明,只要满足以下条件,最优策略就是继续滚动 x 不大于 2.
示例输入 2
200000 200000 200000
示例输出 2
0.999986408692793