分数: 400 点
问题陈述
ARC共和国有 N 公民,所有人都在玩竞技性节目。每个公民都有一个丹 (等级) 这是 1, 2, \ldots,或 K,根据他们的技能。
全国人口普查显示,确实有 A_i 丹公民 i。为了使这些数据更容易理解,国王决定将这个国家描述为一个村庄 M 人。
设置段位人数 i 在村子里, B_i,这样 \max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right| 被最小化,同时满足以下条件:
- 每个 B_i 是一个非负整数,满足 \sum_{i=1}^K B_i = M.
打印这样的方式设置 B = (B_1, B_2, \ldots, B_K).
约束
- 1\leq K\leq 10^5
- 1\leq N, M\leq 10^9
- 每个 A_i 是满足以下条件的非负整数 \sum_{i=1}^K A_i = N.
输入
输入由标准输入按以下格式给出:
K N M A_1 A_2 \ldots A_K
输出
打印整数序列中的元素 B 一行满足要求,中间有空格。
B_1 B_2 \ldots B_K
如果多个序列满足要求,则其中任何一个序列都将被接受。
示例输入 1
3 7 20 1 2 4
示例输出 1
3 6 11
在此输出中,我们有 \max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right| = \max\left(\left|\frac{3}{20}-\frac{1}{7}\right|, \left|\frac{6}{20}-\frac{2}{7}\right|, \left|\frac{11}{20}-\frac{4}{7}\right|\right) = \max\left(\frac{1}{140}, \frac{1}{70}, \frac{3}{140}\right) = \frac{3}{140}.
示例输入 2
3 3 100 1 1 1
示例输出 2
34 33 33
请注意 B_1 = B_2 = B_3 = 33 不满足要求,因为总和必须是 M = 100.
在此示例中,除了 34 33 33,打印 33 34 33 or 33 33 34 也将被接受。
示例输入 3
6 10006 10 10000 3 2 1 0 0
示例输出 3
10 0 0 0 0 0
示例输入 4
7 78314 1000 53515 10620 7271 3817 1910 956 225
示例输出 4
683 136 93 49 24 12 3