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: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
from collections import Counter

N,A,B,C=map(int,raw_input().split())
ORG=[A,B,C]
ORG.sort(reverse=True)

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

P=[]
for i in itertools.product(range(4), repeat=N):	#a:0 , b:1 , c:2 , unused:3
	P.append(i)				#Permutation


ans=float("inf")

for u in P:
	t=0	#答えの候補
	a=0; b=0; c=0	#3本の竹の長さの候補
	for i,x in enumerate(u):
		if x==0: a+=L[i]
		elif x==1: b+=L[i]
		elif x==2: c+=L[i]

	if a!=0 and b!=0 and c!=0:	#候補の数が３つできることは必須
		T=[a,b,c]
		T.sort(reverse=True)
		for x, y in zip(ORG, T):
			t+=abs(x-y)

		CT=Counter(u)
		for num, cnt in CT.items():
			if num in (0,1,2):
				t+=(cnt-1)*10
		ans=min(ans, t)


print ans

Submission status: Accepted

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

def search(a: list, b: list, c: list, yet: list):
    global N, A, B, C, ans
    if len(yet):
        search(a + [yet[0]], b, c, yet[1:])
        search(a, b + [yet[0]], c, yet[1:])
        search(a, b, c + [yet[0]], yet[1:])
        search(a, b, c, yet[1:])
    else:
        if len(a) > 0 and len(b) > 0 and len(c) > 0:
            candidate = 0
            candidate += 10*(len(a) - 1)
            candidate += 10*(len(b) - 1)
            candidate += 10*(len(c) - 1)
            candidate += abs(sum(a) - A)
            candidate += abs(sum(b) - B)
            candidate += abs(sum(c) - C)
            ans = min(ans, candidate)
        
bamboos = []
for i in range(N):
    bamboos.append(int(input()))

search([], [], [], bamboos)
print(ans)

Submission status: Accepted

Solution code:
n, a, b, c = map(int, input().split())
lst = [int(input()) for _ in range(n)]
target_lst = [a,b,c]

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

min_ans = 10 ** 100
for i in range(4**len(lst)):
    a = nsin(i,4)
    if len(a) < len(lst):
        a = '0' * (len(lst)-len(a)) + a
    a_lst,b_lst,c_lst = [], [], []
    for k, j in enumerate(a):
        if int(j) == 1:
            a_lst.append(lst[k])
        elif int(j) == 2:
            b_lst.append(lst[k])
        elif int(j) == 3:
            c_lst.append(lst[k])
    if a_lst == [] or b_lst == [] or c_lst == []:
        ans = 10**100
    else:
        a_pt = abs(target_lst[0]-sum(a_lst)) + (len(a_lst) - 1) * 10
        b_pt = abs(target_lst[1]-sum(b_lst)) + (len(b_lst) - 1) * 10
        c_pt = abs(target_lst[2]-sum(c_lst)) + (len(c_lst) - 1) * 10
        ans = a_pt + b_pt + c_pt
    if min_ans > ans:
        min_ans = ans
        
print(min_ans)

Submission status: Accepted

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

inf = float("inf")


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
    ans0 = dfs(cur + 1, a, b, c)
    ans1 = dfs(cur + 1, a + l_list[cur], b, c) + 10
    ans2 = dfs(cur + 1, a, b + l_list[cur], c) + 10
    ans3 = dfs(cur + 1, a, b, c + l_list[cur]) + 10
    return min(ans0, ans1, ans2, ans3)


print(dfs(0, 0, 0, 0))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    def dfs(depth, l):
        if depth == 0:
            calc(l)
            return
        for i in range(4):
            dfs( depth - 1, l + str(i) )

    def calc(l):
        res = 0
        if not '0' in l or not '1' in l or not '2' in l:
            return
        aa = [[] for i in range(3)]
        for i,x in enumerate(list(l)):
            x = int(x)
            if x == 3:
                continue
            take = NLIST[i]
            aa[x].append(take)
        for i, a in enumerate(aa):
            if len(a) > 1:
                res += 10 * (len(a) - 1)
            res += abs(ABC[i] - sum(a))
        RESULT.append(res)




    RESULT = []
    N,A,B,C = map(int, lines.pop(0).split(' '))
    ABC = [A,B,C]
    NLIST = []
    for i in range(N):
        NLIST.append(int(lines.pop(0)))
    dfs(N, "")
    print(min(RESULT))
    
lines = [x.strip() for x in sys.stdin.readlines()]

#
# solve !!
#
solve(lines)

Submission status: Accepted

Solution code:

N, A, B, C = map(int, input().split())
t = [int(input()) for i in range(N)]
INF = 10 ** 9

l = [[[], [], []]]  # [[[0, 2, 3], [1], [4]], [[0], [1, 2, 3], [4]]]
for i in range(N):
    l2 = l.copy()
    for li in l2:
        a = li[0]
        b = li[1]
        c = li[2]

        l.append([a, b, c])
        l.append([a + [t[i]], b, c])
        l.append([a, b + [t[i]], c])
        l.append([a, b, c + [t[i]]])

ll = []
for li in l:
    a = li[0]
    b = li[1]
    c = li[2]
    if not a or not b or not c:
        continue
    ll.append(li)


ans = 100000000
for li in ll:
    a = li[0]
    b = li[1]
    c = li[2]

    cost = 0
    len_a = len(a)
    len_b = len(b)
    len_c = len(c)
    
    tmp = sum(a)
    cost += 10 * (len_a - 1)
    cost += abs(A - tmp)

    tmp = sum(b)
    cost += 10 * (len_b - 1)
    cost += abs(B - tmp)

    tmp = sum(c)
    cost += 10 * (len_c - 1)
    cost += abs(C - tmp)

    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
ans=[]
for j in itertools.product(range(4),repeat=n):
  LA=[];LB=[];LC=[]
  for k in range(n):
    if j[k]==0:LA.append(l[k])
    elif j[k]==1:LB.append(l[k])
    elif j[k]==2:LC.append(l[k])
  if LA==[] or LB==[] or LC==[]:
    pass
  else:
    ans.append(abs(a-sum(LA))+(len(LA)-1)*10+abs(b-sum(LB))+(len(LB)-1)*10+abs(c-sum(LC))+(len(LC)-1)*10)
print(min(ans))

Submission status: Accepted

Solution code:
def main():
    N,A,B,C = map(int, input().split())
    l = [int(input()) for _ in range(N)]
    
    INF = 1<<20
    f = None
    
    def perm(n, a, b, c):
        if n == N:
            if all([a, b, c]):
                return abs(A-a)+abs(B-b)+abs(C-c)-30
            else:
                return INF
        return min(
            f(n+1,a,b,c),
            f(n+1,a+l[n],b,c)+10,
            f(n+1,a,b+l[n],c)+10,
            f(n+1,a,b,c+l[n])+10
            )
    
    f = perm
    print(f(0,0,0,0))

main()

Submission status: Accepted

Solution code:
def main():
    N,A,B,C = map(int, input().split())
    l = [int(input()) for _ in range(N)]
    
    INF = 1<<20
    
    def perm(n, a, b, c):
        if n == N:
            if all([a, b, c]):
                return abs(A-a)+abs(B-b)+abs(C-c)-30
            else:
                return INF
        return min(
            perm(n+1,a,b,c),
            perm(n+1,a+l[n],b,c)+10,
            perm(n+1,a,b+l[n],c)+10,
            perm(n+1,a,b,c+l[n])+10
            )
    
    print(perm(0,0,0,0))

main()

Submission status: Accepted

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

INF = 1<<20
score = INF

import itertools
for ms in itertools.product(range(-1,3), repeat=N):
    lens = [0]*3
    tmp_score = -30
    for i, group in enumerate(ms):
        if group>=0:
            lens[group] += l[i]
            tmp_score += 10
    if all(lens):
        score = min(score, tmp_score + abs(lens[0]-A)+abs(lens[1]-B)+abs(lens[2]-C))

print(score)

Submission status: Accepted

Solution code:
# coding: utf-8

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()


def solve(b, L, As):
    si = [b // (4**i) % 4 for i in range(len(L))]
    c = 0
    ls = [0] * 4
    for l, s in zip(L, si):
        if s > 0 and ls[s] > 0:
            c += 10
        ls[s] += l
    if 0 in ls[1:]: return float("inf")
    return c + sum([abs(As[i] - ls[i + 1]) for i in range(3)])


def main():
    N, A, B, C = MI()
    L = [II() for _ in range(N)]
    ans = float("inf")
    for i in range(4**N):
        ans = min(ans, solve(i, L, [A, B, C]))
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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


def f(a, b, c, bl, ans):
    if len(bl) == 0:
        if len(a) == 0 or len(b) == 0 or len(c) == 0:
            return ans
        return abs(A - sum(a)) + (len(a) - 1) * 10 + \
            abs(B - sum(b)) + (len(b) - 1) * 10 + \
            abs(C - sum(c)) + (len(c) - 1) * 10
    for i in range(len(bl)):
        l = bl[i]
        a.append(l)
        ans = min(ans, f(a, b, c, bl[i + 1:], ans))
        a.pop(-1)
        b.append(l)
        ans = min(ans, f(a, b, c, bl[i + 1:], ans))
        b.pop(-1)
        c.append(l)
        ans = min(ans, f(a, b, c, bl[i + 1:], ans))
        c.pop(-1)
        ans = min(ans, f(a, b, c, bl[i + 1:], ans))
    return ans


def main():
    bl = []
    for _ in range(N):
        bl.append(int(input()))
    print(f([], [], [], bl, 10000))


main()

Submission status: Accepted

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


def dfs(i,a,b,c):
    if i == N:
        if min(a,b,c) > 0:
            return abs(A-a) + abs(B-b) + abs(C-c) - 30  # 最初に選ぶのは合成しないから。
        else:
            return 10**9

    case1 = dfs(i+1, a, b, c)
    case2 = dfs(i+1, a+l[i], b, c) + 10
    case3 = dfs(i+1, a, b+l[i], c) + 10
    case4 = dfs(i+1, a, b, c+l[i]) + 10

    return min(case1, case2, case3, case4)

print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
inf = 1 << 60
N,A,B,C=map(int, input().split())
l = []
for i in range(N):
    l.append(int(input()))

def dfs(n, a, b, c):
    if n == N:
        if min(a,b,c) == 0:
            return inf
        return abs(A-a)+abs(B-b)+abs(C-c)-30

    a1 = dfs(n+1, a, b, c)
    a2 = dfs(n+1, a + l[n], b, c) + 10
    a3 = dfs(n+1, a, b + l[n], c) + 10
    a4 = dfs(n+1, a, b, c + l[n]) + 10
    return min(a1, a2, a3, a4)

def solve2():
    best_sc = inf
    for i in range(0, 1 << (2*N)):
        le = [0] * 3
        sc = 0
        for j in range(N):
            a = (i >> (2*j)) & 0x3
            if a <= 2:
                le[a] += l[j]
                sc += 10
        if min(le) == 0:
            continue
        sc += abs(A-le[0]) + abs(B-le[1]) + abs(C-le[2]) - 30
        best_sc = min(best_sc, sc)
    return best_sc

#ans = dfs(0, 0, 0, 0)
ans = solve2()
print(ans)

Submission status: Accepted

Solution code:
import itertools

n,a,b,c=(input().split())
n,a,b,c=int(n),int(a),int(b),int(c)
l=[int(input()) for i in range(n)]
#print(n,a,b,c,l)

ansans=float('inf')
ans=float('inf')

mylist=list(itertools.product(range(4),repeat=n))
#print(len(mylist))
#mylist=[1,2,2,2,3]
for j in range(len(mylist)):
    x,y,z=0,0,0
    for i in range(n):
        if mylist[j][i]==1:
            x+=l[i]
        elif mylist[j][i]==2:
            y+=l[i]
        elif mylist[j][i]==3:
            z+=l[i]
        
    if mylist[j].count(1)>0 and mylist[j].count(2)>0 and mylist[j].count(3) > 0:
        ans=0
        ans+=abs(a-x)+abs(b-y)+abs(c-z)
        compo=0
        for i in range(1,4):
            compo+=mylist[j].count(i)-1
        ans+=10*compo

    if ans < ansans:
        ansans = ans

print(ansans)

Submission status: Accepted

Solution code:
inf = 1 << 60
N,A,B,C=map(int, input().split())
l = []
for i in range(N):
    l.append(int(input()))

def dfs(n, a, b, c):
    if n == N:
        if min(a,b,c) == 0:
            return inf
        return abs(A-a)+abs(B-b)+abs(C-c)-30

    a1 = dfs(n+1, a, b, c)
    a2 = dfs(n+1, a + l[n], b, c) + 10
    a3 = dfs(n+1, a, b + l[n], c) + 10
    a4 = dfs(n+1, a, b, c + l[n]) + 10
    return min(a1, a2, a3, a4)

ans = dfs(0, 0, 0, 0)
print(ans)

Submission status: Accepted

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

INF = 1<<20

def perm(n, a, b, c):
    if n == N:
        if all([a, b, c]):
            return abs(A-a)+abs(B-b)+abs(C-c)-30
        else:
            return INF
    return min(
        perm(n+1,a,b,c),
        perm(n+1,a+l[n],b,c)+10,
        perm(n+1,a,b+l[n],c)+10,
        perm(n+1,a,b,c+l[n])+10
        )

print(perm(0,0,0,0))

Submission status: Accepted

Solution code:
from itertools import product

N,a,b,c = map(int,input().split())
L = list(int(input()) for i in range(N))

ans = float("inf")

for prod in product(range(4), repeat=N) :
    A = []
    B = []
    C = []
    for i in range(len(prod)) :
        if prod[i] == 1 :
            A.append(L[i])
        elif prod[i] == 2 :
            B.append(L[i])
        elif prod[i] == 3 :
            C.append(L[i])
    
    if len(A) * len(B) * len(C) == 0 :
        continue
    cost = 0
    for li in [A,B,C] :
        cost += (len(li)-1)*10
    cost += abs(a-sum(A)) + abs(b-sum(B)) + abs(c-sum(C))
    ans = min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N,a,b,c = map(int,input().split())
L = list(int(input()) for i in range(N))

ans = float("inf")

for prod in product(range(4), repeat=N) :
    A = []
    B = []
    C = []
    D = []
    for i in range(len(prod)) :
        if prod[i] == 1 :
            A.append(L[i])
        elif prod[i] == 2 :
            B.append(L[i])
        elif prod[i] == 3 :
            C.append(L[i])
        else :
            D.append(L[i])
    if len(A) * len(B) * len(C) == 0 :
        continue
    cost = 0
    for li in [A,B,C] :
        cost += (len(li)-1)*10
    cost += abs(a-sum(A)) + abs(b-sum(B)) + abs(c-sum(C))
    
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import itertools,sys

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

def eval(a,b,c,aa,bb,cc):
    #print(a,b,c,aa,bb,cc)
    ra=a+sum(aa)
    rb=b+sum(bb)
    rc=c+sum(cc)
    #print("rarbrc:",ra,rb,rc, abs(A-ra), abs(B-rb), abs(C-rc),C,rc)
    diff = abs(A-ra) + abs(B-rb) + abs(C-rc)
    diff+=10*len(aa)
    diff+=10*len(bb)
    diff+=10*len(cc)
    return diff


cn=0
ans=1<<20
ops=[-1,0,1,2]
for a,b,c in itertools.permutations(range(N), 3):
    others=set(range(N))
    others.remove(a)
    others.remove(b)
    others.remove(c)
    others=list(others)
    for O in itertools.product(ops, repeat=len(others)):
        aa,bb,cc=[],[],[]
        for i,op in enumerate(O):
            if op==-1:continue
            if op==0:aa.append(l[others[i]])
            if op==1:bb.append(l[others[i]])
            if op==2:cc.append(l[others[i]])
        #print(aa,bb,cc)
        val=eval(l[a],l[b],l[c],aa,bb,cc)
        #print(val)
        # cn+=1
        # if cn==2:
        #     pass
            #sys.exit(0)
        ans=min(ans,val)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

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

def dfs(n, a, b, c):
    if n == N:
        if a == 0 or b == 0 or c == 0: return float('inf')
        return abs(A-a) + abs(B-b) + abs(C-c)
    ca = dfs(n+1, a+ll[n], b, c)
    if a > 0: ca += 10
    cb = dfs(n+1, a, b+ll[n], c)
    if b > 0: cb += 10
    cc = dfs(n+1, a, b, c+ll[n])
    if c > 0: cc += 10
    cn = dfs(n+1, a, b, c)
    return min(ca, cb, cc, cn)


def main():
    print(dfs(0, 0, 0, 0))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from itertools import product
ans = float("inf")
for p in product(range(4),repeat=N):
    a = [L[i] for i in range(N) if p[i]==1]
    b = [L[i] for i in range(N) if p[i]==2]
    c = [L[i] for i in range(N) if p[i]==3]

    if a==[] or b==[] or c==[]:
        continue
    
    t = 0
    for x in [a,b,c]:
        if len(x)>=2:
            t += (len(x)-1)*10
    sumA = sum(a)
    sumB = sum(b)
    sumC = sum(c)
    t += abs(A-sumA) + abs(B-sumB) + abs(C-sumC)

    ans = min(ans,t)

print(ans)

Submission status: Accepted

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

def f(cur,a,b,c) :
    if cur == N :
        if min(a,b,c) > 0 :
            return abs(a-A) + abs(b-B) + abs(c-C) - 30
        else :
            return float("inf")
    ret0 = f(cur+1,a,b,c)
    ret1 = f(cur+1,a+L[cur],b,c) + 10
    ret2 = f(cur+1,a,b+L[cur],c) + 10
    ret3 = f(cur+1,a,b,c+L[cur]) + 10
    
    return min(ret0,ret1,ret2,ret3)

print(f(0,0,0,0))

Submission status: Accepted

Solution code:
from itertools import product
N,*ABC=map(int,input().split())
L=[int(input()) for i in range(N)]
MP=10**9
for P in product([0,1,2,3],repeat=N):
    if {0,1,2}<=set(P):
        m=[0,0,0]
        for p,l in zip(P,L):
            if p!=3:m[p]+=l
        cost1=sum(abs(m-l) for m,l in zip(m,ABC))
        cost2=sum(1 for i in P if i!=3)-3
        MP=min(MP,cost1+cost2*10)
print(MP)

Submission status: Accepted

Solution code:
#解説のコードそのもの

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9

def dfs(n, a, b, c):
    if n == N:
            return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a,b,c)>0 else INF
    ret0 = dfs(n + 1, a, b, c)
    ret1 = dfs(n + 1, a + l[n], b, c) + 10
    ret2 = dfs(n + 1, a, b + l[n], c) + 10
    ret3 = dfs(n + 1, a, b, c + l[n]) + 10
    return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))

Submission status: Accepted

Solution code:
N, A, B, C = list(map(int, input().rstrip().split()))
l = [int(input()) for i in range(N)]

costs = []

for i in range(2 ** (2 * N)):
    i_bin = format(i, '0' + str(2 * N) + 'b')
    cost = 0
    a = b = c = 0
    for j in range(N):
        t = i_bin[j * 2 : j * 2 + 2]
        if t == '01':
            cost += 10
            a += l[j]
        elif t == '10':
            cost += 10
            b += l[j]
        elif t == '11':
            cost += 10
            c += l[j]
    if min(a, b, c) == 0:
        continue
    cost += abs(a - A) + abs(b - B) + abs(c - C) - 30
    costs.append(cost)

print(min(costs))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,a,b,c = LI()
    a = [a,b,c]
    l = [I() for _ in range(n)]
    r = inf
    for b in range(4**n):
        k = [[] for _ in range(4)]
        for i in range(n):
            k[b % 4].append(l[i])
            b //= 4
        nf = 0
        for i in range(3):
            if len(k[i]) == 0:
                nf = 1
                break
        if nf:
            continue

        t = 0
        for i in range(3):
            t += (len(k[i]) - 1) * 10 + abs(sum(k[i])-a[i])
        if r > t:
            r = t

    return r



print(main())

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF=10**9

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: Accepted

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

takes = takes+[0,0,0,0,0,0,0]
takes = takes[:8]
g = [A, B, C]
combis = []
for i in range(4):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    for n in range(4):
                        for o in range(4):
                            for p in range(4):
                                combis.append([i,j,k,l,m,n,o,p])

min_diff = 10**10
for combi in combis:
    A,B,C = 0,0,0
    for idx, el in enumerate(combi):
        if el == 0:
            A += takes[idx]
        elif el == 1:
            B += takes[idx]
        elif el == 2:
            C += takes[idx]

        if A == 0 or B == 0 or C == 0:
            continue

        A_diff = abs(g[0] - A) + (len([_ for _ in combi if _ == 0]) - 1)*10
        B_diff = abs(g[1] - B) + (len([_ for _ in combi if _ == 1]) - 1)*10
        C_diff = abs(g[2] - C) + (len([_ for _ in combi if _ == 2]) - 1)*10
        diff = A_diff + B_diff + C_diff
        min_diff = min(diff, min_diff)

print(min_diff)

Submission status: Accepted

Solution code:
n, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(n)]
inf = 10 ** 10
def dfs(k, a, b, c):
    if k == n:
        if 0 in (a,b,c):
            return inf
        return abs(A - a) + abs(B - b) + abs(C - c) - 30
    ret = [0] * 4
    ret[0] = dfs(k+1, a + l[k], b, c) + 10
    ret[1] = dfs(k+1, a, b + l[k], c) + 10
    ret[2] = dfs(k+1, a, b, c + l[k]) + 10
    ret[3] = dfs(k+1, a, b, c)
    return min(ret)
print(dfs(0, 0, 0, 0))

Submission status: Accepted

Solution code:
import itertools

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]

ans = []
for X in itertools.product(range(4), repeat=N):
    P = [[] for _ in range(4)]
    for i, x in enumerate(X):
        P[x].append(l[i])
    if min(map(len, P[1:]))==0:
        continue
    
    tmp = 0
    for Q, D in zip(P[1:], [A,B,C]):
        tmp+=10*(len(Q)-1)+abs(D-sum(Q))
    ans.append(tmp)    
print(sorted(ans)[0])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**2) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,a,b,c = li()
l = [ni() for _ in range(n)]

ans = 10**18

for i in range(4**n):
    cur = i
    cnt = {i: [] for i in range(4)}
    
    for bi in l:
        cnt[cur%4].append(bi)
        cur //= 4
    
    
    if len(cnt[1]) * len(cnt[2]) * len(cnt[3]) == 0:
        continue
    
    ans = min(ans, abs(a-sum(cnt[1]))\
                  + abs(b-sum(cnt[2]))\
                  + abs(c-sum(cnt[3]))\
                  + 10*(n - len(cnt[0]) -3))
    
print(ans)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]
INF = 10**9

def dfs(cur, a, b, c):
    if cur==N:
        if a*b*c==0:
            return INF
        else:
            return abs(a-A) + abs(b-B) + abs(c-C) - 30
    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: Accepted

Solution code:
n,A,B,C=map(int,input().split(' '))
l=[int(input()) for i in range(n)]
INF=10**9
def bfs(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
    else:
        ret0=bfs(cur+1,a,b,c)
        ret1=bfs(cur+1,a+l[cur],b,c)+10
        ret2=bfs(cur+1,a,b+l[cur],c)+10
        ret3=bfs(cur+1,a,b,c+l[cur])+10
        return min(ret0,ret1,ret2,ret3)
print(bfs(0,0,0,0))

Submission status: Accepted

Solution code:
from itertools import product
N, A, B, C = [int(i) for i in input().split()]
l_ls = list()
for i in range(N):
    l_ls.append(int(input()))
best = 1e9
for combi in product(range(4),repeat=N):
    a = [l for l, label in zip(l_ls, combi) if label == 1]
    b = [l for l, label in zip(l_ls, combi) if label == 2]
    c = [l for l, label in zip(l_ls, combi) if label == 3]
    dis = abs(A - sum(a)) + abs(B - sum(b)) + abs(C - sum(c)) \
          + (len(a) + len(b) + len(c) - 3) * 10
    if len(a) * len(b) * len(c) == 0:
        continue
    if best > dis:
        best = dis
print(best)

Submission status: Accepted

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

def kadomatsu(i, a, b, c):
  if i == N:
    if min(a, b, c) > 0:
      return abs(a - A) + abs(b - B) + abs(c - C) - 30
    else:
      return float("inf")
  ret0 = kadomatsu(i + 1, a, b, c)
  ret1 = kadomatsu(i + 1, a + l[i], b, c) + 10
  ret2 = kadomatsu(i + 1, a, b + l[i], c) + 10
  ret3 = kadomatsu(i + 1, a, b, c + l[i]) + 10
  return min(ret0, ret1, ret2, ret3)

print(kadomatsu(0, 0, 0, 0))

Submission status: Accepted

Solution code:
from itertools import product
n,a,b,c = (int(i) for i in input().split())
x = [int(input()) for i in range(n)]
ans = float("inf")
def f(q):
    if any(i not in q for i in range(3)): return ans
    else:
        z,num = [0,0,0],0
        for i in range(n):
            if q[i]-3:
                if z[q[i]]: num+=10
                z[q[i]]+=x[i]
        return num+abs(z[0]-a)+abs(z[1]-b)+abs(z[2]-c)
for i in product((0,1,2,3),repeat=n): ans = min(ans,f(i))
print(ans)

Submission status: Accepted

Solution code:

n,A,B,C = map(int, input().split()) 

ls = [int(input()) for _ in range(n)]

inf = 10000

def dfs(i,a,b,c):
    if i == n:
        return \
            inf if min(a,b,c) == 0 \
            else abs(A-a) + abs(B-b)+abs(C-c)-30
    
    i1 = i+1
    lsi = ls[i]

    r0 = dfs(i1, a,b,c)
    r1 = dfs(i1, a+lsi,b,c) + 10
    r2 = dfs(i1, a,b+lsi,c) + 10
    r3 = dfs(i1, a,b,c+lsi) + 10

    return min(r0,r1,r2,r3)

print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
T=[int(input()) for i in range(N)]
INF=10**15

def solve(n,a,b,c):
  if n==N:
    if min(a,b,c) > 0 :
      return abs(a-A)+abs(b-B)+abs(c-C)-30
    else:
      return INF
  else:
    ret0=solve(n+1,a,b,c)
    ret1=solve(n+1,a+T[n],b,c)+10
    ret2=solve(n+1,a,b+T[n],c)+10
    ret3=solve(n+1,a,b,c+T[n])+10
    return min(ret0,ret1,ret2,ret3)
  
print(solve(0,0,0,0))

Submission status: Accepted

Solution code:
import numpy as np
    
INF = float('inf')

n,A,B,C = [int(i) for i in input().split()]

l = [int(input()) for i 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: Accepted

Solution code:
N,A,B,C = (int(i) for i in input().split())  

l = []
for _ in range(N):
    l.append(int(input()))


#N,A,B,C =  5, 100,90,80 

#l = [98,40,30,21,80]

def to_bit(num,digit):
    bit = [0] * digit
    for i in range(digit):
        bit[i] = num % 4
        num = int((num - (num % 4)) / 4)
    return bit

min_cost = 5000

for i in range(4 ** N):
    bit = to_bit(i,len(l))
    #print(bit)
    cost = 0

    #A
    sum_ = 0
    counts = 0
    for j in range(len(l)):
        if bit[j] == 0:
            sum_ += l[j]
            counts += 1
    if counts > 0:
        cost += abs(sum_ - A) + 10 * (counts - 1)
    else:
        cost += 1000000

    #B
    sum_ = 0
    counts = 0
    for j in range(len(l)):
        if bit[j] == 1:
            sum_ += l[j]
            counts += 1
    if counts > 0:
        cost += abs(sum_ - B) + 10 * (counts - 1)
    else:
        cost += 1000000

    #C
    sum_ = 0
    counts = 0
    for j in range(len(l)):
        if bit[j] == 2:
            sum_ += l[j]
            counts += 1
    if counts > 0:
        cost += abs(sum_ - C) + 10 * (counts - 1)
    else:
        cost += 1000000

    if cost < min_cost:
        min_cost = cost
print(min_cost)

Submission status: Accepted

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

INF = 10 ** 9

def dfs(idx, a, b, c) -> int:
	if idx == n:
		return abs(A - a) + abs(B - b) + abs(C - c) - 30 if min(a, b, c) > 0 else INF
	res0 = dfs(idx + 1, a, b, c)
	res1 = dfs(idx + 1, a + l[idx], b, c) + 10
	res2 = dfs(idx + 1, a, b + l[idx], c) + 10
	res3 = dfs(idx + 1, a, b, c + l[idx]) + 10
	return min(res0, res1, res2, res3)

print(dfs(0, 0, 0, 0))

Submission status: Accepted

Solution code:
n,a,b,c=map(int,input().split())
l = [int(input()) for _ in range(n)]
ans = 100000000
for i in range(4**n):
  x,y,z=0,0,0
  s,t,u=0,0,0
  for j in range(n):
    if i % 4 == 0:
      x += l[j]
      s += 1
    elif i % 4 == 1:
      y += l[j]
      t += 1
    elif i % 4  == 2:
      z += l[j]
      u += 1
    i //= 4
  if s == 0 or t == 0 or u == 0:
    continue
  k = (s + t + u - 3) * 10
  k += abs(a - x)
  k += abs(b - y)
  k += abs(c - z)
  ans = min(ans, k)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,a,b,c = map(int,input().split())
l = [int(input()) for i in range(n)]

def dfs(depth,x,y,z):
  if depth==n:
    return abs(x-a)+abs(y-b)+abs(z-c)-30 if min(x,y,z)>0 else np.inf
  
  A = dfs(depth+1,x+l[depth],y,z)+10
  B = dfs(depth+1,x,y+l[depth],z)+10
  C = dfs(depth+1,x,y,z+l[depth])+10
  X = dfs(depth+1,x,y,z)
  
  return min(A,B,C,X)
print(dfs(0,0,0,0))