← 返回题目列表

AtCoder · code_festival_2018_final_b

B. 主题颜色

中文机器翻译题面 查看原题

配点 : 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