← 返回题目列表

AtCoder · abc126_c

C. 骰子和硬币

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

Snuke 有一个公平 N双面骰子,显示来自 1 to N 具有相同的概率和公平的硬币。他将和他们一起玩以下游戏:

  1. 扔骰子。当前分数是骰子的结果。
  2. 只要分数介于 1 和 K-1 (含),继续抛硬币。每次硬币正面朝上落地时,分数加倍,分数变为 0 如果硬币反面朝上。
  3. 当比分变为 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