配点

満点

60

部分点

10

問題文

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

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

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

入力例 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