← 返回题目列表

AtCoder · arc118_b

B. M人村

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

分数: 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