問題一覧 > 通常問題

No.1151 チャレンジゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 43
作問者 : 👑 Kiri8128Kiri8128 / テスター : theory_and_metheory_and_me
8 ProblemId : 4648 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-06 23:09:24

問題文

null さんと kiri さんはチャレンジゲームをします。 最初 $N$ 枚のカードがあり、 $i\ (1\le i\le N)$ 番目のカードには正の整数 $A_i$ が書かれています。
最初、null さんと kiri さんの得点はどちらも0点です。 null さんからはじめて、交互に次の操作をします。

  • まだ取り除かれていないカードを1枚選び、「チャレンジ」する。
  • 選んだカードに書かれている整数が $a$ のとき、チャレンジは $\displaystyle\frac{1}{a}$ の確率で成功する。
  • チャレンジが成功すると、そのカードは取り除かれ、チャレンジした人の得点に $a$ 点が加算される。
  • チャレンジに失敗した場合は、カードは取り除かれず、得点も変化しない。
  • チャレンジに成功しても失敗しても自分のターンは終了し、相手のターンになる。
すべてのカードが取り除かれるまでこれを繰り返します。 すべてのカードが取り除かれたとき、得点の多い方が勝ちです。 ただし同点の場合は kiri さんの勝ちとします。 お互いに自分の勝率を最大にするように行動するとき、null さんが勝つ確率を求めよ。

入力

$N$
$A_1\ A_2\ \cdots A_N$

$1\le N\le 10$
$1\le A_i\le 20\ (1\le i\le N)$

出力

答えを1行に出力してください。
最後に改行してください。
絶対誤差または相対誤差が $10^{-6}$ 以下の場合は正解とみなされます。

なお本問の制約下では、題意の確率が一意に定まることが示せます。

サンプル

サンプル1
入力
2
1 2
出力
0.6666666667

2枚のカードがありますが、2が書かれているカードを取った方が勝ちます。
2のカードが残っている限り、2を狙うのが最善です。2のカードにチャレンジしたときの成功率は $\displaystyle\frac12$ です。
null さんが勝つ確率は、 $\displaystyle\frac{1}{2} + (\frac{1}{2})^3 + (\frac{1}{2})^5 + \cdots = \frac{2}{3}$ です。

サンプル2
入力
4
1 1 1 1
出力
0

1が書かれたカードはチャレンジすると必ず成功します。
同点の場合は kiri さんの勝ちになります。

サンプル3
入力
5
3 4 5 9 11
出力
0.4818994264

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。