← 返回题目列表

AtCoder · relay2018_f

F. 巴士行程

中文机器翻译题面 查看原题

配点 : 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 和每个公交车站都是独立的。

Snuke 是时候了 0 分钟后到达巴士站 从 0 出发N 乘坐书巴士到巴士站 正在尝试移至 N 。 然而,Snuke 一到达一个公交车站就可以登上下一趟公交车。

巴士站 求到达 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