Collector

Time Limit : 2 sec, Memory Limit : 65536 KB

Problem K: Collector

※この物語はフィクションであり、実在の人物、団体などとは一切関係がありません。

最近ソーシャルゲームがとても人気で、 たくさんの会社がソーシャルゲームを開発しています。

あなたは競合しているソーシャルゲーム開発会社の一つにスパイとして潜入しています。

問題

あなたの務めている会社では、ソーシャルゲームを開発している。 開発しているゲームは、カードを集めて戦うゲームであり、1回300円の有料”ガチャガチャ”を収益の柱にしている。 このゲームのカードには、”ノーマル”、”レア”、”Sレア”の3種類がある。”Sレア”カードはN種類存在する。 有料”ガチャガチャ”では、1回行うごとに97%の確率で1枚のレアカードが手に入り、3%の確率で1枚のSレアカードが手に入る。

有料”ガチャガチャ”における各Sレアカードの出現割合(合計3%)を操作する権限を持っているあなたは、 会社の利益を「減少」させることにした。

まず、様々なプレイヤーの有料”ガチャガチャ”の利用傾向を調べたところ、 「各プレイヤーは、 各々の好きなSレアカードを引くと、 満足し、その後は”ガチャガチャ”の利用を行わない」ということが明らかになった。 以上の情報より、 あなたは ”各プレイヤーは、特定のSレアカードを好み、そのSレアカードを引くまでガチャガチャをし続ける” という仮定の下で会社の利益をモデル化した。

すなわち会社の利益とは、 Sレアカードiを好む人の割合 × Sレアカードiが得られるまでの消費金額の期待値 の総和である。

Sレアカードの出現割合を適切に操作することで、 会社の利益を「最小化」せよ。

ただし、出現割合は以下の条件を満たさなければならない。

  • Sレアカード全体の出現割合の和は3%である
  • 各Sレアカードの出現割合は最低0.01%である

入力

N (Sレアカードの種類)
P_1 (カード1が好きな人の割合)
P_2 (カード2が好きな人の割合)
...
P_N (カードNが好きな人の割合)

出力

問題文で定義された会社の利益の最小値を出力せよ。

制約

  • \( N \)は整数
  • \( 1 \leq N \leq 300 \)
  • \( 0.0 \leq P_i (1 \leq i \leq N) \leq 1.0 \)
  • \( P_1 + P_2 + \cdots + P_N = 1.0 \)
  • \( P_i \)は小数点以下5桁まで与えられる
  • 誤差は相対\( 10 ^ {-6} \) まで許容される

入出力例

入力1

1
1.00000

出力1

10000

入力2

2
0.00001
0.99999

出力2

10063.3444816

カード1は\( 0.01% \)の割合で出現し、カード2は\( 2.99% \)の割合で出現するように設定する。

入力3

2
0.50000
0.50000

出力3

20000.0000000

Source: UEC Programming Contest 2013 , Aizu Commpetitive Programming Camp 2013 Day 3, Japan, 2013-09-05
Problem Setter:  k_operafan ,  todo