Dice and Coin

题目描述

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

掷骰子。当前分数为骰子点数。 只要分数在 $1$ 到 $K-1$（含）之间，就不断抛硬币。每次硬币出现正面时分数加倍，出现反面时分数变为 $0$。 当分数变为 $0$ 或达到 $K$ 或以上时游戏结束。若分数为 $K$ 或以上则 Snuke 获胜，若分数为 $0$ 则失败。

给定 $N$ 和 $K$。求 Snuke 获胜的概率。

输入格式

输入从标准输入给出，格式如下： $N$ $K$

输出格式

输出 Snuke 获胜的概率。当绝对误差或相对误差不超过 $10^{-9}$ 时，答案被认为是正确的。

3 10

0.145833333333

100000 5

0.999973749998

提示

$1 ≤ N ≤ 10^5$ $1 ≤ K ≤ 10^5$ 输入中的所有数值都是整数。如果骰子掷出 $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$.

标签: AtCoder|abc126C

来源

AtCoder|abc126C