D - 乱数生成

Contest Duration: 2015-08-29 21:00:00+0900 - 2015-08-29 23:00:00+0900 (local time) (120 minutes) Back to Home

D - 乱数生成 Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

2 つの整数 N、K が与えられます。

1 以上 N 以下の整数のなかからどれか 1 つ、等確率に選ぶ機械を考えます。

その機械を 3 回動かした時、選ばれた 3 つの数の中央値が K となる確率を求めてください。

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

N K

1 行目には整数 N(1 ≦ N ≦ 10^6)、K(1 ≦ K ≦ N) が空白区切りで与えられる。

出力の中央値が K となる確率を出力せよ。出力は標準出力に行い、末尾に改行を入れること。

なお、想定解との絶対誤差または相対誤差が 10^{-9} 以下であれば、正解として扱われる。

3 2

0.48148148148148148148

中央値が 2 となるのは、( 1 回目の出力, 2 回目の出力, 3 回目の出力) が

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
(1, 2, 2)
(2, 1, 2)
(2, 2, 1)
(3, 2, 2)
(2, 3, 2)
(2, 2, 3)
(2, 2, 2)

となる場合で、このいずれかが出る確率は 13/27 = 0.481481481... です

3 1

0.25925925925925925926

765 573

0.00147697396984624371