問題一覧 > 通常問題

No.1682 Unfair Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
20 ProblemId : 6805 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-29 18:22:17

問題文

$N$ 枚のコインがあり、$1$ から $N$ の番号がついています。
これらのコインは特殊な形状をしているため、$i$ 番目のコインを無作為に投げたときに表が出る確率は $\displaystyle{\frac{P_i}{100}}$、裏が出る確率は $\displaystyle{\frac{100-P_i}{100}}$ です。

この中から $1$ 枚以上のコインを選び、AliceとBobが次のようなゲームをします。

  • 選んだコインを全て無作為に投げる。
  • 表が出たコインの枚数が奇数ならAliceの勝ちであり、偶数ならBobの勝ちである。

コインの選び方は $2^N-1$ 通りあります。そのうち、Aliceの勝つ確率が $1/2$ より真に大きくなるような選び方は何通りあるでしょうか。
答えは非常に大きくなることがあるので $10^9+7$ で割った余りを出力してください。

入力

$N$
$P_1\ \ P_2\ \ \cdots\ \ P_N$

  • $1\le N\le 100$
  • $0\le P_i \le 100$
  • 入力は全て整数である。

出力

Aliceの勝つ確率が $1/2$ より真に大きくなるようなコインの選び方の数を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
2
30 80
出力
2

  • コイン $1$ のみを選ぶ場合、Aliceの勝つ確率は ${30}/{100}\ (\le 1/2)$ です。
  • コイン $2$ のみを選ぶ場合、Aliceの勝つ確率は ${80}/{100}\ (> 1/2)$ です。
  • 両方のコインを選ぶ場合、Aliceの勝つ確率は ${6200}/{10000}\ (> 1/2)$ です。
以上より答えは $2$ 通りです。

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

Aliceの勝つ確率がちょうど $1/2$ になる場合は答えに含めないことに注意してください。

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