分数: 300 点
问题陈述
你有 N 竹子。这些的长度(以厘米为单位)是 分别是 l_1, l_2, ..., l_N。
你的目标是使用其中一些竹子(可能全部)来获得三根长度相同的竹子 A, B, C。为此,您可以任意使用以下三种魔法:
- 扩展魔法:消耗 1 MP (魔点)。选择一根竹子并将其长度增加 1.
- 缩短魔法:消耗 1 MP。至少选择一根长度相同的竹子 2 并将其长度减少 1.
- 合成魔法:消耗 10 MP。选择两根竹子,将它们组合成一根竹子。这根新竹子的长度等于两根竹子长度之和。 (之后,可以对这根竹子使用进一步的魔法。)
至少需要多少MP才能达到目的?
约束
- 3 \leq N \leq 8
- 1 \leq C < B < A \leq 1000
- 1 \leq l_i \leq 1000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A B C l_1 l_2 : l_N
输出
打印实现目标所需的最低 MP 数量。
示例输入 1
5 100 90 80 98 40 30 21 80
示例输出 1
23
我们正在获得三根长度相同的竹子 100, 90, 80 来自五竹 98, 40, 30, 21, 80。我们已经有一根长度的竹子了 80,我们可以获得长度的竹子 100, 90 通过使用以下魔法,总成本为 23 MP,这是最佳的。
- 在长度相同的竹子上使用两次延伸魔法 98 获得长度为竹子 100。 (消耗MP: 2)
- 对长度的竹子使用合成魔法 40, 30 获得长度为竹子 70。 (消耗MP: 10)
- 对长度相同的竹子使用一次缩短魔法 21 获得长度为竹子 20。 (消耗MP: 1)
- 在长度的竹子上使用合成魔法 70 步骤2中得到的竹子长度 步骤3中获得的 20 获得一段长度的竹子 90。 (消耗MP: 10)
示例输入 2
8 100 90 80 100 100 90 90 90 80 80 80
示例输出 2
0
如果我们已经拥有所需长度的所有竹子,则所需的 MP 量为 0。从这里可以看出,我们不一定需要使用所有的竹子。
示例输入 3
8 1000 800 100 300 333 400 444 500 555 600 666
示例输出 3
243