← 返回题目列表

AtCoder · tdpc_ball

J. 球

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

问题陈述

N 的事情。 第i 个是坐标 它位于 x_i 。蛇核,坐标 如果您将球瞄准该点 x 如果你瞄准该点扔球 x-1, x, x+1 有 1/3 的几率它会飞到其中任何一个,如果那里放了东西,它就会掉落。当使用最优策略投球时,求投球击倒所有物体的次数的期望值。
追記 : 您可以通过查看前一个球击中的位置来决定将球扔到哪里。

约束

  • 1 ≤ N ≤ 16
  • 0 ≤ x_i ≤ 15
  • x_i 成对不同。

输入格式

输入是按以下格式从标准输入给出的。
N
x_1 ... x_N

输出格式

将答案输出在一行上。当绝对误差小于 10^{-6} 时判定为合理。

示例输入 1

2
0 2

示例输出 1

4.500000000
最好继续将球扔向坐标 1。 有

示例输入 2

5
1 3 4 2 5

示例输出 2

8.986111111