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:
import itertools

def main():
    N, A, B, C = list(map(int, input().split()))
    bars = [A,B,C]
    l = []
    for i in range(N):
        l.append(int(input()))
        if l[-1] in bars:
            j = bars.index(l[-1])
            del bars[j]
            del l[-1]

    # print(bars, l)
    ret = 0

    for k in range(len(bars)):
        full = []
        for i in range(1, N-len(bars[k:])+1):
            full += list(itertools.combinations(l, i))
        # print(full)


        mini = 1000000000
        arg_min = []
        for i in full:
            if abs(sum(i)-bars[k]) < mini:
                mini = abs(sum(i)-bars[k])
                arg_min = i
        
        # print(mini, arg_min)
        ret += 10*(len(arg_min)-1) if len(arg_min)!=0 else 0
        ret += mini
        for i in arg_min:
            del l[l.index(i)]
    print(ret) 

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]
def bintoset(b):
    ret = set()
    for i in range(N):
        if b & 1 == 1:
            ret.add(l[i])
        b = b >> 1
    return ret
def cost(b, x):
    s = bintoset(b)
    return abs(x - sum(s)) + (len(s) - 1) * 10
mincost = 10000000
for a in range(1, 1 << N):
    for b in range(1, (1 << N) - a):
        if b & a == 0:
            for c in range(1, (1 << N) - a - b):
                if c & (a+b) == 0 and a * b * c != 0:
                    mincost = min(mincost, cost(a, A) + cost(b, B) + cost(c, C))
print(mincost)

Submission status: Wrong Answer

Solution code:
import numpy as np
print(np.nan)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

def ns(X, n):
    if (int(X/n)):
        return ns(int(X/n), n)+str(X%n)
    return str(X%n)

n,a,b,c=map(int,input().split())
t=[a,b,c]
l=[]
ans=-1
for i in range(n):
    l.append(int(input()))

for i in range(4**n):
    tmp=ns(i,4)+"0"*8
    h=[0]*3
    p=0
    for j in range(len(l)):
        if tmp[j]=="1":
            if h[0]!=0: p+=10
            h[0]+=l[j]
        elif tmp[j]=="2":
            if h[1]!=0: p+=10
            h[1]+=l[j]
        elif tmp[j]=="3":
            if h[2]!=0: p+=10
            h[2]+=l[j]
    if 0 in h:continue
    for k in range(3):
        p+=abs(h[k]-t[k])
    if ans==-1: ans=p
    else: ans=min(ans,p)
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(wants, remains):
    if len(wants) == 0:
        return 0

    min_cost = float("inf")
    if len(wants) < len(remains):  # 合成
        for i in range(1, len(remains)):
            min_cost = min(min_cost, 10+dfs(wants, [remains[0] + remains[i]] + remains[1:i] + remains[i+1:] ))

    for i in range(len(wants)): # 延長
        min_cost = min(min_cost, abs(wants[i]-remains[0]) + dfs(wants[:i] + wants[i+1:], remains[1:]))
    return min_cost

N, A, B, C = map(int, input().split())
ls = []
for _ in range(N):
    ls.append(int(input()))

wants = [A, B, C]
print(dfs(wants, ls))

Submission status: Wrong Answer

Solution code:
def dfs(wants, remains):
    if len(wants) == 0:
        return 0
    for w in wants:
        if w in remains:
            new_wants = wants[:]
            new_wants.remove(w)
            new_remains = remains[:]
            new_remains.remove(w)
            return dfs(new_wants, new_remains)

    min_cost = float("inf")
    if len(wants) < len(remains):  # 合成
        for i in range(1, len(remains)):
            min_cost = min(min_cost, 10+dfs(wants, [remains[0] + remains[i]] + remains[1:i] + remains[i+1:] ))

    for i in range(len(wants)): # 延長
        min_cost = min(min_cost, abs(wants[i]-remains[0]) + dfs(wants[:i] + wants[i+1:], remains[1:]))
    return min_cost

N, A, B, C = map(int, input().split())
ls = []
for _ in range(N):
    ls.append(int(input()))

wants = [A, B, C]
print(dfs(wants, ls))

Submission status: Wrong Answer

Solution code:
import itertools

def calc(t, l):
	ti = 0
	min_mp = 0
	while ti < 3:
		mp = float('inf')
		op = None
		for i in range(len(l)):
			if l[i] == t[ti]:
				l.pop(i)
				ti += 1
				break
			if 0 < t[ti] - l[i] < mp:
				mp = t[ti] - l[i]
				op = ('a', i)
			if 0 < l[i] - t[ti] < mp:
				mp = l[i] - t[ti]
				op = ('d', i)
			if len(l) > 3 - ti:
				for j in range(i + 1, len(l)):
					if abs(t[ti] - l[i] - l[j]) + 10 < mp:
						mp = abs(t[ti] - l[i] - l[j]) + 10
						op = ('m', i, j)
		else:
			if op[0] == 'a':
				l[op[1]] += 1
				min_mp += 1
			elif op[0] == 'd':
				l[op[1]] -= 1
				min_mp += 1
			else:
				l[op[1]] += l[op[2]]
				l.pop(op[2])
				min_mp += 10
	return min_mp


N, A, B, C = [int(v) for v in input().split()]
l = [int(input()) for _ in range(N)]
l.sort(reverse=True)
t = (A, B, C)
min_mp = float('inf')
for tp in itertools.permutations(t):
	min_mp = min(min_mp, calc(tp, l[:]))
print(min_mp)

Submission status: Wrong Answer

Solution code:
N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]
# l wo a,b,c ni furiwakete zentansaku
def bintoset(b):
    ret = set()
    for i in range(N):
        if b & 1 == 1:
            ret.add(l[i])
        b = b >> 1
    return ret
mincost = 100000000000
for a in range(1, 1 << N):
    rest = (1 << N)  - a
    for b in range(1, rest):
        if b & a == 0:
            for c in range(1, rest - b):
                if c & (a+b) == 0:
                    aset = bintoset(a)
                    bset = bintoset(b)
                    cset = bintoset(c)
                    acost = abs(A - sum(aset)) + (len(aset) - 1) * 10
                    bcost = abs(B - sum(bset)) + (len(bset) - 1) * 10
                    ccost = abs(C - sum(cset)) + (len(cset) - 1) * 10
                    mincost = min(mincost, acost + bcost + ccost)
#                    print(acost, aset, bin(a))
#                    print(bcost, bset, bin(b))
#                    print(ccost, cset, bin(c))
#                    print()
print(mincost)

Submission status: Wrong Answer

Solution code:
import copy

n, a, b, c = list(map(int, input().split(" ")))
l = n*[0]
for i in range(n):
    l[i] = int(input())



def search(abc, l):
    mp = 0
    for x in abc:
        if(x in l): l[l.index(x)] = 0
        else:
            while(True):
                k = 1e9
                d = -1
                for i in range(n):
                    if(l[i] == 0): continue

                    if(abs(x - l[i]) < k):
                        k = abs(x - l[i])
                        d = i

                if(k <= 10):
                    mp += k
                    l[d] = 0
                    break
                else:
                    tmp2 = [k, d]
                    k = 1e9
                    d = -1
                    for i in range(n):
                        if(l[i] == 0): continue
                        for j in range(i+1, n, 1):
                            if(l[j] == 0): continue

                            if(abs(x - (l[i]+l[j])) < k and abs(x - (l[i]+l[j])) < abs(x - l[i]) and abs(x - (l[i]+l[j])) < abs(x - l[j])):
                                k = abs(x - (l[i]+l[j]))
                                d = [i, j]

                    if(k != 1e9):
                        l[d[0]] += l[d[1]]
                        l[d[1]] = 0
                        mp += 10
                    else:
                        mp += tmp2[0]
                        l[tmp2[1]] = 0
                        break

    return mp

ans = []
ans.append(search([a, b, c], copy.deepcopy(l)))
ans.append(search([a, c, b], copy.deepcopy(l)))
ans.append(search([b, a, c], copy.deepcopy(l)))
ans.append(search([b, c, a], copy.deepcopy(l)))
ans.append(search([c, a, b], copy.deepcopy(l)))
ans.append(search([c, b, a], copy.deepcopy(l)))


print(min(ans))

Submission status: Wrong Answer

Solution code:
N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]
# l wo a,b,c ni furiwakete zentansaku
def bintoset(b):
    ret = set()
    for i in range(N):
        if b & 1 == 1:
            ret.add(l[i])
        b = b >> 1
    return ret
mincost = 100000000000
for a in range(1, 1 << N):
    rest = ((1 << N) - 1)  - a
    for b in range(1, rest):
        if b & a == 0:
            for c in range(1, rest - b + 1):
                if c & (a+b) == 0:
                    aset = bintoset(a)
                    bset = bintoset(b)
                    cset = bintoset(c)
                    acost = abs(A - sum(aset)) + (len(aset) - 1) * 10
                    bcost = abs(B - sum(bset)) + (len(bset) - 1) * 10
                    ccost = abs(C - sum(cset)) + (len(cset) - 1) * 10
                    mincost = min(mincost, acost + bcost + ccost)
#                    print(acost, aset, bin(a))
#                    print(bcost, bset, bin(b))
#                    print(ccost, cset, bin(c))
#                    print()
print(mincost)

Submission status: Wrong Answer

Solution code:
import collections
N,A,B,C = map(int, input().split(" "))

L = [int(input()) for i in range(N)]

def solve():
  if A in L and B in L and C in L:
    print(0)
    return
  if(len(L) == 3):
    print(sum(L)-sum([A,B,C]))
  
solve()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import itertools

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, a, b, c = LI()
A = [a, b, c]
K = [II() for _ in range(n)]

ans = INF
for x in itertools.product([0, 1, 2, 3], repeat=n):
    s = set(x)
    if 0 not in s or 1 not in s or 2 not in s:
        continue
    T = [0] * 3
    cnt = 0
    for i, n in enumerate(x):
        if n == 3:
            continue
        if T[n]:
            cnt += 1
        T[n] += K[i]

    # print(T, cnt)
    tmp = cnt * 10
    for i in range(3):
        tmp += abs(T[i] - A[i])
    if tmp == 120:
        print(x)
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
def base4(x):
    if int(x/4):
        return base4(int(x/4)) + str(x%4)
    return str(x%4)

N,A,B,C = list(map(int,input().split()))
l = []
for n in range(N):
    l.append(int(input()))

res = 99999999
for i in range(4**N):
    c = [[0,0,0],[-1,-1,-1]]
    for j,b in enumerate(base4(i)):
        if b == '1':
            c[0][0] += l[j]
            c[1][0] += 1
        elif b == '2':
            c[0][1] += l[j]
            c[1][1] += 1
        elif b == '3':
            c[0][2] += l[j]
            c[1][2] += 1
    if c[1][0] >= 0 and c[1][1] >= 0 and c[1][2] >= 0:
        res = min(res,abs(c[0][0]-A)+abs(c[0][1]-B)+abs(c[0][2]-C)+sum(c[1])*10)

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

def calc(t, l):
	ti = 0
	min_mp = 0
	while ti < 3:
		mp = float('inf')
		op = None
		for i in range(len(l)):
			if l[i] == t[ti]:
				l.pop(i)
				ti += 1
				break
			if 0 < t[ti] - l[i] < mp:
				mp = t[ti] - l[i]
				op = ('a', i)
			if 0 < l[i] - t[ti] < mp:
				mp = l[i] - t[ti]
				op = ('d', i)
			if len(l) > 3 - ti:
				for j in range(i + 1, len(l)):
					if abs(t[ti] - l[i] - l[j]) + 10 < mp:
						mp = abs(t[ti] - l[i] - l[j]) + 10
						op = ('m', i, j)
		else:
			if op[0] == 'a':
				l[op[1]] += 1
				min_mp += 1
			elif op[0] == 'd':
				l[op[1]] -= 1
				min_mp += 1
			else:
				l[op[1]] += l[op[2]]
				l.pop(op[2])
				min_mp += 10
	return min_mp


N, A, B, C = [int(v) for v in input().split()]
l = [int(input()) for _ in range(N)]
t = (A, B, C)
min_mp = float('inf')
for tp in itertools.permutations(t):
	min_mp = min(min_mp, calc(tp, l[:]))
print(min_mp)

Submission status: Wrong Answer

Solution code:
N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]
# l wo a,b,c ni furiwakete zentansaku
def bintoset(b):
    ret = set()
    for i in range(N):
        if b & 1 == 1:
            ret.add(l[i])
        b = b >> 1
    return ret
mincost = 10000000
for a in range(1, 1 << N):
    rest = ((1 << N) - 1)  - a
    for b in range(1, rest):
        if b & a == 0:
            for c in range(1, rest - b + 1):
                if c & (a+b) == 0:
                    aset = bintoset(a)
                    bset = bintoset(b)
                    cset = bintoset(c)
                    acost = abs(A - sum(aset)) + (len(aset) - 1) * 10
                    bcost = abs(B - sum(bset)) + (len(bset) - 1) * 10
                    ccost = abs(C - sum(cset)) + (len(cset) - 1) * 10
                    mincost = min(mincost, acost + bcost + ccost)
#                    print(acost, aset, bin(a))
#                    print(bcost, bset, bin(b))
#                    print(ccost, cset, bin(c))
#                    print()
print(mincost)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit; setrecursionlimit(10**9)
N, A, B, C = map(int, input().split())
L = []
for _ in range(N):
    L.append(int(input()))

def argmin(array):
    return min(enumerate(array), key=lambda x:x[1])

def change_len(L):
    cons = 0
    R = list(map(lambda x: abs(x-A), L))
    cons += min(R)
    L.pop(argmin(R)[0])
    S = list(map(lambda x: abs(x-B), L))
    cons += min(S)
    L.pop(argmin(S)[0])
    T = list(map(lambda x: abs(x-C), L))
    cons += min(T)
    L.pop(argmin(T)[0])
    return cons

def rec(i, a, b, c, comb, cons):
    if i == N:
        if 0 not in [a, b, c]:
            comb.append([a, b, c, cons])
        return None

    # if n < 3:
    #     return
    v = 0 if a == 0 else 10
    rec(i+1, a+L[i], b, c, comb, cons+v)
    v = 0 if b == 0 else 10
    rec(i+1, a, b+L[i], c, comb, cons+v)
    v = 0 if c == 0 else 10
    rec(i+1, a, b, c+L[i], comb, cons+v)
    rec(i+1, a, b, c, comb, cons)
    return comb

comb = rec(0, 0, 0, 0, [], 0)
minval = 1000000
for c in comb:
    minval = min(minval, change_len(c[:3]) + c[3])
print(minval)

Submission status: Wrong Answer

Solution code:
N,A,B,C = map(int,input().split())
l =[]
MP = 0

for i in range(N):
    l.append(int(input()))
l.sort()
l = list(set(l))

if A in l:
    l.remove(A)
if B in l:
    l.remove(B)
if C in l:
    l.remove(C)

if not l:
    print(0)

Submission status: Wrong Answer

Solution code:
import os
import math
from itertools import permutations
import functools as func
INF, MOD = float("inf"), 1e9 + 7
MAX, MIN = -INF, INF
dx1, dy1, dx2, dy2 = [-1, 0, 1, 0], [0, -1, 0, 1], [-1, 0, 1, -1, 1, -1, 0, 1], [-1, -1, -1, 0, 0, 1, 1, 1]

def get_int():
    return int(input())

def get_int_list():
    return list(map(int, input().split()))

while(True):
    try:
        n, a, b, c = get_int_list()
        l = [get_int() for _ in range(n)]
        ans = 1000000000000
        for take in permutations(l, n):
            take = list(take)
            cnt = 0
            i = 3
            while abs(take[0] - a) > 10 and take[0] < a:
                if i >= n:
                    break
                take[0] += take[i]
                i += 1
                cnt += 10
            cnt += abs(take[0] - a)

            while abs(take[1] - b) > 10 and take[1] < b:
                if i >= n:
                    break
                take[1] += take[i]
                i += 1
                cnt += 10
            cnt += abs(take[1] - b)

            while abs(take[2] - c) > 10 and take[2] < c:
                if i >= n:
                    break
                take[2] += take[i]
                i += 1
                cnt += 10
            cnt += abs(take[2] - c)

            ans = min(ans, cnt)
        print(ans)
    except EOFError:
        exit()

Submission status: Wrong Answer

Solution code:
N, A, B, C = map(int, input().split())

ABC = [A, B, C]

l = [int(input()) for i in range(N)]

abc = [0 for i in range(N)]

ans = 1 << 30

def cost():
    take = [0 for i in range(3)]

    tmp = 0

    for i in range(N):
        if abc[i] == 0:
            continue
        take[abc[i]-1] += l[i]
        tmp += 1

    tmp = (tmp - 3) * 10

    for i in range(3):
        tmp += abs(ABC[i] - take[i])

    return tmp


def dfs(i):
    global ans
    if i == N:
        ans = min(ans, cost())
        return
    for j in range(4):
        abc[i] = j
        dfs(i+1)

dfs(0)
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import math
from itertools import permutations
import functools as func
INF, MOD = float("inf"), 1e9 + 7
MAX, MIN = -INF, INF
dx1, dy1, dx2, dy2 = [-1, 0, 1, 0], [0, -1, 0, 1], [-1, 0, 1, -1, 1, -1, 0, 1], [-1, -1, -1, 0, 0, 1, 1, 1]

def get_int():
    return int(input())

def get_int_list():
    return list(map(int, input().split()))

while(True):
    try:
        n, a, b, c = get_int_list()
        l = [get_int() for _ in range(n)]
        ans = 1000000000000
        for take in permutations(l, n):
            take = list(take)
            cnt = 0
            i = 3
            while abs(take[0] - a) > 10:
                if i >= n:
                    break
                take[0] += take[i]
                i += 1
                cnt += 10
            cnt += abs(take[0] - a)

            while abs(take[1] - b) > 10:
                if i >= n:
                    break
                take[1] += take[i]
                i += 1
                cnt += 10
            cnt += abs(take[1] - b)

            while abs(take[2] - c) > 10:
                if i >= n:
                    break
                take[2] += take[i]
                i += 1
                cnt += 10
            cnt += abs(take[2] - c)

            ans = min(ans, cnt)
        print(ans)
    except EOFError:
        exit()

Submission status: Wrong Answer

Solution code:
n,a,b,c=map(int,input().split())
z=[int(input()) for i in range(n)]
abc=[a,b,c]
i=0
for k in [a,b,c]:
  if k in z:
    abc.remove(k)
    z.remove(k)
    i+=1
if i==3:
  print(0)
else:
  print(10)

Submission status: Wrong Answer

Solution code:
N, A, B, C = [int(_) for _ in input().split()]
L = [int(input()) for i in range(N)]

from itertools import combinations

L = set(L)

def combi(xs, left):
    for i in range(len(xs) - left):
        for r in combinations(xs, i + 1):
            yield r

def calc(xs):
    result = 10**100
    for ra in combi(xs, 2):
        sa = abs(A - sum(ra)) + len(ra) * 10 - 10
        xsa = xs - set(ra)
        for rb in combi(xsa, 1):
            sb = abs(B - sum(rb)) + len(rb) * 10 - 10
            xsb = xsa - set(rb)
            for rc in combi(xsb, 0):
                sc = abs(C - sum(rc)) + len(rc) * 10 - 10
                total = sa + sb + sc
                result = min(result, total)
    return result

print(calc(L))

Submission status: Time Limit Exceeded

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)

Submission status: Time Limit Exceeded

Solution code:
#A,B,Cを決めた後、heapqをやめて全探索、たぶんTLE

# 初期入力
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") )

#
mp =[]
for i in dif_A: 
    for j in dif_B:
        for k in dif_C:
            if set(i[1]).isdisjoint(set(j[1])) and \
                set(i[1]).isdisjoint(set(k[1])) and \
                set(j[1]).isdisjoint(set(k[1])):
                mp.append(i[0] +j[0] +k[0])
#mp.sort()

print(min(mp))

Submission status: Time Limit Exceeded

Solution code:

from itertools import combinations
from copy import deepcopy

# class Kadomatsu:
#   def __init__(self, length, cost):
#     self.length = length
#     self.cost = cost
  
#   def __str__(self):
#     return "Kadomatsu(length={0}, cost={1})".format(self.length, self.cost)
  
#   def __repr__(self):
#     return self.__str__()

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, B, C, L = parse()
  # print(N, A, B, C, L)

  # 門松セットの初期化
  kadomatsu_set_list = []
  kadomatsu_set = []
  cost_zero = [0, 0, 0]
  for l in L:
    if A == l: cost_zero[0] = 1
    elif B == l: cost_zero[1] = 1
    elif C == l: cost_zero[2] = 1
    kadomatsu_set.append((l, 0))
    # kadomatsu_set.append(Kadomatsu(l, 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]) > 3:
    for combination in combinations(kadomatsu_set_list[i], 2):
      # print("combination:", combination)
      new_kadomastu = (combination[0][0] + combination[1][0], 
        combination[0][1] + combination[1][1] + 10)
      # new_kadomastu = Kadomatsu(combination[0].length + combination[1].length, 
      #   combination[0].cost + combination[1].cost + 10)
      
      # new_kadomastu_setの初期化
      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 = []
      # for kadomatsu in kadomatsu_set_list[i]:
      #   if kadomatsu is combination[0] or kadomatsu is combination[1]: 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)

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

    # Aに最も長さが近い門松を探す
    min_diff_A = 10 ** 10
    min_diff_A_i = 0
    for i, kadomatsu in enumerate(kadomatsu_set):
      diff = abs(A - kadomatsu[0])
      # diff = abs(A - kadomatsu.length)
      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])
      # diff = abs(B - kadomatsu.length)
      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])
      # diff = abs(C - kadomatsu.length)
      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: Time Limit Exceeded

Solution code:

from itertools import combinations
from copy import deepcopy

class Kadomatsu:
  def __init__(self, length, cost):
    self.length = length
    self.cost = cost
  
  def __str__(self):
    return "Kadomatsu(length={0}, cost={1})".format(self.length, self.cost)
  
  def __repr__(self):
    return self.__str__()

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, B, C, L = parse()
  # print(N, A, B, C, L)

  # 門松セットの初期化
  kadomatsu_set_list = []
  kadomatsu_set = []
  cost_zero = [0, 0, 0]
  for l in L:
    if A == l: cost_zero[0] = 1
    elif B == l: cost_zero[1] = 1
    elif C == l: cost_zero[2] = 1
    kadomatsu_set.append(Kadomatsu(l, 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]) > 3:
    for combination in combinations(kadomatsu_set_list[i], 2):
      # print("combination:", combination)
      new_kadomastu = Kadomatsu(combination[0].length + combination[1].length, 
        combination[0].cost + combination[1].cost + 10)
      
      # new_kadomastu_setの初期化
      new_kadomastu_set = []
      for kadomatsu in kadomatsu_set_list[i]:
        if kadomatsu is combination[0] or kadomatsu is combination[1]: 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)

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

    # Aに最も長さが近い門松を探す
    min_diff_A = 10 ** 10
    min_diff_A_i = 0
    for i, kadomatsu in enumerate(kadomatsu_set):
      diff = abs(A - kadomatsu.length)
      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.length)
      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.length)
      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].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()