C - Cards
Editorial
/
Writer: komiya
Time Limit: 3 sec / Memory Limit: 256 MB
配点
- 満点
- 60
- 部分点
- 10
問題文
N 枚のカードが全て表を向いて並んでいる。それぞれのカードの表側には数字 X_i が書かれている。あなたは以下の操作を行う。
- 表になっているカードのうち無作為に2枚を選んで裏返す。
- 裏になっているカードのうち無作為に1枚を選んで裏返す。このとき選んだカードの表に書かれている数字をスコアに加算する。
- 表になっているカードが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