A16823 | $Create or Duplicate$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

圣诞老人发现手绘圆圈太耗时，因此他决定借助魔法来实现生产目标。 有三种不同价值的礼物，其价值分别为 $a$、$b$ 和 $c$。初始时，圣诞老人各有一种类型的礼物各一件。 你将得到两个整数 $m$ 和 $k$，分别代表圣诞老人最喜欢的数字以及复制魔法的花费。圣诞老人可以不限次数地施放以下两种魔法（可能为零次）： 1. 创造——选择一种礼物类型，额外创造一个同类型礼物。此法术消耗 $x$ 点魔力，其中 $x\in \{a, b, c\}$，表示所选类型的价值。 2. 复制——选择一种礼物类型，并将所有该类型的礼物复制一份。此法术消耗 $k$ 点魔力。 圣诞老人希望通过一系列法术操作，使所有礼物的总价值之和成为 $m$ 的倍数。 请你计算，为达成要求，圣诞老人至少需要消耗多少魔力。在给定约束下，总有一种可行方案。

每个测试点包含多组用例。第一行为测试用例个数 $t$（$1 \leq t \leq 10^4$）。接下来每个测试用例一行，包含五个整数 $a$、$b$、$c$、$m$、$k$（$1 \leq a < b < c < m \leq 5 \cdot 10^5$，$1 \leq k \leq 5 \cdot 10^5$）。 保证所有测试用例中 $m$ 的总和不超过 $5 \cdot 10^5$。 保证所有测试用例中 $k$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示使所有礼物价值和成为 $m$ 的倍数所需的最小魔力值。

输入 #1

7
1 2 3 21 4
3 4 5 12 34
3 12 14 18 1
6 7 8 10 3
100 103 282 488 221
307 2000 5096 12018 5764
194093 292793 395323 475619 490151

输出 #1

令 $\ell$ 表示当前所有礼物的价值序列，$\operatorname{sum}(\ell)$ 为其元素之和。 样例第一个用例的最优操作如下： | # | 操作 | 操作类型 | 操作后 $\ell$ | $\operatorname{sum}(\ell)$ | 花费 | |---|---------------|----------|------------------------|----------------------------|-------| | 0 | — | — | $[1, 2, 3]$ | $6$ | — | | 1 | Create $3$ | 创造 $3$ | $[1, 2, 3, 3]$ | $9$ | $3$ | | 2 | Create $3$ | 创造 $3$ | $[1, 2, 3, 3, 3]$ | $12$ | $3$ | | 3 | Duplicate $3$ | 复制 $3$ | $[1, 2, 3, 3, 3, 3, 3, 3]$ | $21$ | $4$ | | | | | | $21 = 7 \times 3$ | | | | | | | 总计 | $10$ | 样例第二个用例，不操作即最优，因为 $3+4+5=12$ 已经是 $12$ 的倍数。 样例第三个用例的最优操作如下： | # | 操作 | 操作类型 | 操作后 $\ell$ | $\operatorname{sum}(\ell)$ | 花费 | |---|----------------|-----------|-----------------------------|----------------------------|------| | 0 | — | — | $[3, 12, 14]$ | $29$ | — | | 1 | Duplicate $12$ | 复制 $12$ | $[3, 12, 12, 14]$ | $41$ | $1$ | | 2 | Duplicate $14$ | 复制 $14$ | $[3, 12, 12, 14, 14]$ | $55$ | $1$ | | 3 | Create $14$ | 创造 $14$ | $[3, 12, 12, 14, 14, 14]$ | $69$ | $14$ | | 4 | Duplicate $3$ | 复制 $3$ | $[3, 3, 12, 12, 14, 14, 14]$| $72$ | $1$ | | | | | | $72 = 18 \times 4$ | | | | | | | 总计 | $17$ |

C++ 编辑器

输入

输出