No.1151 チャレンジゲーム
タグ : / 解いたユーザー数 46
作問者 : Kiri8128 / テスター : theory_and_me
問題文
null さんと kiri さんはチャレンジゲームをします。
最初 $N$ 枚のカードがあり、 $i\ (1\le i\le N)$ 番目のカードには正の整数 $A_i$ が書かれています。
最初、null さんと kiri さんの得点はどちらも0点です。
null さんからはじめて、交互に次の操作をします。
- まだ取り除かれていないカードを1枚選び、「チャレンジ」する。
- 選んだカードに書かれている整数が $a$ のとき、チャレンジは $\displaystyle\frac{1}{a}$ の確率で成功する。
- チャレンジが成功すると、そのカードは取り除かれ、チャレンジした人の得点に $a$ 点が加算される。
- チャレンジに失敗した場合は、カードは取り除かれず、得点も変化しない。
- チャレンジに成功しても失敗しても自分のターンは終了し、相手のターンになる。
入力
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。