配点

満点

60

部分点

10

---

問題文

$N$ 枚のカードが全て表を向いて並んでいる。それぞれのカードの表側には数字 $X_i$ が書かれている。あなたは以下の操作を行う。

1. 表になっているカードのうち無作為に2枚を選んで裏返す。
2. 裏になっているカードのうち無作為に1枚を選んで裏返す。このとき選んだカードの表に書かれている数字をスコアに加算する。
3. 表になっているカードが2枚以上あれば1に戻る。表になっているカードが1枚しかなければ操作を終了する。

操作を終了したときのスコアの期待値を求めよ。

---

入力形式

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

$N\\\\ X_1\\ X_2\\ ...\\ X_N$

$N$ はカードの枚数である。$X_i$ は $i$ 枚目のカードの表に書かれている数字である。

出力形式

期待値を出力せよ。ただし、実際の値との相対誤差または絶対誤差が $10^{-6}$ 以内でなければならない。

制約

• $2 ≤ N ≤ 20$
• $1 ≤ X_i ≤ 1000$
• 入力値はすべて整数である。

この問題の判定には、10 点分のテストケースのグループが設定されている。 このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす。

• $2 ≤ N ≤ 12$

---

入力例 1

2
10 21

出力例 1

15.5

まず、表になっている2枚を両方裏返す。

次に、裏になっている2枚から無作為に1枚を選んで表にする。このときカードに書かれた分の点数を得ることができる。

この時点で表になっているカードは1枚しかないので、操作を終了する。

$10$が選ばれる確率は$0.5$で、$21$が選ばれる確率は$0.5$なので、期待値は$10\*0.5 + 21\*0.5 = 15.5$となる。

---

入力例 2

3
1 2 3

出力例 2

4

---

入力例 3

13
748 401 960 630 659 363 612 514 258 361 914 107 149

出力例 3

6162.4615384

---

Writer: komiya

---

Source Name

Autumn Fest

---