Problem:


Score : 300 points

Problem Statement

You have N bamboos. The lengths (in centimeters) of these are l_1, l_2, ..., l_N, respectively.

Your objective is to use some of these bamboos (possibly all) to obtain three bamboos of length A, B, C. For that, you can use the following three kinds of magics any number:

Extension Magic: Consumes 1 MP (magic point). Choose one bamboo and increase its length by 1.

Shortening Magic: Consumes 1 MP. Choose one bamboo of length at least 2 and decrease its length by 1.

Composition Magic: Consumes 10 MP. Choose two bamboos and combine them into one bamboo. The length of this new bamboo is equal to the sum of the lengths of the two bamboos combined. (Afterwards, further magics can be used on this bamboo.)

At least how much MP is needed to achieve the objective?

Constraints

3 \leq N \leq 8

1 \leq C < B < A \leq 1000

1 \leq l_i \leq 1000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B C
l_1
l_2
:
l_N

Output

Print the minimum amount of MP needed to achieve the objective.

Sample Input 1

5 100 90 80
98
40
30
21
80

Sample Output 1

23

We are obtaining three bamboos of lengths 100, 90, 80 from five bamboos 98, 40, 30, 21, 80. We already have a bamboo of length 80, and we can obtain bamboos of lengths 100, 90 by using the magics as follows at the total cost of 23 MP, which is optimal.

Use Extension Magic twice on the bamboo of length 98 to obtain a bamboo of length 100. (MP consumed: 2)

Use Composition Magic on the bamboos of lengths 40, 30 to obtain a bamboo of length 70. (MP consumed: 10)

Use Shortening Magic once on the bamboo of length 21 to obtain a bamboo of length 20. (MP consumed: 1)

Use Composition Magic on the bamboo of length 70 obtained in step 2 and the bamboo of length 20 obtained in step 3 to obtain a bamboo of length 90. (MP consumed: 10)

Sample Input 2

8 100 90 80
100
100
90
90
90
80
80
80

Sample Output 2

0

If we already have all bamboos of the desired lengths, the amount of MP needed is 0. As seen here, we do not necessarily need to use all the bamboos.

Sample Input 3

8 1000 800 100
300
333
400
444
500
555
600
666

Sample Output 3

243



Sample input:
5 100 90 80
98
40
30
21
80


Sample output:
23

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def main():
    n, a, b, c = map(int, input().split())
    l = [int(input()) for _ in range(n)]

    # full search
    ans = 10**9
    for perm in permutations(l):
        cost = -30
        for i in range(1, n-1):
            cost1 = cost + 10 * len(perm[:i]) + abs(a - sum(perm[:i]))
            for j in range(i+1, n):
                cost2 = cost1 + 10 * len(perm[i:j]) + abs(b - sum(perm[i:j]))
                for k in range(j+1, n+1):
                    cost3 = cost2 + 10 * len(perm[j:k]) + abs(c - sum(perm[j:k]))
                    if cost3 < ans:
                        ans = cost3
                        print(perm[:i], perm[i:j], perm[j:k])

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
n,a,b,c=map(int,input().split())
l=[int(input()) for _ in range(n)]
ans=10**18
for i in range(4**n):
  la,lb,lc,ca,cb,cc=0,0,0,0,0,0
  for j in range(n):
    if (i>>2*j)&1 and not (i>>2*j+1)&1:
      ca+=1
      la+=l[j]
    if not (i>>2*j)&1 and (i>>2*j+1)&1:
      cb+=1
      lb+=l[j]
    if (i>>2*j)&1 and (i>>2*j+1)&1:
      cc+=1
      lc+=l[j]
  if lc*lb*lc:ans=min((ca+cb+cc-3)*10+abs(la-a)+abs(lb-b)+abs(lc-c),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

class BIT():
    # A1 ... AnのBIT(1-indexed)
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    # A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    # Ai += x O(logN)
    def update(self, idx, x):
        # print(idx)
        while idx <= self.n:
            # print(idx)
            self.BIT[idx] += x
            idx += idx & (-idx)
        return

    def show(self):
        print(self.BIT)

def cost(id, div, x):
    n = len(div)
    use = []
    for i in range(n):
        if id % 2 == 1:
            use.append(div[i])
        id //= 2

    return (len(use) - 1) * 10 + abs(x - sum(use))


def eachtake(div, x):
    n = len(div)
    ret = INF

    for id in range(1, 1 << n):
        tmp = cost(id, div, x)
        ret = min(tmp, ret)

    return ret


def eachpat(pat, a, b, c, li, n):
    div = [[] for i in range(3)]
    for i in range(n):
        if pat % 4 != 3:
            div[pat%4].append(li[i])
        pat //= 4

    for i in range(3):
        if not div[i]:
            return INF

    ret = 0
    ret += eachtake(div[0], a)
    ret += eachtake(div[1], b)
    ret += eachtake(div[2], c)
    if ret == 110:
        print(div)
    return ret


def solve():
    n, a, b, c = getList()
    li = []
    for i in range(n):
        li.append(getN())

    ans = INF
    for pat in range(4 ** n):
        tmp = eachpat(pat, a, b, c, li, n)
        ans = min(ans, tmp)

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()
    # print(eachtake([333], 100))

Submission status: Wrong Answer

Solution code:
def li():
    return [int(x) for x in input().split()]
INF = 10**18
import itertools as it


N, A, B, C = li()
sl = [int(input()) for x in range(N)]
todo_stack = [sl]
candidate_lists = []
seen = []
minmp = INF
target = [A, B, C]
target.sort()
minl = []
while len(todo_stack) > 0:
    l = todo_stack.pop()
    if l in seen:
        continue
    seen.append(l)
    n = len(l)
    cs = it.combinations(l, 3)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if i==j or j==k or k==i:
                    continue
                bamboos = [l[i], l[j], l[k]]
                bamboos.sort()
                diff = abs(bamboos[0] - target[0]) + abs(bamboos[1] - target[1]) + abs(bamboos[2] - target[2])
                mp = (N - n) * 10 + diff
                if mp < minmp:
                    minmp = mp
                    minl = l
    if len(l) <= 3:
        continue
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            syn = l[i] + l[j]
            others = [l[k] for k in range(n) if (k != i and k != j)]
            newl = others + [syn]
            if len(newl) >= 3:
                todo_stack.append(newl)

print(minmp)
print(minl)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,A,B,C = inpl()
ppp = [A,B,C]
ba = [inp() for _ in range(n)]
res = INF
for pt in itertools.product(range(4), repeat=n):
    # print(pt)
    xxx = [0] * 3
    cnt = [0] * 3
    for i,x in enumerate(pt):
        if x == 0: continue
        xxx[x-1] += ba[i]
        cnt[x-1] += 1
    now = sum(abs(ppp[i] - xxx[i]) for i in range(3))
    now += 10*sum(0 if cnt[i]==0 else cnt[i]-1 for i in range(3))
    res = min(res, now)
print(res)

Submission status: Wrong Answer

Solution code:
#全探索をA,B,C一度で分けた
# TLE   ac 

# 初期入力
import heapq
from itertools import combinations
import sys
input = sys.stdin.readline  #文字列では使わない
N,A,B,C = (int(i) for i in input().split())
l =[0]*N
for i in range(N):
    l[i] = int(input())

# A,B,Cどの竹を選ぶかcombination
mp=[]
for na in range(1,N-1):
    for ja in combinations(l,na):

        l_b =list(set(l) -set(ja))
        for nb in range(1,N):
            for jb in combinations(l_b ,nb):

                l_c =list(set(l_b) -set(jb) )
                for nc in range(1,N+1):
                    for jc in combinations(l_c ,nc):
                        
                        # MPの消費量＝（求める長さー今回選んだ竹の長さ合計）+10*（合成魔法の回数)
                        AA =abs(A-sum(ja)) +10*(na-1)
                        BB =abs(B-sum(jb)) +10*(nb-1)
                        CC =abs(C-sum(jc)) +10*(nc-1)
                        mp.append(AA +BB +CC)

print(mp)

Submission status: Wrong Answer

Solution code:
# 初期入力
import heapq
from itertools import combinations
import sys
input = sys.stdin.readline  #文字列では使わない
N,A,B,C = (int(i) for i in input().split())
l =[0]*N
for i in range(N):
    l[i] = int(input())

# A,B,Cと元の竹の長さの差（絶対値）
dif_A =[]
dif_B =[]
dif_C =[]
for n in range(1,N+1):
    for j in combinations(l,n):
        #dif変数の要素＝（求める長さー今回選んだ竹の長さ合計）*10**（合成魔法の回数)＝MPの消費量、
        #               選んだ竹、
        #               A or B or C(heapqするとABCが混ざるので区別に必要)
        #if n >=2:
        dif_A.append((abs(A-sum(j)) +10*(n-1),j,"A") )
        dif_B.append((abs(B-sum(j)) +10*(n-1),j,"B") )
        dif_C.append((abs(C-sum(j)) +10*(n-1),j,"C") )

#heapq でMPの小さいものから取り出す
mp=0 #マジックポイント
confirm =set() #作成したいものを入れる(A,B,C)
used =set() #使用が確定した竹(l)
dif =dif_A +dif_B +dif_C
heapq.heapify(dif)
for i in range(len(dif_A) +len(dif_B) +len(dif_C)):
    x =heapq.heappop( dif)
    #print(x)
    if x[2] not in confirm:
        if set(x[1]).isdisjoint(used):
            confirm.add(x[2])
            used |= set(x[1])
            mp +=x[0]
        if confirm =={"A","B","C"}:
            break
print(mp)

Submission status: Wrong Answer

Solution code:
n,a,b,c=map(int,input().split())
l=[int(input())for i in range(n)]
def dfs(i,x,y,z):
 if i==n:return abs(a-x)+abs(b-y)+abs(c-z)-30if a+b+c>=3else 10**9+7
 A,B,C,D=dfs(i+1,x,y,z),dfs(i+1,x+l[i],y,z)+10,dfs(i+1,x,y+l[i],z)+10,dfs(i+1,x,y,z+l[i])+10
 return min(A,B,C,D)
print(dfs(0,0,0,0))

Submission status: Wrong Answer

Solution code:
from itertools import product, permutations

N, A, B, C = map(int, input().split(' '))
L = [int(input()) for _ in range(N)]

ans = 10 ** 9
for groups in product(range(4), repeat=N):
    items = []
    group_a = []
    group_b = []
    group_c = []

    for group, length in zip(groups, L):
        if group == 0:
            items.append((length, 0))
        elif group == 1:
            group_a.append(length)
        elif group == 2:
            group_b.append(length)
        elif group == 3:
            group_c.append(length)

    if len(items) < 3:
        continue

    if group_a:
        items.append((sum(group_a), (len(group_a) - 1) * 10))
    if group_b:
        items.append((sum(group_b), (len(group_b) - 1) * 10))
    if group_c:
        items.append((sum(group_c), (len(group_c) - 1) * 10))

    for one, two, three in permutations((A, B, C), r=3):
        cost = 0
        _items = list(items)

        _items = sorted(_items, key=lambda x: (abs(x[0] - one), x[1]))
        cost += abs(_items[0][0] - one) + _items[0][1]
        _items.pop(0)

        _items = sorted(_items, key=lambda x: (abs(x[0] - two), x[1]))
        cost += abs(_items[0][0] - two) + _items[0][1]
        _items.pop(0)

        _items = sorted(_items, key=lambda x: (abs(x[0] - three), x[1]))
        cost += abs(_items[0][0] - three) + _items[0][1]

        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product, permutations

N, A, B, C = map(int, input().split(' '))
L = [int(input()) for _ in range(N)]

ans = 10 ** 9
for groups in product(range(4), repeat=N):
    if len(set(groups)) + groups.count(0) - 1 < 3:
        continue

    items = []
    group_a = []
    group_b = []
    group_c = []

    for group, length in zip(groups, L):
        if group == 0:
            items.append((length, 0))
        elif group == 1:
            group_a.append(length)
        elif group == 2:
            group_b.append(length)
        elif group == 3:
            group_c.append(length)

    if group_a:
        items.append((sum(group_a), (len(group_a) - 1) * 10))
    if group_b:
        items.append((sum(group_b), (len(group_b) - 1) * 10))
    if group_c:
        items.append((sum(group_c), (len(group_c) - 1) * 10))

    for one, two, three in permutations((A, B, C), r=3):
        cost = 0
        _items = list(items)

        _items = sorted(_items, key=lambda x: (abs(x[0] - one), x[1]))
        cost += abs(_items[0][0] - one) + _items[0][1]
        _items.pop(0)

        _items = sorted(_items, key=lambda x: (abs(x[0] - two), x[1]))
        cost += abs(_items[0][0] - two) + _items[0][1]
        _items.pop(0)

        _items = sorted(_items, key=lambda x: (abs(x[0] - three), x[1]))
        cost += abs(_items[0][0] - three) + _items[0][1]

        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,A,B,C = I()
l = [i() for _ in range(N)]
def dfs(cur,a,b,c):
    if cur == N:
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c) > 0 else INF
        ret0 = dfs(cur+1,a,b,c)
        ret1 = dfs(cur+1,a+l[cur],b,c)+10
        ret2 = dfs(cur+1,a,b+l[cur],c)+10
        ret3 = dfs(cur+1,a,b,c+l[cur])+10
        return min(ret0,ret1,ret2,ret3)
print(dfs(0,0,0,0))

Submission status: Wrong Answer

Solution code:
N, A, B, C = map(int, input().split())
from itertools import product
l = [int(input()) for i in range(N)]
ans = []
for i in product(range(4), repeat=N):
  a = 0
  b = 0
  c = 0
  d = 0
  for j in range(N):
    if i[j]:
      d += 1
      if i[j] == 1:
        a += l[j]
      elif i[j] == 2:
        b += l[j]

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
import itertools

N, *A = mi()
L = [ii() for _ in range(N)]
L_ = [L[i] for i in range(N)]
N_ = N

A = sorted(A)
#sum_l = sum(L)
tmp = [0] * 3
ans = float('inf')

for k in itertools.product([0,1], repeat=N_):
    #print(k)
    N = sum(k)
    if N < 3:
        continue
    L = [L_[x]*k[x] for x in range(N_)]
    sum_l = sum(L)
    for i in range(1, N+1):
        #for koho_i in itertools.product([0, 1], repeat=N):
        for koho_i in range(1, 2**i):
            #for j in range(1, N-i):
                #for koho_j in itertools.product([0, 1], repeat=N):
            for koho_j in range(1, 2**i):
                j = i
                #print(koho_i, koho_j)
                if koho_i & koho_j:
                    continue
                #tmp[0] = [L[x]*koho_i[x] for x in range(i)]
                tmp[0] = sum([L[x]*min((koho_i & 1<<x), 1) for x in range(i)])
                #tmp[1] = [L[x]*koho_j[x] for x in range(j)]
                tmp[1] = sum([L[x]*min((koho_j & 1<<x), 1) for x in range(j)])
                tmp[2] = sum_l - tmp[0] - tmp[1]
                #print(tmp)

                if 0 in tmp:
                    continue

                tmp = sorted(tmp)
                cost = (N-3) * 10 + sum([abs(tmp[x]-A[x]) for x in range(3)])
                #if cost < ans:
                    #print(tmp, cost, N)
                #if tmp[0] == 80 and tmp[1] == 91 and tmp[2] == 98:
                    #print(cost)
                ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:

from itertools import combinations
from copy import deepcopy

def parse():
  N, A, B, C = map(int, input().split(" "))
  L = []
  for n in range(N):
    L.append(int(input()))
  return N, [A, B, C], L

def main():
  N, A, L = parse()
  # print(N, A, B, C, L)

  # 門松セットの初期化
  kadomatsu_set_list = []
  kadomatsu_set = []
  cost_zero = [0, 0, 0]
  for l in L:
    for i, a in enumerate(A):
      if a == l: cost_zero[i] = 1
    kadomatsu_set.append(l)
    # kadomatsu_set.append((l, 0))
    # kadomatsu_set.append(Kadomatsu(l, 0))
  kadomatsu_set_list.append((kadomatsu_set, 0))
  # kadomatsu_set_list.append(kadomatsu_set)
  # print(kadomatsu_set_list)

  # 初期状態でコスト0の組み合わせがある場合
  if sum(cost_zero) == 3:
    print(0)
    exit(0)

  # kadomatsu_set_list > 3の時，合成可能なので，
  # 合成可能な場合，合成を繰り返す
  i = 0
  while len(kadomatsu_set_list[i][0]) > 3:
  # while len(kadomatsu_set_list[i]) > 3:
    for combination in combinations(kadomatsu_set_list[i][0], 2):
    # for combination in combinations(kadomatsu_set_list[i], 2):
      # print("combination:", combination)
      new_kadomastu = combination[0] + combination[1]
      # new_kadomastu = (combination[0][0] + combination[1][0], 
      #   combination[0][1] + combination[1][1] + 10)
      
      # new_kadomastu_setの初期化
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i][0]]
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i]]
      # new_kadomastu_set.remove(combination[0])
      # new_kadomastu_set.remove(combination[1])
      
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i]
      #   if (not kadomatsu is combination[0]) and (not kadomatsu is combination[1])]
      
      new_kadomastu_set = []
      # new_kadomastu_set = [combination[0] + combination[1]]
      continued0 = False
      continued1 = False
      for kadomatsu in kadomatsu_set_list[i][0]:
        # if kadomatsu == combination[0] or kadomatsu == combination[1]: continue
        if not continued0 and kadomatsu == combination[0]:
          continued0 = True
          continue
        if not continued1 and kadomatsu == combination[1]:
          continued1 = True
          continue
        new_kadomastu_set.append(kadomatsu)
      new_kadomastu_set.append(new_kadomastu)
      # print("new_kadomastu_set:", new_kadomastu_set)
      # input()

      kadomatsu_set_list.append((new_kadomastu_set, kadomatsu_set_list[i][1] + 10))
      # kadomatsu_set_list.append(new_kadomastu_set)

    i += 1
  
  # print(len(kadomatsu_set_list))
  min_cost = 10 ** 20
  for kadomatsu_set, set_cost in kadomatsu_set_list:
  # for kadomatsu_set in kadomatsu_set_list:
    do_skip = False
    # print(kadomatsu_set)

    cost = set_cost
    # cost = 0
    # used_kadomatsu = {}
    for a in A:
      min_diff = 10 ** 10
      min_diff_i = 0
      for i, kadomatsu in enumerate(kadomatsu_set):
        # if i in used_kadomatsu: continue
        diff = abs(a - kadomatsu)
        # diff = abs(a - kadomatsu[0])
        if min_diff > diff:
          min_diff = diff
          min_diff_i = i
      cost += min_diff
      # cost += min_diff + kadomatsu_set[min_diff_i][1]
      if cost > min_cost: # 現時点で最小コストより高い場合はこれ以上探索しない
        # do_skip = True
        break
      # used_kadomatsu[min_diff_i] = None
      kadomatsu_set.remove(kadomatsu_set[min_diff_i])

    # if do_skip: continue

    # # Aに最も長さが近い門松を探す
    # min_diff_A = 10 ** 10
    # min_diff_A_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   diff = abs(A - kadomatsu[0])
    #   if min_diff_A > diff:
    #     min_diff_A = diff
    #     min_diff_A_i = i

    # # Bに最も長さが近い門松を探す
    # min_diff_B = 10 ** 10
    # min_diff_B_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   if i == min_diff_A_i: continue  # Aですでに選んでいる門松はスキップ
    #   diff = abs(B - kadomatsu[0])
    #   if min_diff_B > diff:
    #     min_diff_B = diff
    #     min_diff_B_i = i
    
    # # Cに最も長さが近い門松を探す
    # min_diff_C = 10 ** 10
    # min_diff_C_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   if i == min_diff_A_i: continue  # Aですでに選んでいる門松はスキップ
    #   if i == min_diff_B_i: continue  # Bですでに選んでいる門松はスキップ
    #   diff = abs(C - kadomatsu[0])
    #   if min_diff_C > diff:
    #     min_diff_C = diff
    #     min_diff_C_i = i
    
    # cost = min_diff_A + min_diff_B + min_diff_C \
      # + kadomatsu_set[min_diff_A_i][1] + kadomatsu_set[min_diff_B_i][1] + kadomatsu_set[min_diff_C_i][1]
      # + kadomatsu_set[min_diff_A_i].cost + kadomatsu_set[min_diff_B_i].cost + kadomatsu_set[min_diff_C_i].cost
    if min_cost > cost: min_cost = cost
    if min_cost == 0: # コスト0の時点で最小値のため即終了
      print(0)
      exit(0)
    # print(min_diff_A_i, min_diff_B_i, min_diff_C_i, cost)
    # input()
  print(min_cost)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:

from itertools import combinations
from copy import deepcopy

def parse():
  N, A, B, C = map(int, input().split(" "))
  L = []
  for n in range(N):
    L.append(int(input()))
  return N, [A, B, C], L

def main():
  N, A, L = parse()
  # print(N, A, B, C, L)

  # 門松セットの初期化
  kadomatsu_set_list = []
  kadomatsu_set = []
  cost_zero = [0, 0, 0]
  for l in L:
    for i, a in enumerate(A):
      if a == l: cost_zero[i] = 1
    kadomatsu_set.append(l)
    # kadomatsu_set.append((l, 0))
    # kadomatsu_set.append(Kadomatsu(l, 0))
  kadomatsu_set_list.append((kadomatsu_set, 0))
  # kadomatsu_set_list.append(kadomatsu_set)
  # print(kadomatsu_set_list)

  # 初期状態でコスト0の組み合わせがある場合
  if sum(cost_zero) == 3:
    print(0)
    exit(0)

  # kadomatsu_set_list > 3の時，合成可能なので，
  # 合成可能な場合，合成を繰り返す
  i = 0
  while len(kadomatsu_set_list[i][0]) > 3:
  # while len(kadomatsu_set_list[i]) > 3:
    for combination in combinations(kadomatsu_set_list[i][0], 2):
    # for combination in combinations(kadomatsu_set_list[i], 2):
      # print("combination:", combination)
      # new_kadomastu = combination[0] + combination[1]
      # new_kadomastu = (combination[0][0] + combination[1][0], 
      #   combination[0][1] + combination[1][1] + 10)
      
      # new_kadomastu_setの初期化
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i][0]]
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i]]
      # new_kadomastu_set.remove(combination[0])
      # new_kadomastu_set.remove(combination[1])
      
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i]
      #   if (not kadomatsu is combination[0]) and (not kadomatsu is combination[1])]
      
      new_kadomastu_set = [combination[0] + combination[1]]
      continued0 = False
      continued1 = False
      for kadomatsu in kadomatsu_set_list[i][0]:
        # if kadomatsu == combination[0] or kadomatsu == combination[1]: continue
        if not continued0 and kadomatsu == combination[0]:
          continued0 = True
          continue
        if not continued1 and kadomatsu == combination[1]:
          continued1 = True
          continue
        new_kadomastu_set.append(kadomatsu)
      # new_kadomastu_set.append(new_kadomastu)
      # print("new_kadomastu_set:", new_kadomastu_set)
      # input()

      kadomatsu_set_list.append((new_kadomastu_set, kadomatsu_set_list[i][1] + 10))
      # kadomatsu_set_list.append(new_kadomastu_set)

    i += 1
  
  # print(len(kadomatsu_set_list))
  min_cost = 10 ** 20
  for kadomatsu_set, set_cost in kadomatsu_set_list:
  # for kadomatsu_set in kadomatsu_set_list:
    do_skip = False
    # print(kadomatsu_set)

    cost = set_cost
    # cost = 0
    used_kadomatsu = {}
    for a in A:
      min_diff = 10 ** 10
      min_diff_i = 0
      for i, kadomatsu in enumerate(kadomatsu_set):
        # if i in used_kadomatsu: continue
        diff = abs(a - kadomatsu)
        # diff = abs(a - kadomatsu[0])
        if min_diff > diff:
          min_diff = diff
          min_diff_i = i
      cost += min_diff
      # cost += min_diff + kadomatsu_set[min_diff_i][1]
      if cost > min_cost: # 現時点で最小コストより高い場合はこれ以上探索しない
        # do_skip = True
        break
      # used_kadomatsu[min_diff_i] = None
      kadomatsu_set.remove(kadomatsu_set[min_diff_i])

    # if do_skip: continue

    # # Aに最も長さが近い門松を探す
    # min_diff_A = 10 ** 10
    # min_diff_A_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   diff = abs(A - kadomatsu[0])
    #   if min_diff_A > diff:
    #     min_diff_A = diff
    #     min_diff_A_i = i

    # # Bに最も長さが近い門松を探す
    # min_diff_B = 10 ** 10
    # min_diff_B_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   if i == min_diff_A_i: continue  # Aですでに選んでいる門松はスキップ
    #   diff = abs(B - kadomatsu[0])
    #   if min_diff_B > diff:
    #     min_diff_B = diff
    #     min_diff_B_i = i
    
    # # Cに最も長さが近い門松を探す
    # min_diff_C = 10 ** 10
    # min_diff_C_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   if i == min_diff_A_i: continue  # Aですでに選んでいる門松はスキップ
    #   if i == min_diff_B_i: continue  # Bですでに選んでいる門松はスキップ
    #   diff = abs(C - kadomatsu[0])
    #   if min_diff_C > diff:
    #     min_diff_C = diff
    #     min_diff_C_i = i
    
    # cost = min_diff_A + min_diff_B + min_diff_C \
      # + kadomatsu_set[min_diff_A_i][1] + kadomatsu_set[min_diff_B_i][1] + kadomatsu_set[min_diff_C_i][1]
      # + kadomatsu_set[min_diff_A_i].cost + kadomatsu_set[min_diff_B_i].cost + kadomatsu_set[min_diff_C_i].cost
    if min_cost > cost: min_cost = cost
    if min_cost == 0: # コスト0の時点で最小値のため即終了
      print(0)
      exit(0)
    # print(min_diff_A_i, min_diff_B_i, min_diff_C_i, cost)
    # input()
  print(min_cost)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:

from itertools import combinations
from copy import deepcopy

def parse():
  N, A, B, C = map(int, input().split(" "))
  L = []
  for n in range(N):
    L.append(int(input()))
  return N, [A, B, C], L

def main():
  N, A, L = parse()
  # print(N, A, B, C, L)

  # 門松セットの初期化
  kadomatsu_set_list = []
  kadomatsu_set = []
  cost_zero = [0, 0, 0]
  for l in L:
    for i, a in enumerate(A):
      if a == l: cost_zero[i] = 1
    kadomatsu_set.append(l)
    # kadomatsu_set.append((l, 0))
    # kadomatsu_set.append(Kadomatsu(l, 0))
  kadomatsu_set_list.append((kadomatsu_set, 0))
  # kadomatsu_set_list.append(kadomatsu_set)
  # print(kadomatsu_set_list)

  # 初期状態でコスト0の組み合わせがある場合
  if sum(cost_zero) == 3:
    print(0)
    exit(0)

  # kadomatsu_set_list > 3の時，合成可能なので，
  # 合成可能な場合，合成を繰り返す
  i = 0
  while len(kadomatsu_set_list[i][0]) > 3:
  # while len(kadomatsu_set_list[i]) > 3:
    for combination in combinations(kadomatsu_set_list[i][0], 2):
    # for combination in combinations(kadomatsu_set_list[i], 2):
      # print("combination:", combination)
      new_kadomastu = combination[0] + combination[1]
      # new_kadomastu = (combination[0][0] + combination[1][0], 
      #   combination[0][1] + combination[1][1] + 10)
      
      # new_kadomastu_setの初期化
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i][0]]
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i]]
      # new_kadomastu_set.remove(combination[0])
      # new_kadomastu_set.remove(combination[1])
      
      # new_kadomastu_set = [kadomatsu for kadomatsu in kadomatsu_set_list[i]
      #   if (not kadomatsu is combination[0]) and (not kadomatsu is combination[1])]
      
      new_kadomastu_set = [new_kadomastu]
      continued0 = False
      continued1 = False
      for kadomatsu in kadomatsu_set_list[i][0]:
        # if kadomatsu == combination[0] or kadomatsu == combination[1]: continue
        if not continued0 and kadomatsu == combination[0]:
          continued0 = True
          continue
        if not continued1 and kadomatsu == combination[1]:
          continued1 = True
          continue
        new_kadomastu_set.append(kadomatsu)
      # new_kadomastu_set.append(new_kadomastu)
      # print("new_kadomastu_set:", new_kadomastu_set)
      # input()

      kadomatsu_set_list.append((new_kadomastu_set, kadomatsu_set_list[i][1] + 10))
      # kadomatsu_set_list.append(new_kadomastu_set)

    i += 1
  
  # print(len(kadomatsu_set_list))
  min_cost = 10 ** 20
  for kadomatsu_set, set_cost in kadomatsu_set_list:
  # for kadomatsu_set in kadomatsu_set_list:
    do_skip = False
    # print(kadomatsu_set)

    cost = set_cost
    # cost = 0
    used_kadomatsu = {}
    for a in A:
      min_diff = 10 ** 10
      min_diff_i = 0
      for i, kadomatsu in enumerate(kadomatsu_set):
        if i in used_kadomatsu: continue
        diff = abs(a - kadomatsu)
        # diff = abs(a - kadomatsu[0])
        if min_diff > diff:
          min_diff = diff
          min_diff_i = i
      cost += min_diff
      # cost += min_diff + kadomatsu_set[min_diff_i][1]
      if cost > min_cost: # 現時点で最小コストより高い場合はこれ以上探索しない
        # do_skip = True
        break
      used_kadomatsu[min_diff_i] = None
      # kadomatsu_set.remove(kadomatsu_set[min_diff_i])

    # if do_skip: continue

    # # Aに最も長さが近い門松を探す
    # min_diff_A = 10 ** 10
    # min_diff_A_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   diff = abs(A - kadomatsu[0])
    #   if min_diff_A > diff:
    #     min_diff_A = diff
    #     min_diff_A_i = i

    # # Bに最も長さが近い門松を探す
    # min_diff_B = 10 ** 10
    # min_diff_B_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   if i == min_diff_A_i: continue  # Aですでに選んでいる門松はスキップ
    #   diff = abs(B - kadomatsu[0])
    #   if min_diff_B > diff:
    #     min_diff_B = diff
    #     min_diff_B_i = i
    
    # # Cに最も長さが近い門松を探す
    # min_diff_C = 10 ** 10
    # min_diff_C_i = 0
    # for i, kadomatsu in enumerate(kadomatsu_set):
    #   if i == min_diff_A_i: continue  # Aですでに選んでいる門松はスキップ
    #   if i == min_diff_B_i: continue  # Bですでに選んでいる門松はスキップ
    #   diff = abs(C - kadomatsu[0])
    #   if min_diff_C > diff:
    #     min_diff_C = diff
    #     min_diff_C_i = i
    
    # cost = min_diff_A + min_diff_B + min_diff_C \
      # + kadomatsu_set[min_diff_A_i][1] + kadomatsu_set[min_diff_B_i][1] + kadomatsu_set[min_diff_C_i][1]
      # + kadomatsu_set[min_diff_A_i].cost + kadomatsu_set[min_diff_B_i].cost + kadomatsu_set[min_diff_C_i].cost
    if min_cost > cost: min_cost = cost
    if min_cost == 0: # コスト0の時点で最小値のため即終了
      print(0)
      exit(0)
    # print(min_diff_A_i, min_diff_B_i, min_diff_C_i, cost)
    # input()
  print(min_cost)


if __name__ == "__main__":
  main()