J - ボール
Editorial
/
N 個のものがある。i 番目のものは座標 x_i におかれている。すぬけ君が、座標 x の点を目指してボールを投げると x-1, x, x+1 のうちのいずれかに 1/3 ずつの確率で飛んでいき、そこに物がおいてあった場合は倒れる。最適な戦略でボールを投げたとき、すべての物を倒すのに必要なボールを投げる回数の期待値を求めよ。
追記 : ボールを投げる場所は、前に投げたボールの飛んだ場所を見た後に決めることができる。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。絶対誤差が 10^{-6} 以下のとき正当と判定される。
座標 1 に向かってボールを投げ続けるのがよい。
Time Limit: 2 sec / Memory Limit: 256 MB
Problem Statement
追記 : ボールを投げる場所は、前に投げたボールの飛んだ場所を見た後に決めることができる。
Constraints
- 1 ≤ N ≤ 16
- 0 ≤ x_i ≤ 15
- x_i are pairwise distinct.
Input Format
N x_1 ... x_N
Output Format
Sample Input 1
2 0 2
Sample Output 1
4.500000000
Sample Input 2
5 1 3 4 2 5
Sample Output 2
8.986111111