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:
#encoding: utf-8

import sys

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

def dfs(idx, a, b, c):
    if idx == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else sys.maxsize
    
    ret0 = dfs(idx + 1, a, b, c)
    ret1 = dfs(idx + 1, a + l[idx], b, c) + 10
    ret2 = dfs(idx + 1, a, b + l[idx], c) + 10
    ret3 = dfs(idx + 1, a, b, c + l[idx]) + 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 = [int(input()) for _ in range(N)]
INF = 10**12

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

    res1 = dfs(depth + 1, a, b, c)
    res2 = dfs(depth + 1, a + l[depth], b, c) + 10
    res3 = dfs(depth + 1, a, b + l[depth], c) + 10
    res4 = dfs(depth + 1, a, b, c + l[depth]) + 10

    return min(res1, res2, res3, res4)

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

Submission status: Accepted

Solution code:
#coding:utf-8
import sys

BAMB_NUM = 0
BAMB_A = 0
BAMB_B = 0
BAMB_C = 0
BAMB_LIST = []

def calcMP(idx, lenA, lenB, lenC):
    """
    calculate MP.
    """
    # when classified all bamboos
    if (idx == BAMB_NUM):
        return abs(lenA - BAMB_A) + abs(lenB - BAMB_B) + abs(lenC - BAMB_C) - 30 if min(lenA, lenB, lenC) > 0 else sys.maxsize
    
    # don't use idx-th bamboo
    mp1 = calcMP(idx + 1, lenA, lenB, lenC)
    # use idx-th bamboo
    mp2 = calcMP(idx + 1, lenA + BAMB_LIST[idx], lenB, lenC) + 10
    mp3 = calcMP(idx + 1, lenA, lenB + BAMB_LIST[idx], lenC) + 10
    mp4 = calcMP(idx + 1, lenA, lenB, lenC + BAMB_LIST[idx]) + 10

    return min(mp1, mp2, mp3, mp4)

if __name__ == "__main__":
    """
    http://drken1215.hatenablog.com/entry/2019/02/24/224100
    """
    # requested bamboo lengths
    BAMB_NUM, BAMB_A, BAMB_B, BAMB_C = map(lambda x: int(x), input().split())
    # available bamboo lengths
    for bamb in range(BAMB_NUM):
        BAMB_LIST.append(int(input()))

    mp = calcMP(0, 0, 0, 0)
    print(mp)

Submission status: Accepted

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


def solve(n, a, b, c, l):

    target = [a, b, c]

    INF = 10 ** 4
    ans = INF
    for i in range(2 ** (2 * n)):
        counts = [0] * 3
        lengths = [0] * 3
        x = i
        for j in range(n):
            g = x % 4
            if g < 3:
                counts[g] += 1
                lengths[g] += l[j]
            x = x // 4
        r = 0
        for g in range(3):
            if counts[g] == 0:
                r = INF
                break
            r += abs(target[g] - lengths[g])
        r += (sum(counts) - 3) * 10
        ans = min(ans, r)

    return ans


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

    print(solve(n, a, b, c, l))


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): #curは深さ、a~cはA~Cの暫定的な長さ
    if cur == N: #再帰の脱出条件
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF 
    #abs(a-A)は伸縮魔法に使うMP量、-30は最後の処理
    #→このアルゴリズムだと無から1本出す時もMP10使っているので30だけ多めになっている
    #DFSするので、min(a,b,c)>0でA~Cのいずれかが0になる最小コストを除外
    #Pythonはreturnの時点で下の処理は行われない(?)ので模範解答ではelseが書かれていない
    else:
        ret0 = dfs(cur + 1, a, b, c) #使わない場合
        ret1 = dfs(cur + 1, a + l[cur], b, c) + 10 #l[cur]をAの合成に使う場合
        ret2 = dfs(cur + 1, a, b + l[cur], c) + 10 #l[cur]をBの合成に使う場合
        ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10 #l[cur]をCの合成に使う場合
        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 func(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 = func(cur+1,a,b,c)
	ret1 = func(cur+1, a+l[cur],b,c) + 10
	ret2 = func(cur+1, a,b+l[cur],c) + 10
	ret3 = func(cur+1, a,b,c+l[cur]) + 10
	
	return min(ret0, ret1, ret2, ret3)

print(func(0,0,0,0))

Submission status: Accepted

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


def solve(N: int, A: int, B: int, C: int, l: "List[int]"):
    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 10e9
            )
        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))


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    l = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B, C, l)


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 = float('inf')

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 inf
        
    res0 = dfs(i + 1, a, b, c)
    res1 = dfs(i + 1, a + L[i], b, c) + 10
    res2 = dfs(i + 1, a, b + L[i], c) + 10
    res3 = dfs(i + 1, a, b, c + L[i]) + 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)]
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
    retNO = 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(retNO, retA, retB, retC)


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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A

#B

#C
def dfs(n,k,nu):
    global ans
    if n == 0:
        d = [0,0,0]
        m = 0
        for i in range(nu):
            if k[i] < 3:
                if d[k[i]] != 0:
                    m += 10
                d[k[i]] += l[i]
        if d[0]*d[1]*d[2] != 0:
            m += abs(a-d[0])+abs(b-d[1])+abs(c-d[2])
            ans = min(ans, m)
    else:
        for i in range(4):
            dfs(n-1,k+[i],nu)
n,a,b,c = LI()
l = IR(n)
li = []
ans = float("inf")
dfs(n,[],n)
print(ans)
#D
"""
a,b,q = LI()
s = IR(a)
t = IR(b)
for i in range(q):
    x = I()
    c = bisect.bisect_left(s,x)
    ans = float("inf")
    if c == a:
        k = abs(x-s[-1])
        y = s[-1]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
    else:
        k = abs(x-s[c-1])
        y = s[c-1]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
        k = abs(x-s[c])
        y = s[c]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
    c = bisect.bisect_left(t,x)
    if c == b:
        k = abs(x-t[-1])
        y = t[-1]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
    else:
        k = abs(x-t[c-1])
        y = t[c-1]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
        k = abs(x-t[c])
        y = t[c]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
    print(ans)
"""

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A

#B

#C
def dfs(n,k):
    if n == 0:
        li.append(k)
    else:
        for i in range(4):
            dfs(n-1,k+[i])
n,a,b,c = LI()
l = IR(n)
li = []
dfs(n,[])
ans = float("inf")
for k in li:
    d = [0,0,0]
    m = 0
    for i in range(n):
        if k[i] < 3:
            if d[k[i]] != 0:
                m += 10
            d[k[i]] += l[i]
    if d[0]*d[1]*d[2] == 0:continue
    m += abs(a-d[0])+abs(b-d[1])+abs(c-d[2])
    ans = min(ans, m)
print(ans)
#D
"""
a,b,q = LI()
s = IR(a)
t = IR(b)
for i in range(q):
    x = I()
    c = bisect.bisect_left(s,x)
    ans = float("inf")
    if c == a:
        k = abs(x-s[-1])
        y = s[-1]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
    else:
        k = abs(x-s[c-1])
        y = s[c-1]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
        k = abs(x-s[c])
        y = s[c]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
    c = bisect.bisect_left(t,x)
    if c == b:
        k = abs(x-t[-1])
        y = t[-1]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
    else:
        k = abs(x-t[c-1])
        y = t[c-1]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
        k = abs(x-t[c])
        y = t[c]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
    print(ans)
"""

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
from itertools import combinations

def f(in_A,in_B,in_C,A,B,C,ex_l,counter):
    if (counter == len(ex_l)):
        return abs(in_A-A)+abs(in_B-B)+abs(in_C-C)
    else:
        tmp = ex_l[counter]
        counter +=1
        a1 = f(in_A+tmp,in_B,in_C,A,B,C,ex_l,counter)+10
        a2 = f(in_A,in_B+tmp,in_C,A,B,C,ex_l,counter)+10
        a3 = f(in_A,in_B,in_C+tmp,A,B,C,ex_l,counter)+10
        a4 = f(in_A,in_B,in_C,A,B,C,ex_l,counter)
    return min(a1,a2,a3,a4)

N,A,B,C=map(int,input().split())
l = []
for i in range(N):
    l.append(int(input()))
in_l = list(map(list,combinations(l,3)))
ex_l = [l[:] for _ in range(len(in_l))]
for i in range(len(in_l)):
    ex_l[i].remove(in_l[i][0])
    ex_l[i].remove(in_l[i][1])
    ex_l[i].remove(in_l[i][2])

mp = []
for i in range(len(in_l)):
    mp.append(f(in_l[i][0],in_l[i][1],in_l[i][2],A,B,C,ex_l[i],0))
    mp.append(f(in_l[i][0],in_l[i][1],in_l[i][2],A,C,B,ex_l[i],0))
    mp.append(f(in_l[i][0],in_l[i][1],in_l[i][2],B,A,C,ex_l[i],0))
    mp.append(f(in_l[i][0],in_l[i][1],in_l[i][2],B,C,A,ex_l[i],0))
    mp.append(f(in_l[i][0],in_l[i][1],in_l[i][2],C,A,B,ex_l[i],0))
    mp.append(f(in_l[i][0],in_l[i][1],in_l[i][2],C,B,A,ex_l[i],0))
mp = min(mp)
print(mp)

Submission status: Accepted

Solution code:
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 float('inf')

    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
    ret4 = dfs(n+1,a,b,c)

    return min(ret1,ret2,ret3,ret4)



if __name__ == "__main__":
    N,A,B,C = map(int,input().split())
    l = [int(input()) for _ in range(N)]
    print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
from itertools import combinations

def f(in_A,in_B,in_C,A,B,C,ex_l,counter):
    if (counter == len(ex_l)):
        return abs(in_A-A)+abs(in_B-B)+abs(in_C-C)
    else:
        tmp = ex_l[counter]
        counter +=1
        a1 = f(in_A+tmp,in_B,in_C,A,B,C,ex_l,counter)+10
        a2 = f(in_A,in_B+tmp,in_C,A,B,C,ex_l,counter)+10
        a3 = f(in_A,in_B,in_C+tmp,A,B,C,ex_l,counter)+10
        a4 = f(in_A,in_B,in_C,A,B,C,ex_l,counter)
    return min(a1,a2,a3,a4)

N,A,B,C=map(int,input().split())
l = []
for i in range(N):
    l.append(int(input()))
in_l = list(map(list,combinations(l,3)))
ex_l = [l[:] for _ in range(len(in_l))]
for i in range(len(in_l)):
    ex_l[i].remove(in_l[i][0])
    ex_l[i].remove(in_l[i][1])
    ex_l[i].remove(in_l[i][2])

mp = 1000000
for i in range(len(in_l)):
    tmp = f(in_l[i][0],in_l[i][1],in_l[i][2],A,B,C,ex_l[i],0)
    if(mp>tmp):
        mp = tmp
for i in range(len(in_l)):
    tmp = f(in_l[i][0],in_l[i][1],in_l[i][2],A,C,B,ex_l[i],0)
    if(mp>tmp):
        mp = tmp
for i in range(len(in_l)):
    tmp = f(in_l[i][0],in_l[i][1],in_l[i][2],B,A,C,ex_l[i],0)
    if(mp>tmp):
        mp = tmp
for i in range(len(in_l)):
    tmp = f(in_l[i][0],in_l[i][1],in_l[i][2],B,C,A,ex_l[i],0)
    if(mp>tmp):
        mp = tmp
for i in range(len(in_l)):
    tmp = f(in_l[i][0],in_l[i][1],in_l[i][2],C,A,B,ex_l[i],0)
    if(mp>tmp):
        mp = tmp
for i in range(len(in_l)):
    tmp = f(in_l[i][0],in_l[i][1],in_l[i][2],C,B,A,ex_l[i],0)
    if(mp>tmp):
        mp = tmp
print(mp)

Submission status: Accepted

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


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 10 ** 9
  ret0 = dfs(n + 1,a + l[n],b,c) + 10
  ret1 = dfs(n + 1,a,b + l[n],c) + 10
  ret2 = dfs(n + 1,a,b,c + l[n]) + 10
  ret3 = dfs(n + 1,a,b,c)
  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())
lst = [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 + lst[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + lst[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + lst[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 = []
for i in range(N):
    L.append(int(input()))
    
import itertools
m = 4
bit_list = list(itertools.product([i for i in range(m)], repeat=N))
ans = 10 ** 18
for bit in bit_list:
    retA = 0
    retB = 0
    retC = 0
    checkA = False
    checkB = False
    checkC = False
    cost = 0
    for i,j in enumerate(bit):
        if j == 1:
            retA += L[i]
            if checkA:
                cost += 10
            checkA = True
        if j == 2:
            retB += L[i]
            if checkB:
                cost += 10
            checkB = True
        if j == 3:
            retC += L[i]
            if checkC:
                cost += 10
            checkC = True
    if min(retA,retB,retC) != 0:
        ans = min(ans, abs(A-retA)+abs(B-retB)+abs(C-retC)+cost)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]
ans = min(
    sum(
        abs(sum(x for k, x in zip(p, l) if k == r) - y) + 10 * (p.count(r) - 1)
        for r, y in enumerate((A, B, C), 1)
    )
    for p in product(range(4), repeat=N)
    if {1, 2, 3} <= set(p)
)
print(ans)

Submission status: Accepted

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


def f(idx, mp, a, b, c):
    if idx == N:
        if a==0 or b==0 or c==0:
            return float('inf')
        else:
            d = abs(A - a) + abs(B - b) + abs(C - c)
            return mp + d

    l = L[idx]
    # idxをAとして使う
    if a == 0:
        f1 = f(idx + 1, mp, l, b, c)
    else:
        f1 = f(idx + 1, mp + 10, a + l, b, c)

    # idxをBとして使う
    if b == 0:
        f2 = f(idx + 1, mp, a, l, c)
    else:
        f2 = f(idx + 1, mp + 10, a, b + l, c)

    # idxをCとして使う
    if c == 0:
        f3 = f(idx + 1, mp, a, b, l)
    else:
        f3 = f(idx + 1, mp + 10, a, b, c + l)

    # idx は使わない
    f4 = f(idx + 1, mp, a, b, c)

    return min(f1, f2, f3, f4)


ans = f(0, 0, 0, 0, 0)
print(ans)

Submission status: Accepted

Solution code:
N,A,B,C = map(int,input().split())
l = []
cand = []
for i in range(N):
    l.append(int(input()))
for i in range(4**N):
    a,b,c = [],[],[]
    for j in range(N):
        tmp = i // (4**j) % 4
        if tmp == 1:
            a.append(l[j])
        elif tmp == 2:
            b.append(l[j])
        elif tmp == 3:
            c.append(l[j])
    if a != [] and b != [] and c != []:
        al,bl,cl = sum(a),sum(b),sum(c)
        cand.append(abs(al-A)+abs(bl-B)+abs(cl-C)+10*(len(a)+len(b)+len(c)-3))
print(min(cand))

Submission status: Accepted

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

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

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 10**9
  ret0 = dfs(n+1, a+take[n], b, c) + 10
  ret1 = dfs(n+1, a, b+take[n], c) + 10
  ret2 = dfs(n+1, a, b, c+take[n]) + 10
  ret3 = dfs(n+1, a, b, c)
  return min(ret0, ret1, ret2, ret3)

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

Submission status: Accepted

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

    ans = editorial(N, A, B, C, ls)
    print(ans)


def editorial(N, A, B, C, ls):
    def dfs(cur, a, b, c):
        if cur == N:
            if min([a, b, c]) > 0:
                # 使わなくて足りない/使いすぎて超過している分は差引すればいい
                tmp = abs(a - A) + abs(b - B) + abs(c - C) - 30
            else:
                tmp = float("inf")
            # print(tmp, a, b, c, sep="\t")
            return tmp

        # 使うか使わないか,合成パターンを試す
        d = ls[cur]
        ret0 = dfs(cur + 1, a, b, c)
        ret1 = dfs(cur + 1, a + d, b, c) + 10
        ret2 = dfs(cur + 1, a, b + d, c) + 10
        ret3 = dfs(cur + 1, a, b, c + d) + 10

        return min([ret0, ret1, ret2, ret3])

    ans = dfs(0, 0, 0, 0)
    return 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(d,a,b,c):
    if d==N:#合成完了
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else inf #無からは作れない#0に合成するのにmpは使わないので-30
    ret0=dfs(d+1,a,b,c)#l[d]を使わない
    ret1=dfs(d+1,a+l[d],b,c)+10#l[d]をAに
    ret2=dfs(d+1,a,b+l[d],c)+10#l[d]をBに
    ret3=dfs(d+1,a,b,c+l[d])+10#l[d]をCに
    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 dfs(d,a,b,c):
    if d==N:#合成完了
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else inf #無からは作れない#0に合成するのにmpは使わないので-30
    ret0=dfs(d+1,a,b,c)#l[d]を使わない
    ret1=dfs(d+1,a+l[d],b,c)+10#l[d]をAに
    ret2=dfs(d+1,a,b+l[d],c)+10#l[d]をBに
    ret3=dfs(d+1,a,b,c+l[d])+10#l[d]をCに
    ans=min(ret0,ret1,ret2,ret3)
    return ans
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:

import itertools
import math
import copy

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

pattern = [list(itertools.combinations(range(x), 3)) for x in range(3, N+1)]

def stretch_shortening(sticks, A, B, C):
    min_cost = 1e10
    
    for i1, i2, i3 in pattern[len(sticks) - 3]:
        cost = abs(sticks[i1] - A) + abs(sticks[i2] - B) + abs(sticks[i3] - C)
        if min_cost > cost:
            min_cost = cost
    return min_cost

temp_set = set()
def connect(sticks, A, B, C):
    
    min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        if sticks[i1] + sticks[i2] > sticks[-1] and sticks[-1] >= C:
            continue
        if sticks[i1] <= 10 or sticks[i2] <= 10:
            continue
        
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        copied_sticks = sorted(copied_sticks)
        
        len_set = len(temp_set)
        temp_set.add(''.join(["{:05d}".format(x) for x in copied_sticks]))
        if len_set == len(temp_set):
            continue
        
        min_cost_connect = connect(copied_sticks, A, B, C)

        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost

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

min_cost = connect(sticks, C, B, A) #, 1e10)
#min_cost = stretch_shortening(sticks, A, B, C)
#print(pattern)

print(min_cost)

Submission status: Accepted

Solution code:
import numpy as np

def calc(i,x):
    if i ==0:
        return int((x % 4 == 1) or (x % 4 == 2))
    else:
        return int((x % (2**(i+1)) >= 2**i) and (x % 2 == 0))

def main():
    N,A,B,C = map(int, input().split())
    
    l = [int(input()) for i in range(N)]
    
    num = 4**N
    cre = 5000
    
    for i in range(num):
        num_A = 0
        num_B = 0
        num_C = 0
        new_cre_A = 0
        new_cre_B = 0
        new_cre_C = 0
        s = i
        for m in range(N):
            num_A += int(s % 4 == 1)
            num_B += int(s % 4 == 2)
            num_C += int(s % 4 == 3)
            s = s // 4
            #print(num_A)
        #print(num_A,num_B,num_C)
        #exit()
        s = i
        if num_A > 0 and num_B > 0 and num_C > 0:
            for j in range(N):
                new_cre_A += l[j]*int(s % 4 == 1)
                new_cre_B += l[j]*int(s % 4 == 2)
                new_cre_C += l[j]*int(s % 4 == 3)
                s = s // 4
                
            new_cre_A = abs(new_cre_A - A) + (num_A-1) * 10
            new_cre_B = abs(new_cre_B - B) + (num_B-1) * 10
            new_cre_C = abs(new_cre_C - C) + (num_C-1) * 10
            new_cre_A = new_cre_A + new_cre_B + new_cre_C
            #print(new_cre_A,cre)
            #exit()
            if cre > new_cre_A:
                cre = new_cre_A

    print(cre)
    
main()

Submission status: Accepted

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

l = []


for i in range(0,N):
  inp = int(input())
  l.append(inp)


def select_bamboo(choice,mp,ID,a,b,c,aa,bb,cc):
  if ID > N-1 and aa>= 1 and bb >= 1 and cc >= 1:
    return mp + abs(A-a) + abs(B-b) + abs(C-c)
  elif ID > N-1:
    return 10**12
  
  if choice == "a":
    a += l[ID]
    if aa>=1:
      mp += 10
    aa += 1
    reta = min(select_bamboo("a",mp,ID+1,a,b,c,aa,bb,cc), select_bamboo("b",mp,ID+1,a,b,c,aa,bb,cc), select_bamboo("c",mp,ID+1,a,b,c,aa,bb,cc), select_bamboo("x",mp,ID+1,a,b,c,aa,bb,cc))
    return reta
  if choice == "b":
    b += l[ID]
    if bb>=1:
      mp += 10
    bb += 1
    retb = min(select_bamboo("a",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("b",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("c",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("x",mp,ID+1,a,b,c,aa,bb,cc))
    return retb
  if choice == "c":
    c += l[ID]
    if cc>=1:
      mp += 10
    cc += 1
    retc = min(select_bamboo("a",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("b",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("c",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("x",mp,ID+1,a,b,c,aa,bb,cc))
    return retc
  if choice == "x":
    retx = min(select_bamboo("a",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("b",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("c",mp,ID+1,a,b,c,aa,bb,cc),select_bamboo("x",mp,ID+1,a,b,c,aa,bb,cc))
    return retx
  

print(min(select_bamboo("a",0,0,0,0,0,0,0,0),select_bamboo("b",0,0,0,0,0,0,0,0),select_bamboo("c",0,0,0,0,0,0,0,0),select_bamboo("x",0,0,0,0,0,0,0,0)))

Submission status: Accepted

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

cnt = 0
out = None
for i in range(4**N):
    j = [(i//(4**k) % 4) for k in range(N)]
    num = [j.count(i) for i in range(3)]
    if num[0]==0 or num[1]==0 or num[2]==0:
        continue
    score = sum([abs(target[k]-sum([l[tmp] for tmp in range(N) if j[tmp]==k])) for k in range(3)]) + (sum(num)-3)*10
    if out == None:
        out = score
    else:
        out = min(out,score)
print(out)

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(n, a, b, c): # n本目を使用するかしないか
  if n == N: # 全ての竹を選び終わったら、延長魔法と短縮魔法を使ってA,B,Cの長さにする
    if min(a, b, c) > 0: # 最低でも1本のみ使用する
      return abs(A-a)+abs(B-b)+abs(C-c)-30 # 1本使用の場合は合成しないため-30
    else:
      return INF
  ret0 = dfs(n + 1, a, b, c) # 使わない
  ret1 = dfs(n + 1, a + L[n], b, c) + 10 # Aに使う
  ret2 = dfs(n + 1, a, b + L[n], c) + 10 # Bに使う
  ret3 = dfs(n + 1, a, b, c + L[n]) + 10 # Cに使う
  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)]

def dfs(x, a, b, c):
  if(x == N):
    if(min(a, b, c) > 0):
      return abs(a-A)+abs(b-B)+abs(c-C)-30
    else:
      return 1e9+7
  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 _ in range(n):
    l.append(int(input()))

def dfs(depth, t, ans):
    if depth == n:
        sum = calc(t)
        if sum < ans:
            return sum
        else:
            return ans

    for j in range(4):
        tt = t.copy()
        tt.append(j)
        ans = dfs(depth + 1, tt, ans)

    return ans

def calc(t):
    ttt = [ [0, 0] ] * 3

    for i, v in enumerate(t):
        if v < 3:
            ttt[v] = [ttt[v][0] + 1, ttt[v][1] + l[i]]

    if ttt[0][0] == 0 or ttt[1][0] == 0 or ttt[2][0] == 0:
        return 1000000000

    sum = 0
    abc = [a, b, c, 0]
    for i, v in enumerate(ttt):
        sum += ((v[0] - 1) * 10) + abs(v[1] - abc[i])

    return sum


ans = dfs(0, [], 1000000000)
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))