← 返回题目列表

AtCoder · abc119_c

C. 合成门松

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

分数: 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,这是最佳的。

  1. 在长度相同的竹子上使用两次延伸魔法 98 获得长度为竹子 100。 (消耗MP: 2)
  2. 对长度的竹子使用合成魔法 40, 30 获得长度为竹子 70。 (消耗MP: 10)
  3. 对长度相同的竹子使用一次缩短魔法 21 获得长度为竹子 20。 (消耗MP: 1)
  4. 在长度的竹子上使用合成魔法 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