B - Theme Color
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 人のクラスがあり、色 1,2,...,M の中から 1 つの色を選んでテーマカラーを決めることとなりました。
それぞれの人が同確率でどれかの色 1 つに投票するとき、色 i(1 \leq i \leq M) に r_i 票集まる確率を p とします。
p \geq 10^{-x} を満たす最小の整数 x を求めてください。
ただし、p に 10^{-6} 以下の相対誤差が生じても x は変わらないことが保証されるものとします。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq r_i \leq N
- r_1+r_2+...+r_M=N
- 入力は全て整数
- p に 10^{-6} 以下の相対誤差が生じても解は変わらない
入力
入力は以下の形式で標準入力から与えられる。
N M r_1 r_2 ... r_M
出力
p \geq 10^{-x} を満たす最小の整数 x を出力せよ。
入力例 1
3 2 1 2
出力例 1
1
p=0.375 より、p \geq 10^{-x} を満たす最小の整数は 1 となります。
入力例 2
120 5 18 36 31 12 23
出力例 2
8