Time Limit: 2 sec / Memory Limit: 256 MB
問題文
シカの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枚目を食べていないなら)食べる。
入力例2
17 17
出力例2
1.000000000000
全てのせんべいを食べることが出来るので、求める確率は1です。
入力例3
1000 10
出力例3
0.984898795563