問題一覧 > 通常問題

No.1151 チャレンジゲーム

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

問題文

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

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

入力

N
A1 A2 AN

1N10
1Ai20 (1iN)

出力

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

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

サンプル

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

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

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

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

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

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