AtCoder Regular Contest 055

B - せんべい


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

シカのAtCoDeerくんはせんべいが好きです。今、AtCoDeerくんは1~Nの番号のついたN枚のせんべいをくれると噂の高橋くんに目をつけました。番号が大きい方が大きくて価値があるので、AtCoDeer君は番号Nのせんべいは絶対に食べたいと考えました。しかし、AtCoDeerくんはお腹がいっぱいになるためK枚までしかせんべいを食べることが出来ません。

高橋くんは事前にN枚のせんべいを並び替え、一枚ずつ順にせんべいをAtCoDeerくんにあげようとします。AtCoDeerくんはi(1≦i≦N)枚目をもらうとき、そのせんべいを食べるかどうかをその時点で選択します。しかし、既にK枚食べている場合は、これ以上食べることは出来ません。食べない場合は高橋くんがそのせんべいを食べるので、後になってAtCoDeerくんがそのせんべいを食べることは出来ません。AtCoDeerくんはせんべいを見てもその番号はわかりませんが、既に見た(食べたものも含む)全てのせんべいの大小を比べることは出来ます。

高橋くんがせんべいをあげる順番はランダム(N!個の順列のうちから等確率で選ばれる)で、AtCoDeerくんには事前にはわかりません。 AtCoDeerくんが最適な戦略をとった時、最終的に番号NのせんべいをAtCoDeerくんが食べられる確率を求めてください。

制約

  • 1≦K≦N≦1000

入力

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

N K

出力

AtCoDeerくんが最適な戦略をとった時に最終的にせんべいNを食べられる確率を出力せよ。出力は絶対誤差または相対誤差が10^{-6}以下であれば許容される。


入力例1

3 1

出力例1

0.500000000000

次のような戦略が最適です。

  • 1枚目は食べない。
  • 2枚目は、1枚目より大きければ食べる。
  • 3枚目は、まだ食べられるなら(2枚目を食べていないなら)食べる。
この時、せんべいを見る順番が1,3,2 と 2,1,3 と 2,3,1 の時はせんべい3を食べることが出来るので、確率は3/3! = 1/2 です。


入力例2

17 17

出力例2

1.000000000000

全てのせんべいを食べることが出来るので、求める確率は1です。


入力例3

1000 10

出力例3

0.984898795563

Submit提出する