分数: 300 点
问题陈述
Snuke 有一个公平 N双面骰子,显示来自 1 to N 具有相同的概率和公平的硬币。他将和他们一起玩以下游戏:
- 扔骰子。当前分数是骰子的结果。
- 只要分数介于 1 和 K-1 (含),继续抛硬币。每次硬币正面朝上落地时,分数加倍,分数变为 0 如果硬币反面朝上。
- 当比分变为 0 或变为 K 或以上。如果比分是 Snuke 获胜 K 或以上,如果分数为 0.
你被给予 N 和 K。求 Snuke 赢得比赛的概率。
约束
- 1 ≤ N ≤ 10^5
- 1 ≤ K ≤ 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
输出
打印 Snuke 赢得比赛的概率。当绝对或相对误差最大时,输出被认为是正确的 10^{-9}.
示例输入 1
3 10
示例输出 1
0.145833333333
- 如果骰子显示 1,Snuke需要在四次抛硬币中连续得到四次正面才能获得分数 10 或以上。这种情况发生的概率是 \frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48}.
- 如果骰子显示 2, Snuke 需要在 3 次抛硬币中连续得到 3 个正面才能获得分数 10 或以上。这种情况发生的概率是 \frac{1}{3} \times (\frac{1}{2})^3 = \frac{1}{24}.
- 如果骰子显示 3,Snuke需要在两次抛硬币中连续得到两次正面才能获得分数 10 或以上。这种情况发生的概率是 \frac{1}{3} \times (\frac{1}{2})^2 = \frac{1}{12}.
因此,Snuke 获胜的概率为 \frac{1}{48} + \frac{1}{24} + \frac{1}{12} = \frac{7}{48} \simeq 0.1458333333.
示例输入 2
100000 5
示例输出 2
0.999973749998