F - バス旅行

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

問題文

N+1 個のバス停があり、0 から N の番号が付けられています。 バス停 i (0 ≤ i ≤ N-1)からはバス停 i+1 行きのバスが出ており、移動するのに t_{i+1} 分かかります。

また、正整数 k が定まっています。どのバス停 i (0 ≤ i ≤ N-1)からも、バス停 i+1 行きのバスは (時刻 0 分 〜 時刻 k-1 分のうち整数分のどこかで 1 回)、(時刻 k 分 〜 時刻 2k-1 分のうち整数分のどこかで 1 回)、(時刻 2k 分 〜 時刻 3k-1 分のうち整数分のどこかで 1 回)、... に発車します。 それぞれの時刻 mk 分〜 時刻 (m+1)k-1 分 の中では、等確率でどの整数分に発車するかが選ばれます。これは m ごと、バス停ごとに独立です。

すぬけ君は時刻 0 分にバス停 0 を出発し、N 本のバスに乗ってバス停 N まで移動しようとしています。 ただし、すぬけ君はあるバス停に到着すると同時に次のバスに乗ることができます。

バス停 N に到着するのに何分かかるか、期待値を求めてください。

制約

  • 1 ≤ N ≤ 10^5
  • 1 ≤ k ≤ 300
  • 1 ≤ t_i ≤ 10^9
  • 入力で与えられる値は全て整数

入力

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

N k
t_1
:
t_N

出力

バス停 N に到着するのに何分かかるかの期待値を出力せよ。絶対誤差または相対誤差が 10^{-9} 以下ならば正解となる。


入力例 1

2 2
2
1

出力例 1

4.125000000000
  • 時刻 0 分にバス停 0 からバスが発車し、時刻 2 分にバス停 1 に到着し、時刻 2 分にバス停 1 からバスが発車し、時刻 3 分にバス停 2 に到着する。これは確率 1/4 で起こります。
  • 時刻 0 分にバス停 0 からバスが発車し、時刻 2 分にバス停 1 に到着し、時刻 3 分にバス停 1 からバスが発車し、時刻 4 分にバス停 2 に到着する。これは確率 1/4 で起こります。
  • 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 3 分にバス停 1 からバスが発車し、時刻 4 分にバス停 2 に到着する。これは確率 1/4 で起こります。
  • 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 4 分にバス停 1 からバスが発車し、時刻 5 分にバス停 2 に到着する。これは確率 1/8 で起こります。
  • 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 5 分にバス停 1 からバスが発車し、時刻 6 分にバス停 2 に到着する。これは確率 1/8 で起こります。

よって、求める期待値は、3 \times (1/4) + 4 \times (1/4) + 4 \times (1/4) + 5 \times (1/8) + 6 \times (1/8) = 33/8 です。


入力例 2

6 4
4
6
4
2
1
7

出力例 2

34.524398803711