← 返回题目列表

Codeforces · 2038/A

A. 奖金项目

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

有一个由 $$$n$$$ 软件工程师组成的团队,编号从 $$$1$$$ 到 $$$n$$$。他们的老板承诺,如果他们完成一个额外的项目,就会给他们奖金。该项目总共需要 $$$k$$$ 个工作单元。向第$$$i$$$工程师承诺的奖金是$$$a_i$$$ burles。老板不会给工程师分配具体的任务;预计每个工程师都会自愿完成一定数量的工作单元。只有项目完成后才会向整个团队发放奖金;换句话说,如果该项目的志愿工作单位总数大于或等于 $$$k$$$。

每个工程师可以执行的工作量不受限制。然而,所有工程师都重视他们的劳动。第 $$$i$$$ 工程师将他们的一个工作单元估计为 $$$b_i$$$ burles。如果支付奖金,则第 $$$i$$$ 工程师完成 $$$c$$$ 工作单元的收益 $$$s_i$$$ 定义为 $$$s_i = a_i - c \cdot b_i$$$。如果不支付奖金,工程师将不会自愿做任何工作。

工程师们一起工作多年,所以他们知道奖金将如何分配,以及同事对劳动的重视程度。也就是说,所有 $$$a_i$$$ 和所有 $$$b_i$$$ 都是团队中的每个工程师都知道的。

工程师们渴望得到奖金,因此他们同意以下的工作分配流程:

- 第一个工程师说:“我将完成 $$$c_1$$$ 工作单元”,其中 $$$c_1$$$ 是一个非负整数;
- 然后,第二个工程师说:“我将完成 $$$c_2$$$ 工作单元”,其中 $$$c_2$$$ 是一个非负整数;
- ...等等;
- 最后,第 $$$n$$$ 工程师说:“我将完成 $$$c_n$$$ 工作单元”,其中 $$$c_n$$$ 是一个非负整数。

每个工程师都以最大化自己利益$$$s_i$$$的方式表达$$$c_i$$$。如果预期收益为零,工程师仍然会同意通过工作来获得经验并帮助同事获得奖金。但是,如果由于某种原因预计收益为负(工程师需要执行过多的工作或项目无法完成),则该工程师将根本不会工作(完成零数量的工作单元)。

鉴于每个工程师都表现得完美,你的任务是找出每个工程师说出的数字$$$c_i$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 1000$$$; $$$1 \le k \le 10^6$$$)——分别是公司的工程师数量和项目需要的工作单元数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是项目完成后将支付给第 $$$i$$$ 工程师的奖金。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 1000$$$),其中 $$$b_i$$$ 是第 $$$i$$$ 工程师的工作单位成本。

输出

打印 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le k$$$) - 假设每个工程师都表现最佳,则每个工程师完成的工作量。请注意,答案是唯一的。

示例

输入 #1

3 6
4 7 6
1 2 3

输出 #1

1 3 2

输入 #2

3 12
4 7 6
1 2 3

输出 #2

0 0 0

输入 #3

3 11
6 7 8
1 2 3

输出 #3

6 3 2

注意

在第一个示例中,工程师将工作分配给他们并获得了奖金,尽管第三个工程师的收益为零。

在第二个示例中,奖金项目需要太多工作单元才能完成,因此对于工程师来说根本不工作更有利。