← 返回题目列表

AtCoder · nupc2024_b

B. 改变

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

配点 : 100 点

問題文

目前在 NUPC 国家 N 流通中的硬币种类繁多,其价值为 C_1, C_2, \dots, C_N 这是日元。

您将依次收到这些硬币。 A_1, A_2, \dots, A_N 我每一个都有。

你 M 我想购买价值 ¥ 的产品。 商店单独存放所有硬币。 10^{100} 我各有一个,M 如果您支付的金额超过日元,则将以最低数量的硬币支付找零。 (在这个问题的约束下,唯一确定了这种支付方式。)

此外,不支持将支付时使用的硬币作为找零退回的支付方式。 例如,10 使用日元硬币进行支付和找零。 10 无法使用日元硬币进行支付。

您希望最大限度地减少购买产品后剩余的硬币数量。 请输出一个最小化手头剩余硬币数量的支付方式示例。 是

制約

  • 输入全部为整数
  • 1\leq N\leq 30
  • 1=C_1<C_2<\cdots<C_N\leq 10^9
  • C_{i+1} 是 C_{i} 的倍数 (1\leq i\leq N-1)
  • 0\leq A_i\leq 10^9 (1\leq i\leq N)
  • 1\leq M\leq \sum_{i=1}^N {C_i \cdot A_i}

入力

输入如下格式从标准输入给出。

N M
C_1 C_2 \dots C_N
A_1 A_2 \dots A_N

出力

请输出付款方式示例如下。

m_1 m_2 \dots m_N

这里 m_1, m_2, \dots, m_N 是支付的每个硬币的数量, 0\le m_i \le A_i (1\le i \le N)和 必须满足 \sum_{i=1}^N C_i \cdot m_i \geq M 。


入力例1

6 100
1 5 10 50 100 500
1 1 1 1 1 1

出力例1

0 0 0 0 1 0

100 日元硬币 当您使用 1 金币时,您最终拥有的金币数量为 5 件。 这是答案的示例,因为不可能支付低于4 的费用。


入力例2

6 100
1 5 10 50 100 500
2 2 2 2 2 2

出力例2

0 2 0 2 0 0

50 日元硬币 当您使用 2 枚、5 日元硬币 当您使用 2 金币时,您最终拥有的金币数量为 9 件。 这是答案的示例,因为不可能支付低于8 的费用。

您还可以使用以下付款方式。 9 可以实现,但是10 由于我使用日元硬币付款并收到零钱,因此不符合付款方式条件。

0 2 1 2 0 0

入力例3

4 1000
1 100 500 1000
2000 0 0 0

出力例3

2000 0 0 0