← 返回题目列表

AtCoder · tessoku_book_fi

C11. 选举

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

配点: 1000 点

問題文

今天,KYOPRO国家举行大选。N 政党作为候选人参选;i 方是 A_i 获得选票。根据比例代表制 K 分配席位时,每一方获得多少个席位?

然而,在比例代表制中,如下表所示,“票数÷席位数”中较大者 我们将从开始分配座位(不要方法)。

制約

  • 2 \leq N \leq 100000
  • 1 \leq K \leq 10^9
  • 1 \leq A_i
  • A_1 + A_2 + \cdots + A_N \leq 10^9
  • 构成边界的“票数 ÷ 席位数”的值为 超过 1 超过 10^9 少于
  • 边界为“票数÷席位数”,亚军为“票数÷席位数”。 超过相対誤差是 您也可以写 10^{-6} 超过
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 \cdots A_N

出力

请以整数形式输出答案。


入力例 1

4 10
1000000 700000 300000 180000

出力例 1

5 3 1 1

正如问题文本图片中所写。


入力例 2

2 3
6000 3000

出力例 2

2 1

该输入满足约束,但如果 请注意,如果 A = [6000, 3000] 和 K=2 边界已绑定,因此不满足约束(不应给出此类输入)。


入力例 3

15 50
18256245 7845995 6771945 6181431 3618432 3159625 2319156 1768385 1258501 1253872 193724 148020 109045 77861 65107

出力例 3

18 8 7 6 3 3 2 1 1 1 0 0 0 0 0

第 26 回参議院通常選挙数据。


入力例 4

2 1
900000000 100000000

出力例 4

1 0