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:
N,A,B,C=map(int,input().split())
L=[]
for i in range(0,N):
    L.append(int(input()))

ans=float('inf')
for i in range(0,4**N):
    a=0
    b=0
    c=0
    MP=0
    for j in range(0,16):
        if i>>(2*j) & 1==1 and i>>(2*j+1) &1==0:
            a+=L[j]
            MP+=10
        elif i>>(2*j) & 1==0 and i>>(2*j+1) &1==1:
            b+=L[j]
            MP+=10
        elif i>>(2*j) & 1==1 and i>>(2*j+1) &1==1:
            c+=L[j]
            MP+=10

    if a*b*c==0:
        continue
    else:
        MP-=30
        MP+=abs(a-A)+abs(b-B)+abs(c-C)
        ans=min(MP,ans)

print(ans)

Submission status: Accepted

Solution code:
n,a,b,c = map(int,input().split())
l = [int(input()) for _ in range(n)]
ans = 10**6
for i in range(4**n):
  pattern = [0]*n
  for j in range(n):
    pattern[j] = ((i >> j*2) & 3)
  bamboo = [0]*4
  for j in range(n):
    bamboo[pattern[j]] += l[j]
  if bamboo[1]*bamboo[2]*bamboo[3]==0:
    continue
  time = pattern.count(1)*10+pattern.count(2)*10+pattern.count(3)*10-30+abs(bamboo[1]-a)+abs(bamboo[2]-b)+abs(bamboo[3]-c)
  if ans > time:
    ans = time
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n, a, b, c = map(int, input().split())
kumiawase = list(product(range(4), repeat=n))
L = []
for _ in range(n):
    L.append(int(input()))


ans = 10 ** 20

for kumi in kumiawase:
    temp = 0
    L0 = []
    L1 = []
    L2 = []
    for j in range(n):
        if kumi[j] == 0:
            L0.append(L[j])
        if kumi[j] == 1:
            L1.append(L[j])
        if kumi[j] == 2:
            L2.append(L[j])
    n0 = len(L0)
    n1 = len(L1)
    n2 = len(L2)
    if n0 == 0 or n1 == 0 or n2 == 0:
        continue
    l0 = sum(L0)
    l1 = sum(L1)
    l2 = sum(L2)
    temp = 10 * (n0 - 1 + n1 - 1 + n2 - 1) + abs(l0 - a) + abs(l1 - b) + abs(l2 - c)
    ans = min(temp, ans)
print(ans)

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())
L=[0]*n
for i in range(n):
  L[i]=int(input())
ans=10**10
for i in range(2**n):
  S=format(i,"10b")
  K=[]
  for j in range(n):
    if S[-1-j]=="1":
      K.append(j)
  k=len(K)
  if len(K)<3:
    continue
  for j in range(2**k):
    SS=format(j,"10b")
    AA=[]
    for l in range(k):
      if SS[-1-l]=="1":
        AA.append(K[l])
    a=len(AA)
    if a<1 or k-2<a:
      continue
    KK=sorted(list(set(K)-set(AA)))
    kk=k-a
    for l in range(2**kk):
      SSS=format(l,"10b")
      BB=[]
      for m in range(kk):
        if SSS[-1-m]=="1":
          BB.append(KK[m])
      b=len(BB)
      if b<1 or kk-1<b:
        continue
      CC=sorted(list(set(KK)-set(BB)))
      c=len(CC)
      AAA=sum(L[AA[x]] for x in range(a))
      BBB=sum(L[BB[x]] for x in range(b))
      CCC=sum(L[CC[x]] for x in range(c))
      aans=(a+b+c-3)*10+abs(AAA-A)+abs(BBB-B)+abs(CCC-C)
      if aans<ans:
        ans=aans
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def dfs():
    stack = [(0, 0, 0, 0, 0)]
    ans = float("inf")
    while stack:
        c, c_a, c_b, c_c, score = stack.pop()

        if c == N:
            #一本目を選ぶ時には合体コストがかからないが+10を計上してるので、最後に-10 * 3をする。
            if c_a > 0 and c_b > 0 and c_c > 0:
                ans = min(ans, abs(A-c_a) + abs(B-c_b) + abs(C-c_c) + score - 30)
            continue
        
        stack.append((c+1, c_a, c_b, c_c, score))
        stack.append((c+1, c_a+l[c], c_b, c_c, score + 10))
        stack.append((c+1, c_a, c_b+l[c], c_c, score + 10))
        stack.append((c+1, c_a, c_b, c_c+l[c], score + 10))
    return ans
    

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

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

print(dfs())

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 = (int(i) for i in input().split())
l = [int(input()) for i in range(n)]
a = []
b = []
c = []

def furiwake(x):
    global a
    global b
    global c
    a = []
    b = []
    c = []
    for i in range(1, n+1):
        if dig4(x, i) == 0:
            a.append(l[i-1])
        if dig4(x, i) == 1:
            b.append(l[i-1])
        if dig4(x, i) == 2:
            c.append(l[i-1])

def dig4(n, k):
    return (n%(4**k))//(4**(k-1))

def cost():
    costa = 10 * (len(a)-1) + abs(sum(a)-A)
    costb = 10 * (len(b)-1) + abs(sum(b)-B)
    costc = 10 * (len(c)-1) + abs(sum(c)-C)
    return costa+costb+costc

ans = 1000000000
for i in range(1, 4**8):
    furiwake(i)
    if(len(a)*len(b)*len(c)):
        ans = min(ans, cost())
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n,*B=map(int,input().split())
A=[int(input()) for i in range(n)]
s=10**9
for P in product([0,1,2,3],repeat=n):
  if {0,1,2}<=set(P):
    m=[0,0,0]
    for x,y in zip(P,A):
      if x!=3:
        m[x]+=y
    t=sum(abs(m-y) for m,y in zip(m,B))
    l=sum(1 for j in P if j!=3)-3
    s=min(s,t+l*10)
print(s)

Submission status: Accepted

Solution code:
n,a,b,c=map(int,input().split())
L=[]

def base10to(n,b):
    if n//b:
        return base10to(n//b,b)+str(n%b)
    return str(n%b)

for i in range(n):
    L.append(int(input()))
ans=10**10
for i in range(4**n):
    S=base10to(i,4)
    S=S.zfill(n)
    A=[]
    B=[]
    C=[]
    for j in range(n):
        if S[j]=='0':
            continue
        elif S[j]=='1':
            A.append(L[j])
        elif S[j]=='2':
            B.append(L[j])
        else:
            C.append(L[j])
    if A and B and C:
        ans=min(ans,abs(a-sum(A))+(len(A)-1)*10+abs(b-sum(B))+(len(B)-1)*10+abs(c-sum(C))+(len(C)-1)*10)
print(ans)

Submission status: Accepted

Solution code:
INF = float("inf")

N, A, B, C = map(int, 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:
import itertools
N,A,B,C = map(int,input().split())
L = [int(input()) for _ in range(N)]
 
INF = 10 ** 18
answer = INF
for pattern in itertools.product(range(4), repeat = N):
  x = [0] * 4
  MP = 0
  for take, length in zip(pattern, L):
    if take == 3:
      continue
    if x[take] != 0:
      MP += 10
    x[take] += length
  if x[0] == 0 or x[1] == 0 or x[2] == 0:
    continue
  MP += abs(A-x[0])
  MP += abs(B-x[1])
  MP += abs(C-x[2])
  if answer > MP:
    answer = MP
print(answer)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n,a,b,c=map(int,input().split())
L=[]
A=[a,b,c]
for i in range(n):
    L.append(int(input()))
L.sort()

ans=10**9
for i in range(4**n):
    F=[[] for i in range(3)] #竹格納:[A,B,C]
    now=i
    for j in range(n):
        r=now%(4**(j+1))
        chk=r//(4**(j))
        if chk!=3:
            F[chk].append(L[j])
        now-=r    
    if F[0] and F[1] and F[2]: #竹が1本以上あるとき
        mp=0
        for k in range(3):
            f=F[k]
            mp+=abs(sum(f)-A[k])+10*(max(0,len(f)-1))
        ans=min(mp,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n,a,b,c=map(int,input().split())
L=[]
A=[a,b,c]
for i in range(n):
    L.append(int(input()))
L.sort()

Ans=10**9
for i in range(4**n):
    F=[[] for i in range(3)] #竹格納:[A,B,C]
    now=i
    for j in range(n):
        r=now%(4**(j+1))
        chk=r//(4**(j))
        if chk!=3:
            F[chk].append(L[j])
        now-=r    
    if F[0] and F[1] and F[2]: #竹が1本以上あるとき
        ans=0
        for k in range(3):
            f=F[k] #竹一覧
            Len=len(f)
            mp=10**9
            for l in range(1,2**Len):
                t=0
                cnt=0
                for q in range(Len):
                    if (l>>q)&1:
                        cnt+=1
                        t+=f[q]
                mp=min(abs(t-A[k])+10*(max(0,cnt-1)),mp)
            ans+=mp
        Ans=min(ans,Ans)
print(Ans)

Submission status: Accepted

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

import itertools
bambuu = [[0,0,0] for _ in range(4**N)]
for i,pro in enumerate(itertools.product(['A','B',"C",'D'], repeat=N)):
    lisA = [L[j] for j in range(N) if pro[j]=='A']
    lisB = [L[j] for j in range(N) if pro[j]=='B']
    lisC = [L[j] for j in range(N) if pro[j]=='C']
    sumA = [sum(lisA),(len(lisA)-1)*10]
    sumB = [sum(lisB),(len(lisB)-1)*10]
    sumC = [sum(lisC),(len(lisC)-1)*10]
    bambuu[i-1] = [sumA,sumB,sumC]

ans = 10000
for sA,sB,sC in bambuu:
    if sA[0]>0 and sB[0]>0 and sC[0]>0:
        mp_total = abs(A-sA[0])+abs(B-sB[0])+abs(C-sC[0])+sA[1]+sB[1]+sC[1]
        if mp_total < ans:
            #record = [sA,sB,sC]
            ans = mp_total
#print(record)
print(ans)
#print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

n,a,b,c = LI()
l = [I() for _ in range(n)]

s = a+b+c
ans = inf
for i in range(1<<n):
    lst = []
    t = 0
    for j in range(n):
        if i >> j & 1:
            t += 1
            lst.append(l[j])
    if t < 3:
        continue
    for j in range(3**t):
        tmp = '0'*t + Base_10_to_n(j,3)
        tmp = tmp[-t:]
        B = [0]*t
        for k in range(t):
            if str(tmp[k]) == '1':
                B[k] = 1
            elif str(tmp[k]) == '2':
                B[k] = 2
        X = [[],[],[]]
        for k in range(t):
            X[B[k]].append(lst[k])
        if len(X[0]) == 0:
            continue
        if len(X[1]) == 0:
            continue
        if len(X[2]) == 0:
            continue
        cost = abs(sum(X[0])-a)
        cost += abs(sum(X[1])-b)
        cost += abs(sum(X[2])-c)
        cost += 10*(len(X[0])-1)
        cost += 10*(len(X[1])-1)
        cost += 10*(len(X[2])-1)
        ans = min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from itertools import product
    n, a, b, c, *l = map(int, open(0).read().split())
    k = ['A', 'B', 'C', 'D']
    cost = []
    for abcd in product(k, repeat=n):
        s, t, u = [], [], []
        for p, q in zip(abcd, l):
            if p == 'A':
                s.append(q)
            elif p == 'B':
                t.append(q)
            elif p == 'C':
                u.append(q)
        tmp = 0
        for p, q in zip([a, b, c], [s, t, u]):
            tmp += abs(p - sum(q)) + 10 * (len(q) - 1)

        if len(s) > 0 and len(t) > 0 and len(u) > 0:
            cost.append(tmp)

    ans = min(cost)
    print(ans)


if __name__ == '__main__':
    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: # 実質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) # A,B,Cどれにも使わない
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10 # Aの合成に使う
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10 # Bの合成に使う
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10 # Cの合成に使う
  
  return min(ret0, ret1, ret2, ret3)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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


    res = 10**20
    #各竹について0~3で場合分け
    for s in range(1<<(2*n)):
        l1 = []
        l2 = []
        l3 = []
        mp = 0
        #iセット目(i本目)
        for i in range(0, 2*n, 2):
            num = (s>>i) & 1 + ((s>>(i+1)) & 1)*2
            if num==1:
                l1.append(l[i//2])
            elif num==2:
                l2.append(l[i//2])
            elif num==3:
                l3.append(l[i//2])
        d, e, f = len(l1), len(l2), len(l3)
        if d==0 or e==0 or f==0:
            continue
        mp += (d+e+f-3)*10
        mp += abs(sum(l1)-a) + abs(sum(l2)-b) + abs(sum(l3)-c)
        res = min(res, mp)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,A,B,C = map(int,input().split())
l = [int(input()) 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 10**9
    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 _ in range(n)]

from collections import deque

ans = float('inf')

def dfs(i, abc, cost):
    global ans
    stack = deque([[i, abc, cost]])
    while stack:
        i, abc, cost = stack.pop()
        a, b, c = abc
        if i == n:
            if a * b * c:
                ans = min(ans, abs(A-a) + abs(B-b) + abs(C-c) + cost*10)
            continue
        for e in (0, 1, 2, 3):
            n_cost = cost
            n_abc = abc[:]
            if e < 3:
                if abc[e]:
                    n_cost += 1
                n_abc[e] += l[i]
            stack.append([i + 1, n_abc, n_cost])

dfs(0, [0,0,0], 0)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

ans = 0
mpa = mpb = mpc = 0
mp = [0,0,0]
INF = 10**4

groups = [[]*n for _ in range(3)]

def dfs(groups, parent=-1):
    groupa = groups[0]
    groupb = groups[1]
    groupc = groups[2]

    if parent == n-1:
        if len(groupa) > 0:mpa = 10 * (len(groupa)-1) + abs(sum(groupa)-a)
        else: mpa = INF

        if len(groupb) > 0:mpb = 10 * (len(groupb)-1) + abs(sum(groupb)-b)
        else: mpb = INF

        if len(groupc) > 0:mpc = 10 * (len(groupc)-1) + abs(sum(groupc)-c)
        else: mpc = INF

        return mpa+mpb+mpc

    else:
        parent+=1

        addl = [l[parent]]

        adda = dfs([groupa+addl ,groupb, groupc], parent)
        addb = dfs([groupa, groupb+addl, groupc], parent)
        addc = dfs([groupa, groupb, groupc+addl], parent)
        noadd = dfs([groupa,groupb,groupc],parent)

        return min(adda, addb, addc, noadd)

print(dfs(groups))

Submission status: Accepted

Solution code:
import math
import collections
from operator import mul
from functools import reduce
import bisect
import string

numbers = "0123456789"
alphabets = string.ascii_letters # a-z+A-Zをロード
characters = numbers + alphabets
def base_cvt(value, n=2):
    try:
        tmp = int(value)
    except:
        raise ValueError('Invalid value:', value)
 
    if n < 2 or n > len(characters):
        raise ValueError('Invalid n:', value)
    result = ''
    tmp = int(value)
    while tmp >= n:
        idx = tmp%n
        result = characters[idx] + result
        tmp = int(tmp / n)
    idx = tmp%n
    result = characters[idx] + result
    return result

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

def zeropad(s,i):
    while len(s)<i:
        s="0"+s
    return s


mp=10000000000000000
for i in range(4**n):
    A=0
    B=0
    C=0
    ai=0
    bi=0
    ci=0
    s=base_cvt(str(i),4)
    s=zeropad(s,n)
    for j in range(n):
        if s[j]=='1':
            A+=l[j]
            ai+=1
        elif s[j]=='2':
            B+=l[j]
            bi+=1
        elif s[j]=='3':
            C+=l[j]
            ci+=1
    if ai>0 and bi>0 and ci>0:
        mp=min(mp,10*((ai-1)+(bi-1)+(ci-1))+abs(A-a)+abs(B-b)+abs(C-c))


print(mp)

Submission status: Accepted

Solution code:
n,A,B,C=map(int,input().split())
l=[]
for _ in range(n):
    l.append(int(input()))
def solve(cur,a,b,c):
    if cur==n:
        #base case
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else float('INF')
    ret0=solve(cur+1,a,b,c)
    ret1=solve(cur+1,a+l[cur],b,c)+10
    ret2=solve(cur+1,a,b+l[cur],c)+10
    ret3=solve(cur+1,a,b,c+l[cur])+10
    return min(ret0,ret1,ret2,ret3)
print(solve(0,0,0,0))

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
X=[0,A,B,C]
L=[int(input()) for i in range(N)]
d=4**N
ans=float('inf')

for i in range(d):
  F=[0 for i in range(4)]
  cnt=[0 for i in range(4)]
  for j in range(N):
    F[i%4]+=L[j]
    cnt[i%4]+=1
    i //= 4
  p=True
  for k in range(1,4):
    if F[k]==0:
      p=False
      break
  tmp=0
  if p:
    for k in range(1,4):
      tmp+=cnt[k]*10+abs(X[k]-F[k])-10
    ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
n, a, b, c = map(int, input().split())
bamboo = [0]*n
for i in range(n):
  bamboo[i] = int(input())

answer = 10**10
for i in range(4**n):
  key = [0, 0, 0, 0]
  sub = [0, 0, 0]
  for j in range(n):
    k = 0
    if (i >> (2*j))&1:
      k += 1
    if (i >> (2*j+1))&1:
      k += 2
    key[k] += 1
    if k != 3:
      sub[k] += bamboo[j]
  if not all(sub):
    continue
  ans = (sum(key[:3])-3)*10+abs(sub[0]-a)+abs(sub[1]-b)+abs(sub[2]-c)
  if ans < answer:
    answer = ans
print(answer)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
X = [0, A, B, C]
L = [int(input()) for _ in range(N)]
d = 4 ** N
magic = int(1e+9)
for i in range(d):
  F = [0 for _ in range(4)]
  cnt = [0 for _ in range(4)]
  tmp = i
  for j in range(N):
    F[i%4] += L[j]
    cnt[i%4] += 1
    i //= 4
  p = True
  for k in range(1, 4):
    if F[k] == 0:
      p = False
      break
  tmpp = 0
  if p:
    for k in range(1, 4):
      tmpp += cnt[k] * 10 + abs(X[k] - F[k]) - 10
    if tmpp < magic:
      magic = tmpp
print(magic)

Submission status: Accepted

Solution code:
n,a,b,c = map(int,input().split())
l = [int(input()) for _ in range(n)]
def dfs(cur,x,y,z):
    if cur == n:
        return abs(a-x) + abs(b-y) + abs(c-z)-30 if min(x,y,z) > 0 else 10**9
    ret1 = dfs(cur+1,x,y,z)
    ret2 = dfs(cur+1,x+l[cur],y,z) + 10
    ret3 = dfs(cur+1,x,y+l[cur],z) + 10
    ret4 = dfs(cur+1,x,y,z+l[cur]) + 10
    return min(ret1,ret2,ret3,ret4)
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
# coding: utf-8
N,A,B,C=map(int,input().split())
L=[]
for i in range(N):
    L.append(int(input()))

def Base_10_to_n(X, base_n, len_N):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%base_n)+out
        X_dumy = int(X_dumy/base_n)
    return out.zfill(len_N)

ans=10**6

for i in range(4**N):
    bit=Base_10_to_n(i,4,N)
    group=[[] for j in range(4)]
    
    for j in range(N):
        group[int(bit[j])].append(L[j])
    
    if not(group[1]) or not(group[2]) or not(group[3]):
        continue
    
    costA = abs(A-sum(group[1])) + (len(group[1])-1)*10
    costB = abs(B-sum(group[2])) + (len(group[2])-1)*10
    costC = abs(C-sum(group[3])) + (len(group[3])-1)*10
    
    cost = costA + costB + costC
    
    ans=min(ans,cost)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(10**9)
def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
N, A, B, C = map(int, input().split())
L = []
for i in range(N):
    L.append(int(input()))
# L.sort()
def dfs(cnt, a, b, c):
    if cnt == N:
        return abs(A - a) + abs(B - b) + abs(C - c) - 30 if min(a,b,c) > 0 else 10**9
    r0 = dfs(cnt+1, a, b, c)
    r1 = dfs(cnt+1, a+L[cnt], b, c) + 10
    r2 = dfs(cnt+1, a, b+L[cnt], c) + 10
    r3 = dfs(cnt+1, a, b, c+L[cnt]) + 10
    return min(r0, r1, r2, r3)
    
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
INF=10**9
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:
        if min(x,y,z)>0:
            return abs(x-a)+abs(y-b)+abs(z-c)-30
        else:
            return INF
    ans=dfs(i+1,x,y,z)
    ant=dfs(i+1,x+l[i],y,z)+10
    anu=dfs(i+1,x,y+l[i],z)+10
    anv=dfs(i+1,x,y,z+l[i])+10
    return min(ans,ant,anu,anv)
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
# coding: utf-8
def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
    
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]
ans = float("inf")
for i in range(4**N):
    bits = Base_10_to_n(i, 4).zfill(N)
    a, b, c = 0, 0, 0
    cost = 0
    for j in range(len(bits)):
        if bits[j] == "0":
            pass
        elif bits[j] == "1":
            a += L[j]
            cost += 10
        elif bits[j] == "2":
            b += L[j]
            cost += 10
        else:
            c += L[j]
            cost += 10
    if min(a, b, c) > 0:
        ans = min(ans, cost + abs(a-A)+abs(b-B)+abs(c-C) - 10*3)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
INF=10**9
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
def dfs(i,x,y,z,m):
    if i==n:
        if x>0 and y>0 and z>0:
            return abs(x-a)+abs(y-b)+abs(z-c)+m
        else:
            return INF
    ans=INF
    if x==0:
        ans=min(dfs(i+1,l[i],y,z,m),ans)
    else:
        ans=min(dfs(i+1,x+l[i],y,z,m+10),ans)
    if y==0:
        ans=min(dfs(i+1,x,l[i],z,m),ans)
    else:
        ans=min(dfs(i+1,x,y+l[i],z,m+10),ans)
    if z==0:
        ans=min(dfs(i+1,x,y,l[i],m),ans)
    else:
        ans=min(dfs(i+1,x,y,z+l[i],m+10),ans)
    return min(ans,dfs(i+1,x,y,z,m))
print(dfs(0,0,0,0,0))

Submission status: Accepted

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    ans = INF

    selects = list(itertools.product(range(4), repeat=n))

    for select in selects:
        mp = -30
        bamboo_length = [0] * 3
        for i, num in enumerate(select):
            if num != 3:
                bamboo_length[num] += l[i]
                mp += 10

        for length in bamboo_length:
            if length == 0:
                break
        else:
            mp += abs(a - bamboo_length[0])
            mp += abs(b - bamboo_length[1])
            mp += abs(c - bamboo_length[2])
            ans = min(mp, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# import bisect
from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    ans = INF

    base_idx = list(itertools.permutations(range(n), r=3))

    for bi in base_idx:
        bamboo_length = [0] * 3
        add_bamboo = list(itertools.product(range(4), repeat=(n-3)))
        rem_idx = [i for i in range(n) if i not in bi]
        for ai in add_bamboo:
            mp = 0
            bamboo_length[0] = l[bi[0]]
            bamboo_length[1] = l[bi[1]]
            bamboo_length[2] = l[bi[2]]
            for idx, num in enumerate(ai):
                if num != 3:
                    bamboo_length[num] += l[rem_idx[idx]]
                    mp += 10
            mp += abs(a - bamboo_length[0])
            mp += abs(b - bamboo_length[1])
            mp += abs(c - bamboo_length[2])
            ans = min(mp, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

def main():
    ans = 10 ** 9
    N, A, B, C = map(int, input().split())
    l = []
    for _ in range(N):
        l.append(int(input()))
    for i in range(4 ** N):
        group = []
        for j in range(N):
            k = i
            for _ in range(j):
                k //= 4
            group.append(k % 4)
        sm = [0] * 3
        for j in range(N):
            if group[j] < 3:
                sm[group[j]] += l[j]
        if min(sm) > 0:
            ans = min(ans, 10 * (N - group.count(3) - 3) + sum(abs(i - j) for i, j in zip(sorted(sm), [C, B, A])))
    print(ans)


main()

Submission status: Accepted

Solution code:
n, a, b, c = [int(e) for e in input().split()]
L = [int(input()) for i in range(n)]

def dfs(A, B, C, O, lst, mi):
    if len(lst) == 0:
        if len(A) == 0 or len(B) == 0 or len(C) == 0:
            return mi

        mp = 0
        mp += (len(A) - 1)*10 + abs(a - sum(A))
        mp += (len(B) - 1)*10 + abs(b - sum(B))
        mp += (len(C) - 1)*10 + abs(c - sum(C))
        return min(mp, mi)

    l = lst.pop()
    mi = dfs(A + [l], B.copy(), C.copy(), O.copy(), lst.copy(), mi)
    mi = dfs(A.copy(), B + [l], C.copy(), O.copy(), lst.copy(), mi)
    mi = dfs(A.copy(), B.copy(), C + [l], O.copy(), lst.copy(), mi)
    mi = dfs(A.copy(), B.copy(), C.copy(), O + [l], lst.copy(), mi)

    return mi

def main():
    print(dfs([], [], [], [], L.copy(), float('inf')))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N,A,B,C = map(int,input().split())
    l = [int(input()) for _ in range(N)]
    
    def point(x,y):
        con = len(x)-1
        s = sum(x)
        return con*10+abs(y-s)
    
    ans = 10**8
    for i in range(4**N):
        num = i
        use = []
        base = 1
        bam = [[] for _ in range(4)]
        for j in range(N):
            use.append(num%4)
            num //= 4
        for k in range(N):
            bam[use[k]].append(l[k])
        if len(bam[1])*len(bam[2])*len(bam[3]) == 0:
            continue
        else:
            p = point(bam[1],A)+point(bam[2],B)+point(bam[3],C)
            ans = min(ans,p)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
L=[int(input()) for i in range(N)]
INF=10**8
def dfs(n,a,b,c):
  #n:n番目の竹までをみる
  #a:Aに使う竹の合計
  #b:Bに使う竹の合計
  #c:Cに使う竹の合計
  if n==N:
    if a*b*c>0:
      ret=abs(A-a)+abs(B-b)+abs(C-c)-30
    else:
      ret=INF
  else:
    ret=dfs(n+1,a,b,c)
    reta=dfs(n+1,a+L[n],b,c)+10
    retb=dfs(n+1,a,b+L[n],c)+10
    retc=dfs(n+1,a,b,c+L[n])+10
    ret = min(ret,reta,retb,retc)
  return ret
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
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 f_inf

    ret0 = dfs(i + 1, a, b, c)
    ret1 = dfs(i + 1, a + l[i], b, c) + 10
    ret2 = dfs(i + 1, a, b + l[i], c) + 10
    ret3 = dfs(i + 1, a, b, c + l[i]) + 10

    return min(ret0, ret1, ret2, ret3)


n, A, B, C = map(int, input().split())
l = list(int(input()) for _ in range(n))
f_inf = float("inf")
print(dfs(0, 0, 0, 0))