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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    def dfs(cursor, a, b, c):
        if cursor == N:
            return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF

        no_compound_pattern = dfs(cursor+1, a, b, c)
        compound_a_pattern = dfs(cursor+1, a + l[cursor], b, c) + 10
        compound_b_pattern = dfs(cursor+1, a, b + l[cursor], c) + 10
        compound_c_pattern = dfs(cursor+1, a, b, c + l[cursor]) + 10

        return min(no_compound_pattern, compound_a_pattern, compound_b_pattern, compound_c_pattern)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,a,b,c=map(int,input().split())
    L=[int(input()) for _ in range(n)]

    def dfs(v,Idx)->int:
        # terminate condition
        if(v==n):
            score=0
            Idx=tuple(Idx)
            A,B,C=[],[],[]
            for i,k in enumerate(Idx):
                if(k==0): A.append(L[i])
                elif(k==1): B.append(L[i])
                elif(k==2): C.append(L[i])
            if((not A) or (not B) or (not C)): return INF # 1つも竹が無いのはダメ
            score+=(len(A)+len(B)+len(C)-3)*10

            SA=sum(A)
            SB=sum(B)
            SC=sum(C)
            score+=abs(SA-a)
            score+=abs(SB-b)
            score+=abs(SC-c)
            return score
            
        res=INF
        for i in range(4):
            Idx[v]=i
            res=min(res,dfs(v+1,Idx))
        return res

    print(dfs(0,[0]*n))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,a,b,c=map(int,input().split())
    L=[int(input()) for _ in range(n)]

    def dfs(v,Idx)->int:
        # terminate condition
        if(v==n):
            score=0
            Idx=tuple(Idx)
            A,B,C=[],[],[]
            for i,k in enumerate(Idx):
                if(k==0): A.append(L[i])
                elif(k==1): B.append(L[i])
                elif(k==2): C.append(L[i])
            if((not A) or (not B) or (not C)): return INF # 1つも竹が無いのはダメ
            score+=(len(A)+len(B)+len(C)-3)*10

            SA=sum(A)
            SB=sum(B)
            SC=sum(C)
            score+=abs(SA-a)
            score+=abs(SB-b)
            score+=abs(SC-c)

            return score

        res=INF
        for i in range(4):
            res=min(res,dfs(v+1,Idx+[i]))
        return res

    print(dfs(0,[]))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,a,b,c=map(int,input().split())
    L=[int(input()) for _ in range(n)]
    ans=INF
    from itertools import product
    for I in product(range(4),repeat=n):
        score=0
        I=tuple(I)
        A,B,C=[],[],[]
        for i,k in enumerate(I):
            if(k==0): A.append(L[i])
            elif(k==1): B.append(L[i])
            elif(k==2): C.append(L[i])
        if((not A) or (not B) or (not C)): continue # 1つも竹が無いのはダメ
        score+=(len(A)+len(B)+len(C)-3)*10

        SA=sum(A)
        SB=sum(B)
        SC=sum(C)
        score+=abs(SA-a)
        score+=abs(SB-b)
        score+=abs(SC-c)
        ans=min(ans,score)
    print(ans)
resolve()

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(t,a,b,c):
    if t == n:
        if min(a,b,c)>0: return abs(a-A)+abs(b-B)+abs(c-C)-30
        else: return inf
    ret0 = dfs(t+1,a,b,c)
    ret1 = dfs(t+1,a+l[t],b,c)+10
    ret2 = dfs(t+1,a,b+l[t],c)+10
    ret3 = dfs(t+1,a,b,c+l[t])+10
    return min(ret0,ret1,ret2,ret3)

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

Submission status: Accepted

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

def dfs(bamboo_number,a,b,c):
    #停止条件
    #深さに限らず，任意の停止条件を書く
    if bamboo_number == N:
        #合成完了　長さを調整
        if min(a,b,c) > 0:
            return abs(a-A)+abs(b-B)+abs(c-C) - 30 #最初の1本分の合成コストは無料なので-10 *3
        else:
            return INF
        
    # pos (bamboo_number)を進めながら（末端に進みながら）分岐処理
    # 末端まで到達した時それぞれの分岐から値が返される
    # for 文で書ける場合は for 文で実装
    ret1 = dfs(bamboo_number+1,a,b,c);
    ret2 = dfs(bamboo_number+1,a+l[bamboo_number],b,c) + 10
    ret3 = dfs(bamboo_number+1,a,b+l[bamboo_number],c) + 10
    ret4 = dfs(bamboo_number+1,a,b,c+l[bamboo_number]) + 10

    #それぞれの分岐からの戻り値の処理を行う関数
    return min(ret1, ret2, ret3, ret4)

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

Submission status: Accepted

Solution code:
n, a, b, c = map(int, input().split())
ABC = [a, b, c]
l = []
for i in range(n):
	l.append(int(input()))
# = input()
# = list(map(int, input().split()))

mi = -1
for i in range(4**n):
	j = i
	p = []
	m = n-1
	while m >= 0:
		p.append(j//(4**m))
		j = j%(4**m)
		m -= 1
	abc = [0 for k in range(3)]
	cnt = -30
	for k in range(n):
		if p[k] != 3:
			cnt += 10
			abc[p[k]] += l[k]
	if 0 not in abc:
		for k in range(3):
			cnt += abs(ABC[k] - abc[k])
		if mi == -1:
			mi = cnt
		else:
			mi = min(cnt, mi)
print(mi)

Submission status: Accepted

Solution code:
n,A,B,C=map(int,input().split())
L=[]
r=10000
for i in range(n):
	l=int(input())
	L.append(l)
def k(i,a,b,c,s):
	global r
	if i==n:
		if a!=A and b!=B and c!=C:
			s+=abs(a)+abs(b)+abs(c)-30
			r=min(r,s)
	else:
		k(i+1,a-L[i],b,c,s+10)
		k(i+1,a,b-L[i],c,s+10)
		k(i+1,a,b,c-L[i],s+10)
		k(i+1,a,b,c,s)
a=A
b=B
c=C
k(0,a,b,c,0)
print(r)

Submission status: Accepted

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

ans=[]
for i in range(4**N):
  A=[]
  B=[]
  C=[]
  p=i
  for j in range(N):
    if p%4==1:
      A.append(l[j])
    elif p%4==2:
      B.append(l[j])
    elif p%4==3:
      C.append(l[j])
    p=(p-p%4)//4
  if len(A)>0 and len(B)>0 and len(C)>0:
    ans.append(abs(sum(A)-a)+10*(len(A)-1)+abs(sum(B)-b)+10*(len(B)-1)+abs(sum(C)-c)+10*(len(C)-1))
    
print(min(ans))

Submission status: Accepted

Solution code:
n,a,b,c=map(int,input().split())
l=[]
for i in range(n):
	x=int(input())
	l.append(x)
def tet(x):
	s=""
	for i in range(n):
		if x%4==0:
			s+="0"
		elif x%4==1:
			s+="1"
		elif x%4==2:
			s+="2"
		else:
			s+="3"
		x//=4
	return s[::-1]
ans=10**25
for i in range(4**n):
	q=tet(i)
	A=B=C=0
	AA=BB=CC=0
	for j in range(n):
		if q[j]=="0":
			A+=l[j]
			AA+=1
		elif q[j]=="1":
			B+=l[j]
			BB+=1
		elif q[j]=="2":
			C+=l[j]
			CC+=1
	if AA==0 or BB==0 or CC==0:
		continue
	cnt=0
	cnt+=(AA+BB+CC-3)*10
	cnt+=abs(A-a)+abs(B-b)+abs(C-c)
	ans=min(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
inpl = lambda: list(map(int,input().split()))
N, A, B, C = inpl()
L = [int(input()) for _ in range(N)]
ABC = [A,B,C]

ans = 10000
for dist in itertools.product(range(4),repeat=N):
    n = [0]*3
    l = [0]*3
    for i in range(N):
        k = dist[i]
        if k < 3:
            n[k] += 1
            l[k] += L[i]
    for k in range(3):
        if n[k] == 0:
            break
    else:
        p = (sum(n)-3)*10 + sum(abs(ABC[k]-l[k]) for k in range(3))
        if p < ans:
            ans = p
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())
INF = 10 ** 9


def dfs(times, a, b, c):  #  a,b,c:現在の竹の長さ
    if times == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    # 適切な竹に対して、(A or B or Cに合成する) or (使わない)の場合に分ける
    no_pattern = dfs(times + 1, a, b, c)
    a_pattern = dfs(times + 1, a + L[times], b, c) + 10
    b_pattern = dfs(times + 1, a, b + L[times], c) + 10
    c_pattern = dfs(times + 1, a, b, c + L[times]) + 10

    return min(no_pattern, a_pattern, b_pattern, c_pattern)


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 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(x) for x in input().split()]
L = [int(input()) for _ in range(N)]
INF = 10**8
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)
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)]

ret = float('inf')

def mp(x, target) :
    ret = -10
    long = 0
    for i in range(N) :
        if x & 1 :
            ret += 10
            long += l[i]
        x >>= 1
    ret += abs(long - target)
    return ret

for i in range(1, 1 << N) :
    for j in range(1, 1 << N) :
        if i & j :
            continue
        for k in range(1, 1 << N) :
            if i & k or j & k :
                continue
            ret = min(ret, mp(i, A) + mp(j, B) + mp(k, C))

print(ret)

Submission status: Accepted

Solution code:
#解き方が全然思いつかなかったので、少しでも再帰の書き方に慣れようと他の人の答えを参考にした
N,A,B,C = map(int,input().split())
l = []
for i in range(N):
  l.append(int(input()))

def dfs(dep,a,b,c):
    if dep == N:
        if min(a,b,c) > 0:
          #伸縮させるコストの計算
            return abs(a-A)+abs(b-B)+abs(c-C) - 30
        else:
            return 10**9
    #各A,B,Cが合成する、合成しないの4つパターンからNに対して行う 4**Nになる
    numA = dfs(dep+1,a+l[dep],b,c) + 10
    numB = dfs(dep+1,a,b+l[dep],c) + 10
    numC = dfs(dep+1,a,b,c+l[dep]) + 10
    numX = dfs(dep+1,a,b,c)
    return min(numA,numB,numC,numX)
print(dfs(0,0,0,0))

Submission status: Accepted

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

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:
        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)
    retA = DFS(cur+1, a+l[cur], b, c) + 10
    retB = DFS(cur+1, a, b+l[cur], c) + 10
    retC = DFS(cur+1, a, b, c+l[cur]) + 10
    return min(ret0, retA, retB, retC)

print(DFS(0, 0, 0, 0))

Submission status: Accepted

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

lst = []

min_mp = 100000000

def check_mp(lst):

        global a,b,c
        global L

        len_A=0
        len_B=0
        len_C=0

        cnt_A=0
        cnt_B=0
        cnt_C=0

        for i in range(len(lst)):
                if lst[i] == "a":
                        cnt_A += 1
                        len_A += L[i]
                if lst[i] == "b":
                        cnt_B += 1
                        len_B += L[i]
                if lst[i] == "c":
                        cnt_C += 1
                        len_C += L[i]

        if cnt_A==0 or cnt_B==0 or cnt_C==0:
                return 10000000000




        difA = abs(len_A - A)
        difB = abs(len_B - B)
        difC = abs(len_C - C)

        diff = difA+difB+difC

        synth_mp = 10 * (cnt_A+cnt_B+cnt_C - 3)

        return diff + synth_mp


def nxt():
        global N
        global lst
        global min_mp

        if len(lst) == N:
                mp = check_mp(lst)

                if mp < min_mp:
                        min_mp = mp
                return

        lst.append("a")
        nxt()
        lst.pop(-1)

        lst.append("b")
        nxt()
        lst.pop(-1)

        lst.append("c")
        nxt()
        lst.pop(-1)

        lst.append("N")
        nxt()
        lst.pop(-1)

        return


nxt()

print(min_mp)

Submission status: Accepted

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

ans = 10 ** 10
for i in range(4**N):
    a = 0
    l = [0, 0, 0]
    for n in range(N):
        x = i % 4
        i //= 4
        if x == 3:
            continue
        if l[x] > 0:
            a += 10
        l[x] += L[n]

    if l[0] == 0 or l[1] == 0 or l[2] == 0:
        continue

    a += abs(l[0]-A) + abs(l[1]-B) + abs(l[2]-C)
    ans = min(a, ans)

print(ans)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import itertools
    input = sys.stdin.readline
    n, a, b, c = list(map(int, input().rstrip('\n').split()))
    l = [int(input().rstrip('\n')) for _ in range(n)]
    mt = 10 ** 10
    for v in itertools.product([i for i in range(4)], repeat=n):
        nl = [[] for _ in range(4)]
        for i, vv in enumerate(v):
            nl[vv].append(l[i])
        if len(nl[1]) != 0 and len(nl[2]) != 0 and len(nl[3]) != 0:
            t = 0
            t += ((len(nl[1]) - 1) * 10 + abs(a - sum(nl[1])))
            t += ((len(nl[2]) - 1) * 10 + abs(b - sum(nl[2])))
            t += ((len(nl[3]) - 1) * 10 + abs(c - sum(nl[3])))
            mt = min(t, mt)
    print(mt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n,a,b,c=map(int,input().split())
l=[]
for i in range(n):
    l.append(int(input()))
op=[[0],[1],[2],[3]]
for i in range(n-1):
    tmp=[]
    for j in op:
        tmp.append(j+[0])
        tmp.append(j+[1])
        tmp.append(j+[2])
        tmp.append(j+[3])
    op=tmp
ans=1000000000
for i in op:
    ta=0
    tb=0
    tc=0
    mp=0
    for j in range(len(i)):
        if i[j]==0:
            if ta!=0:
                mp+=10
            ta+=l[j]        
        elif i[j]==1:
            if tb!=0:
                mp+=10
            tb+=l[j]
        elif i[j]==2:
            if tc!=0:
                mp+=10
            tc+=l[j]
    mp+=abs(a-ta)+abs(b-tb)+abs(c-tc)
    if ta==0 or tb==0 or tc==0:
        mp=1000000000
    ans=min(ans,mp)
print(ans)

Submission status: Accepted

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

ans = float('inf')
for mask in range(pow(4, N)):
    cost = 0
    for i, l in enumerate([A, B, C]):
        grp = []
        for digit in range(N):
            if mask // pow(4, digit) % 4 == i:
                grp.append(L[digit])

        if not grp:
            cost = float('inf')

        cost += (len(grp) - 1) * 10
        cost += abs(l - sum(grp))
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
#解説見ながら作った。
#DFSで行う。停止条件・分岐処理の二つが大枠。

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

    #curはcurrentのことで現在の状態
def dfs(cur, a, b, c):
    
    '''
    停止条件(終端処理)
    深さに限らず，任意の停止条件を書く
    
    深さがNだったら使用MPを評価
    1本も竹を使用していなかったら棄却→MPを無限に使うこととしている
    
    (-30って引いてるのは、最初の 1 本目は合体コストなし、
    2 本目からはコスト 10 かかるため、その1本目のコストの分
    を加えてしまっているため、それを引いている（たぶん）)
    '''
    if cur == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF


    '''
    cur(current) を進めながら,（末端に進みながら）分岐処理
    末端まで到達した時それぞれの分岐から値が返される
    for 文で書ける場合は for 文で実装
    
    cur番目の竹に対して
        ret0:ABCどれにも使わない
        ret1:Aに使う（合成:MP+10）
        ret2:Bに使う（合成:MP+10）
        ret3:Cに使う（合成:MP+10）
    '''
    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 i in range(N)]
M=[A,B,C]
M.sort()

ans=10**10
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      X=[L[i],L[j],L[k]]
      Y=[]
      for l in range(N):
        if l!=i and l!=j and l!=k:
          Y.append(L[l])
      #print(X,Y)
      
      for m in range(4**len(Y)):
        tmp=0
        mm=m
        XX=[L[i],L[j],L[k]]
        for n in range(len(Y)):
          mmm=mm%4
          if mmm!=0:
            XX[mmm-1]+=Y[n]
            tmp+=10
          mm=(mm-mmm)//4
        XX.sort()
        #print(XX)
        tmp+=abs(XX[0]-M[0])+abs(XX[1]-M[1])+abs(XX[2]-M[2])
        ans=min(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
def MP(lA,nA,lB,nB,lC,nC):
    res=0
    res+=abs(lA-A)+abs(lB-B)+abs(lC-C)
    res+=(nA+nB+nC-3)*10
    return res

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

ans=2**31-1

for k in range(1<<(2*N)): # kは0~4^N-1,2進で2N桁以下
    lA=lB=lC=0 # 各長さの竹を作るの使う竹の長さの初期値の合計
    nA=nB=nC=0 # 各長さの竹を作るのに使う竹の本数
    for i in range(N):
        ti=(k//(4**i))%4 # kの下から2i桁目，2i+1桁目
        if ti==1: # 長さliの竹を長さAの竹に使用
            lA+=l[i]
            nA+=1
        elif ti==2: # B
            lB+=l[i]
            nB+=1
        elif ti==3: # C
            lC+=l[i]
            nC+=1
    if nA>0 and nB>0 and nC>0:
        ans=min(ans,MP(lA,nA,lB,nB,lC,nC))

print(ans)

Submission status: Accepted

Solution code:
INF = pow(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 + length[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + length[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + length[cur]) + 10
    return min(ret0, ret1, ret2, ret3)

if __name__ == '__main__':
    N, A, B, C = map(int, input().split())
    length = [int(input()) for i in range(N)]
    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)]
data=[[[],[],[],[]] for i in range(4**n)]
inf=float("inf")
for i in range(4**n):
    k=i
    for j in range(n):
        m=k//4**(n-1-j)
        if m>0:
            data[i][m].append(j)
            k%=4**(n-1-j)
        else:
            data[i][0].append(j)
            
ans=inf
for h in data:
    if h[0] and h[1] and h[2]:
        count=0
        
        count+=(len(h[0])-1)*10
        count+=(len(h[1])-1)*10
        count+=(len(h[2])-1)*10
        
        s=0
        for i in h[0]:
            s+=l[i]
        count+=abs(s-a)
        
        s=0
        for i in h[1]:
            s+=l[i]
        count+=abs(s-b)
        
        s=0
        for i in h[2]:
            s+=l[i]
        count+=abs(s-c)
        
        ans=min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
"""
できなかった

- 操作 = 四則演算 or 関数
- 交換法則などが成り立つかどうか確認する必要がある
- 再帰的(dfs)に実装する場合、何を初期値として終了条件とするかの理解が必要
  - 前提として全探索であること => 1の解に収束する必要がない
    全ての葉を訪れたときに最小・最大値・解への到達が判定できれば良い

- dfsの実装: いまどの高さにいるかを引数として渡す = 何を高さとして定義するか
  - 階層のインデックスは選択可能な配列のインデックス
  - 同階層のノードは選択肢
  - ノードが持つ値は、その選択をした時の合計の値
  - 終了条件A, B, Cを満たす

- 求める長さA, B, Cの竹 -> 選択肢

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


def dfs(index, a, b, c):
    if N == index:
        if 0 < min(a, b, c):
            return abs(a - A) + abs(b - B) + abs(c - C) - 30
        else:
            return 10 ** 9
    costs = []
    costs.append(dfs(index + 1, a, b, c))
    costs.append(dfs(index + 1, a + l[index], b, c) + 10)
    costs.append(dfs(index + 1, a, b + l[index], c) + 10)
    costs.append(dfs(index + 1, a, b, c + l[index]) + 10)
    return min(costs)


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

Submission status: Accepted

Solution code:
# ABC119C - Synthetic Kadomatsu
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(cur: int, x: int, y: int, z: int) -> int:
    if cur == N:
        if min(x, y, z):
            return abs(x - A) + abs(y - B) + abs(z - C) - 30
        else:
            return 1 << 60
    patterns = []
    patterns.append(dfs(cur + 1, x, y, z))
    patterns.append(dfs(cur + 1, x + L[cur], y, z) + 10)
    patterns.append(dfs(cur + 1, x, y + L[cur], z) + 10)
    patterns.append(dfs(cur + 1, x, y, z + L[cur]) + 10)
    return min(patterns)


def main():
    global N, A, B, C, L
    N, A, B, C, *L = map(int, open(0).read().split())
    ans = dfs(0, 0, 0, 0)
    print(ans)


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(i,x,y,z):
  if i==n:
    return abs(x-a)+abs(y-b)+abs(z-c) if x*y*z else 10**9
  r1 = dfs(i+1,x+l[i],y,z)+ (10 if x>0 else 0)
  r2 = dfs(i+1,x,y+l[i],z)+ (10 if y>0 else 0)
  r3 = dfs(i+1,x,y,z+l[i])+ (10 if z>0 else 0)
  r4 = dfs(i+1,x,y,z)
  return min(r1,r2,r3,r4)

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)]
answer = a+b+c
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)
  
for i in range(1, 4**n):
  aa = []
  bb = []
  cc = []
  four = list(str(Base_10_to_n(i,4).zfill(n)))
  
  if four.count("1")==0 or four.count("2")==0 or four.count("3") ==0:
    continue
  for index,f in enumerate(four) :
    if f == "0": #使わない
      continue
    elif f == "1":
      aa.append(l[index])
    elif f == "2":
      bb.append(l[index])
    elif f == "3":
      cc.append(l[index])
    else:
      break
  cur = (len(aa)-1)*10+abs(a-sum(aa))+(len(bb)-1)*10+abs(b-sum(bb))+(len(cc)-1)*10+abs(c-sum(cc))
  answer = min(answer, cur)


  
print(answer)

Submission status: Accepted

Solution code:
N, A, B, C = map(int,input().split(' '))
l = []
for i in range(N):
    l.append(int(input()))
#print(l)
def baseN(nums,base,maxketa):
    ans = ""
    for i in range(maxketa-1,-1,-1):
        ans+=str(nums//pow(base,i))
        nums=nums%pow(base,i)
        #print(i,ans,nums)
    return(ans)

#print(baseN(1021,2,10))
#print(baseN(pow(4,N)-1,4,N))
allsel=[]
for i in range(pow(4,N)):
    allsel.append(baseN(i,4,N))

mincost=3*1000
for key in allsel:
    #print(key)
    a0=[]
    b1=[]
    c2=[]
    x3=[]

    for i in range(len(key)):
        if key[i] == '0':
            a0.append(l[i])
        elif key[i] == '1':
            b1.append(l[i])
        elif key[i] == '2':
            c2.append(l[i])
        else:
            x3.append(l[i])
    #print(key,a0,b1,c2,x3)     
    costA = abs(sum(a0)-A)+10*(len(a0)-1)
    costB = abs(sum(b1)-B)+10*(len(b1)-1)
    costC = abs(sum(c2)-C)+10*(len(c2)-1)
    if len(a0) >= 1 and len(b1) >= 1 and len(c2) >= 1 :
        #print(a0,b1,c2,costA,costB,costC)
        mincost=min(mincost,costA+costB+costC)

print(mincost)

Submission status: Accepted

Solution code:
import itertools
N,A,B,C=map(int,input().split())
l = [int(input()) for _ in range(N)]
ans = 10**9
lis = itertools.product([0,1,2,3],repeat=N)
for i in lis:
    At=0; Bt=0; Ct=0
    Al=0; Bl=0; Cl=0
    cnt=0
    for j in range(N):
        if i[j]==1:
            At+=1
            Al+=l[j]
        if i[j]==2:
            Bt+=1
            Bl+=l[j]
        if i[j]==3:
            Ct+=1
            Cl+=l[j]
    if At*Bt*Ct==0:
        continue
    ans = min(ans,abs(Al-A)+abs(Bl-B)+abs(Cl-C)+(At+Bt+Ct-3)*10)
print(ans)

Submission status: Accepted

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

for _ in range(n):
    l.append(int(input()))
 
ind = 2**(2*n)
ans = 10000000

for i in range(ind):
    use = [[] for _ in range(4)]
    for j in range(n):
        t = (i>>(2*j))&3
        use[t].append(l[j])
        ax = sum(use[0])
        bx =sum(use[1])
        cx = sum(use[2])
        tmp = abs(a-ax) + abs(b-bx) + abs(c-cx) + 10*len(use[0]) -10 + 10*len(use[1]) - 10 + 10*len(use[2]) - 10
        if tmp<ans and len(use[0]) and len(use[1]) and len(use[2]):
            
            ans = tmp
print(ans)

Submission status: Accepted

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


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

    def dfs(cursor, a, b, c):
        if cursor == N:
            return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a, b, c) > 0 else INF

        no_compound_pattern = dfs(cursor+1, a, b, c)
        compound_a_pattern = dfs(cursor+1, a+l[cursor], b, c) + 10
        compound_b_pattern = dfs(cursor+1, a, b+l[cursor], c) + 10
        compound_c_pattern = dfs(cursor+1, a, b, c+l[cursor]) + 10

        return min(no_compound_pattern, compound_a_pattern, compound_b_pattern, compound_c_pattern)

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

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

# ABCのいずれかの竹の材料にするか、使わないかの4通りを全ての竹に対して試す
appli = ["A", "B", "C", "D"]
appli = list(itertools.product(appli, repeat=N))

# 目的の竹と、その材料リストを入力すると、必要MPを返す関数
def need_MP_for_one_bamboo(X, bamboo_list):
    return 10*(len(bamboo_list)-1) + abs(sum(bamboo_list)-X)

# N本の竹の用途パターンを入力すると必要MPを返す関数
def need_MP_for_pattern(appli_pattern):
    bamboo_for_A = []
    bamboo_for_B = []
    bamboo_for_C = []
    for idx in range(len(appli_pattern)):
        if appli_pattern[idx] == "A":
            bamboo_for_A.append(l[idx])
        elif appli_pattern[idx] == "B":
            bamboo_for_B.append(l[idx])
        elif appli_pattern[idx] == "C":
            bamboo_for_C.append(l[idx])
            
    # A,B,Cいずれかにおいて、材料となる竹が1本もない場合
    if not (bamboo_for_A and bamboo_for_B and bamboo_for_C):
        return float("inf")
    else:
        return need_MP_for_one_bamboo(A, bamboo_for_A) + need_MP_for_one_bamboo(B, bamboo_for_B) + need_MP_for_one_bamboo(C, bamboo_for_C)
        
            

# 用途全パターンについて必要MPを計算し、最小のものを出力する
ans = float("inf")
for appli_pattern in appli:
    ans = min(ans, need_MP_for_pattern(appli_pattern))

print(ans)

Submission status: Accepted

Solution code:

def Synthetic_Kadomatsu_dfs(l, depth, a, b, c, N, A, B, C):
    if depth == N: return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a,b,c) > 0 else float('INF')

    ret0 = Synthetic_Kadomatsu_dfs(l, depth+1, a, b, c, N, A, B, C)
    ret1 = Synthetic_Kadomatsu_dfs(l, depth + 1, a + l[depth], b, c, N, A, B, C)+10
    ret2 = Synthetic_Kadomatsu_dfs(l, depth + 1, a, b + l[depth], c, N, A, B, C)+10
    ret3 = Synthetic_Kadomatsu_dfs(l, depth + 1, a, b, c + l[depth], N, A, B, C)+10
    return min(ret0,ret1,ret2,ret3)

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

    print(Synthetic_Kadomatsu_dfs(l, 0, 0, 0, 0, N, A, B, C))



if __name__ == "__main__":
    Synthetic_Kadomatsu()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from copy import copy
sys.setrecursionlimit(1000000)
N,A,B,C = map(int,input().split())
L = [int(input()) for _ in range(N)]

def dfs(x,a,b,c):
    if x == N:
        return abs(a-A)+abs(b-B)+abs(c-C) - 30 if min(a,b,c) > 0 else 1000000000
    ret0 = dfs(x+1,a,b,c)
    ret1 = dfs(x+1,a+L[x],b,c) + 10
    ret2 = dfs(x+1,a,b+L[x],c) + 10
    ret3 = dfs(x+1,a,b,c+L[x]) + 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().split()))
L = []
for i in range(N):
    L.append(int(input()))

# print(N,A,B,C,L)

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:
from collections import deque

def dfs():
  queue = deque()
  queue.append([0,[0]])
  queue.append([0,[1]])
  queue.append([0,[2]])
  queue.append([0,[3]])
  
  grps = []
  while len(queue) != 0:
    idx, Llist = queue.pop()
    if idx == N-1:
      grps.append(Llist)
    else:
      queue.append([idx+1,Llist+[0]])
      queue.append([idx+1,Llist+[1]])
      queue.append([idx+1,Llist+[2]])
      queue.append([idx+1,Llist+[3]])
  return grps

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

ans = float('inf')
for grp in grps:
  A_mem = []
  B_mem = []
  C_mem = []
  for idx, val in enumerate(grp):
    if val == 0:A_mem.append(L[idx])
    elif val == 1:B_mem.append(L[idx])
    elif val == 2:C_mem.append(L[idx])
    
  len_A_mem, len_B_mem, len_C_mem = len(A_mem), len(B_mem), len(C_mem)  
  if 0 in [len_A_mem, len_B_mem, len_C_mem]: continue
  else:
    pt = (sum([len_A_mem,len_B_mem, len_C_mem]) -3)*10
    pt += abs(sum(A_mem)-A) + abs(sum(B_mem)-B) + abs(sum(C_mem)-C)
    ans = min(ans, pt)
print(ans)