C - コイン

C - コイン解説

実行時間制限: 2 sec / メモリ制限: 256 MB

高橋君は裏表が区別できる N 枚のコインを持っている。コインの大きさは異なり、それぞれのコインには 1 つずつ正の整数が書かれている。

これらのコインを無作為に (N! 通りの組み合わせがすべて同じ確率で出てくるように) 一列に並べる。その後、以下の手順を実行する。

すべてのコインを表向きにする。
左端のコインから順に、現在見ているコインよりも右側 (それ自身を除く) にあるコインのうち、現在見ているコインに書かれている整数の倍数が書かれているコインすべての裏表をひっくり返す。

高橋君はこの操作を終了した後に表を向いているコインの枚数の期待値が知りたい。

あなたは高橋くんの代わりに、期待値を計算するプログラムを作成してほしい。

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

N
C_1
C_2
:
C_N

1 行目には、コインの枚数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
2 行目から N 行のうち i (1 ≦ i ≦ N) 行目には、i 番目に大きいコインに書かれている整数 C_i (1 ≦ C_i ≦ 10^9) が書かれている。

この問題には部分点が設定されている。

表を向いているコインの枚数の期待値を出力せよ。絶対誤差または相対誤差が 10^{-6} 以下であれば許容される。出力の末尾にも改行を入れること。

2.166666666667

コインには、サイズの小さい方から順にそれぞれ 2 , 4 , 8 という数が書かれています。例えば、3! 通りの並べ方のうち、コインが大きさの昇順に並んでいる場合は、以下の手順が行われることになります。

初期状態で、すべてのコインを表に向けるので、コインは左から順に、[表, 表, 表] となっています。
次に、左から 2 番目以降のコインの中で、2 の倍数が書かれたコインを探します。左から 2 番目のコインと左から 3 番目のコインが該当するので、これらのコインを裏返します。その結果、コインは左から順に [表, 裏, 裏] となります。
次に、左から 3 番目以降のコインの中で、4 の倍数が書かれたコインを探します。左から 3 番目のコインのみが該当するので、このコインを裏返します。その結果、コインは左から順に [表, 裏, 表] となります。

コインの裏表は下図のように変化します。この図において、白いコインは表向きのコイン、黒いコインは裏向きのコインで表してあります。

このように、3! = 6 通りの並べ方について、それぞれの並べ方での最終状態は下図のようになります。

以上より期待値は 13/6 = 2.16666666666... となります。

2.000000000000

どのような順番で並べても、左から順に、[表, 裏, 表, 裏] となります。

3.100000000000