C - 掷骰子和硬币

得分：$300$ 分

问题描述

Snuke 有一个公平的 $N$ 面骰子，显示从 $1$ 到 $N$ 的整数，概率相等，还有一枚公平的硬币。他将用它们来玩以下游戏：

1. 投掷骰子。当前得分是骰子的结果。
2. 只要得分在 $1$ 到 $K-1$ 之间（包括 $1$ 和 $K-1$），继续抛硬币。每次硬币正面朝上，得分翻倍，如果硬币背面朝上，得分变为 $0$。
3. 当得分变为 $0$ 或达到 $K$ 以上时，游戏结束。如果得分达到或超过 $K$，Snuke 赢了，否则输了。

给定 $N$ 和 $K$，求 Snuke 赢得比赛的概率。

约束

• $1 ≤ N ≤ 10^5$
• $1 ≤ K ≤ 10^5$
• 输入中所有的值均为整数。

输入

输入以以下格式从标准输入中给出：

$N$ $K$

输出

输出 Snuke 赢得比赛的概率。当绝对或相对误差不超过 $10^{-9}$ 时，输出被视为正确答案。

3 10

0.145833333333

• 如果骰子显示 $1$，Snuke 需要从四次硬币抛掷中连续得到四次正面，从而得分达到 $10$ 或以上。这个事件发生的概率为 $\frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48}$。
• 如果骰子显示 $2$，Snuke 需要从三次硬币抛掷中连续得到三次正面，从而得分达到 $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$。

100000 5

0.999973749998