[ABC126C] Dice and Coin
题意翻译
Snuke 有一个 $n$ 面的色子,投掷这个色子的时候会以相等的概率得到一个在 $1$ 到 $n$ 之间的整数。他还有一个硬币,投掷时正面朝上和反面朝上的概率相等。
现在他要用色子和硬币玩一个游戏:
* 扔色子,将得到的整数作为初始分数。
* 只要这个分数在 $1$ 到 $k-1$ 之间(包含 $1$ 和 $k-1$),就扔硬币。当正面朝上时,将这一分数翻倍;否则,将分数归零。
* 分数归零或大于等于 $k$ 时,游戏结束。若分数大于等于 $k$,Snuke 获胜,否则 Snuke 失败。
给出 $n$ 和 $k$,你需要求出 Snuke 获胜的概率。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc126/tasks/abc126_c
すぬけ君は $ 1 $ 〜 $ N $ の整数が等確率で出る $ N $ 面サイコロと表と裏が等確率で出るコインを持っています。すぬけ君は、このサイコロとコインを使って今から次のようなゲームをします。
1. まず、サイコロを $ 1 $ 回振り、出た目を現在の得点とする。
2. 得点が $ 1 $ 以上 $ K-1 $ 以下である限り、すぬけ君はコインを振り続ける。表が出たら得点は $ 2 $ 倍になり、裏が出たら得点は $ 0 $ になる。
3. 得点が $ 0 $ になった、もしくは $ K $ 以上になった時点でゲームが終了する。このとき、得点が $ K $ 以上である場合すぬけ君の勝ち、 $ 0 $ である場合すぬけ君の負けである。
$ N $ と $ K $ が与えられるので、このゲームですぬけ君が勝つ確率を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ K $
输出格式
すぬけ君が勝つ確率を出力せよ。絶対誤差または相対誤差が $ 10^{-9} $ 以下のとき正解とみなされる。
输入输出样例
输入样例 #1
3 10
输出样例 #1
0.145833333333
输入样例 #2
100000 5
输出样例 #2
0.999973749998
说明
### 制約
- $ 1\ <\ =\ N\ <\ =\ 10^5 $
- $ 1\ <\ =\ K\ <\ =\ 10^5 $
- 入力はすべて整数
### Sample Explanation 1
\- サイコロの出た目が $ 1 $ のとき、得点が $ 10 $ 以上になるためには、 $ 4 $ 回コインを振って $ 4 $ 連続で表が出る必要があります。この確率は、 $ \frac{1}{3}\ \times\ (\frac{1}{2})^4\ =\ \frac{1}{48} $ です。 - サイコロの出た目が $ 2 $ のとき、得点が $ 10 $ 以上になるためには、 $ 3 $ 回コインを振って $ 3 $ 連続で表が出る必要があります。この確率は、 $ \frac{1}{3}\ \times\ (\frac{1}{2})^3\ =\ \frac{1}{24} $ です。 - サイコロの出た目が $ 3 $ のとき、得点が $ 10 $ 以上になるためには、 $ 2 $ 回コインを振って $ 2 $ 連続で表が出る必要があります。この確率は、 $ \frac{1}{3}\ \times\ (\frac{1}{2})^2\ =\ \frac{1}{12} $ です。 よって、すぬけ君が勝つ確率は、 $ \frac{1}{48}\ +\ \frac{1}{24}\ +\ \frac{1}{12}\ =\ \frac{7}{48}\ \simeq\ 0.1458333333 $ です。