atcoder#ABC126C. [ABC126C] Dice and Coin

[ABC126C] Dice and Coin

配点 : 300300

問題文

すぬけ君は 11NN の整数が等確率で出る NN 面サイコロと表と裏が等確率で出るコインを持っています。すぬけ君は、このサイコロとコインを使って今から次のようなゲームをします。

  1. まず、サイコロを 11 回振り、出た目を現在の得点とする。
  2. 得点が 11 以上 K1K-1 以下である限り、すぬけ君はコインを振り続ける。表が出たら得点は 22 倍になり、裏が出たら得点は 00 になる。
  3. 得点が 00 になった、もしくは KK 以上になった時点でゲームが終了する。このとき、得点が KK 以上である場合すぬけ君の勝ち、 00 である場合すぬけ君の負けである。

NNKK が与えられるので、このゲームですぬけ君が勝つ確率を求めてください。

制約

  • 1N1051 \leq N \leq 10^5
  • 1K1051 \leq K \leq 10^5
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

NN KK

出力

すぬけ君が勝つ確率を出力せよ。絶対誤差または相対誤差が 10910^{-9} 以下のとき正解とみなされる。

3 10
0.145833333333
  • サイコロの出た目が 11 のとき、得点が 1010 以上になるためには、 44 回コインを振って 44 連続で表が出る必要があります。この確率は、 13×(12)4=148\frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48} です。
  • サイコロの出た目が 22 のとき、得点が 1010 以上になるためには、 33 回コインを振って 33 連続で表が出る必要があります。この確率は、 13×(12)3=124\frac{1}{3} \times (\frac{1}{2})^3 = \frac{1}{24} です。
  • サイコロの出た目が 33 のとき、得点が 1010 以上になるためには、 22 回コインを振って 22 連続で表が出る必要があります。この確率は、 13×(12)2=112\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$ です。

100000 5
0.999973749998