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
sys.setrecursionlimit(500000)

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

kumi = []
abcx = ['A', 'B', 'C', 'X']

def dfs(arr: list):
    if len(arr) == N:
        kumi.append(arr[:])
        return
    for k in ['A', 'B', 'C', 'X']:
        arr.append(k)
        dfs(arr)
        arr.pop()

dfs([])

ans = float('inf')
for k in kumi:
    if set(k) & set(['A', 'B', 'C']) != set(['A', 'B', 'C']):
        continue
    tmp = 0
    a = 0
    b = 0
    c = 0
    for i in range(N):
        if k[i] == 'A':
            if a > 0:
                tmp += 10
            a += L[i]
        elif k[i] == 'B':
            if b > 0:
                tmp += 10
            b += L[i]
        elif k[i] == 'C':
            if c > 0:
                tmp += 10
            c += L[i]
    tmp += abs(A-a)
    tmp += abs(B-b)
    tmp += abs(C-c)
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
# ＢＦＳ, パターン列挙_竹'n'本の使用パターン

from collections import deque

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

queue = deque([[0],[1],[2],[-1]]) # 初期化_ここでは竹の使用パターン4つを設置
ptns = [] # パターン候補の器_初期化
 
while queue: # queueが空になるまでループ
    tmp = queue.popleft() # パターンの候補を popleft
    if len(tmp) == n: # 条件に合えば append
        ptns.append(tmp)
    elif len(tmp) < n: # 条件に合わなければ...
        w = tmp + [0] # パターンの候補を作成して...
        x = tmp + [1] # 〃
        y = tmp + [2] # 〃
        z = tmp + [-1]
        queue += [w, x, y, z]  # キューに追加

#print(ptns) # 竹の使用パターン

ans = 10**9
for i in range(len(ptns)):
    if 0 not in ptns[i] or 1 not in ptns[i] or 2 not in ptns[i]:
        continue
    abc = [0, 0, 0, -30]
    for j in range(n):
        tmp = ptns[i][j]
        if tmp >= 0:
            abc[tmp] += l[j]
            abc[3] += 10
    mp = abc[3]
    mp += abs(abc[0] - a)
    mp += abs(abc[1] - b)
    mp += abs(abc[2] - c)
    ans = min(ans, mp)

print(ans)

'''
# パターン列挙と探索を並行して処理

from collections import deque

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

queue = deque([[0],[1],[2],[-1]])

ans = 10**9
while queue:
    tmp = queue.popleft()
    if len(tmp) == n:
        if 0 not in tmp or 1 not in tmp or 2 not in tmp:
            continue
        abc = [0, 0, 0, -30]
        for j in range(n):
            if tmp[j] >= 0:
                abc[tmp[j]] += l[j]
                abc[3] += 10
        mp = abc[3]
        mp += abs(abc[0] - a)
        mp += abs(abc[1] - b)
        mp += abs(abc[2] - c)
        ans = min(ans, mp)

    elif len(tmp) < n:
        w = tmp + [0]
        x = tmp + [1]
        y = tmp + [2]
        z = tmp + [-1]
        queue += [w, x, y, z]

print(ans)

'''

Submission status: Accepted

Solution code:
# ＤＦＳ, パターン列挙_竹'n'本の使用パターン
'''
from collections import deque

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

queue = deque([[0],[1],[2],[-1]]) # 初期化_ここでは竹の使用パターン4つを設置
ptns = [] # パターン候補の器_初期化
 
while queue: # stackが空になるまでループ
    tmp = queue.pop() # パターンの候補を pop
    if len(tmp) == n: # 条件に合えば append
        ptns.append(tmp)
    elif len(tmp) < n: # 条件に合わなければ...
        w = tmp + [0] # パターンの候補を作成して...
        x = tmp + [1] # 〃
        y = tmp + [2] # 〃
        z = tmp + [-1]
        queue += [w, x, y, z]  # 積む

#print(ptns) # 竹の使用パターン

ans = 10**9
for i in range(len(ptns)):
    if 0 not in ptns[i] or 1 not in ptns[i] or 2 not in ptns[i]:
        continue
    abc = [0, 0, 0, -30]
    for j in range(n):
        tmp = ptns[i][j]
        if tmp >= 0:
            abc[tmp] += l[j]
            abc[3] += 10
    mp = abc[3]
    mp += abs(abc[0] - a)
    mp += abs(abc[1] - b)
    mp += abs(abc[2] - c)
    ans = min(ans, mp)

print(ans)

'''
# パターン列挙と探索を並行して処理

from collections import deque

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

queue = deque([[0],[1],[2],[-1]])

ans = 10**9
while queue:
    tmp = queue.pop()
    if len(tmp) == n:
        if 0 not in tmp or 1 not in tmp or 2 not in tmp:
            continue
        abc = [0, 0, 0, -30]
        for j in range(n):
            if tmp[j] >= 0:
                abc[tmp[j]] += l[j]
                abc[3] += 10
        mp = abc[3]
        mp += abs(abc[0] - a)
        mp += abs(abc[1] - b)
        mp += abs(abc[2] - c)
        ans = min(ans, mp)

    elif len(tmp) < n:
        w = tmp + [0]
        x = tmp + [1]
        y = tmp + [2]
        z = tmp + [-1]
        queue += [w, x, y, z]

print(ans)

Submission status: Accepted

Solution code:
# ＤＦＳ, パターン列挙_竹'n'本の使用パターン

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

stack = [[0],[1],[2],[-1]] # 初期化_ここでは竹の使用パターン4つを設置
ptns = [] # パターン候補の器_初期化
 
while stack: # stackが空になるまでループ
    tmp = stack.pop() # パターンの候補を pop
    if len(tmp) == n: # 条件に合えば append
        ptns.append(tmp)
    elif len(tmp) < n: # 条件に合わなければ...
        w = tmp + [0] # パターンの候補を作成して...
        x = tmp + [1] # 〃
        y = tmp + [2] # 〃
        z = tmp + [-1]
        stack += [w, x, y, z]  # 積む

#print(ptns) # 竹の使用パターン

ans = 10**9
for i in range(len(ptns)):
    if 0 not in ptns[i] or 1 not in ptns[i] or 2 not in ptns[i]:
        continue
    abc = [0, 0, 0, -30]
    for j in range(n):
        tmp = ptns[i][j]
        if tmp >= 0:
            abc[tmp] += l[j]
            abc[3] += 10
    mp = abc[3]
    mp += abs(abc[0] - a)
    mp += abs(abc[1] - b)
    mp += abs(abc[2] - c)
    ans = min(ans, mp)

print(ans)

'''
# パターン列挙と探索を並行して処理

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

stack = [[0],[1],[2],[-1]]

ans = 10**9
while stack:
    tmp = stack.pop()
    if len(tmp) == n:
        if 0 not in tmp or 1 not in tmp or 2 not in tmp:
            continue
        abc = [0, 0, 0, -30]
        for j in range(n):
            if tmp[j] >= 0:
                abc[tmp[j]] += l[j]
                abc[3] += 10
        mp = abc[3]
        mp += abs(abc[0] - a)
        mp += abs(abc[1] - b)
        mp += abs(abc[2] - c)
        ans = min(ans, mp)

    elif len(tmp) < n:
        w = tmp + [0]
        x = tmp + [1]
        y = tmp + [2]
        z = tmp + [-1]
        stack += [w, x, y, z]

print(ans)
'''

Submission status: Accepted

Solution code:
# ＤＦＳ, パターン列挙_竹'n'本の使用パターン

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

stack = [[0],[1],[2],[-1]] # 初期化_ここでは竹の使用パターン4つを設置
ptns = [] # パターン候補の器_初期化
 
while stack: # stackが空になるまでループ
    tmp = stack.pop() # パターンの候補を pop
    if len(tmp) == n: # 条件に合えば append
        ptns.append(tmp)
    elif len(tmp) < n: # 条件に合わなければ...
        w = tmp + [0] # パターンの候補を作成して...
        x = tmp + [1] # 〃
        y = tmp + [2] # 〃
        z = tmp + [-1]
        stack += [w, x, y, z]  # 積む

ans = 10**9
for i in range(len(ptns)):
    if 0 not in ptns[i] or 1 not in ptns[i] or 2 not in ptns[i]:
        continue
    abc = [0, 0, 0, -30]
    for j in range(n):
        tmp = ptns[i][j]
        if tmp >= 0:
            abc[tmp] += l[j]
            abc[3] += 10
    mp = abc[3]
    mp += abs(abc[0] - a)
    mp += abs(abc[1] - b)
    mp += abs(abc[2] - c)
    ans = min(ans, mp)

print(ans)

'''
# パターン列挙と探索を並行して処理

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

stack = [[0],[1],[2],[-1]]

ans = 10**9
while stack:
    tmp = stack.pop()
    if len(tmp) == n:
        if 0 not in tmp or 1 not in tmp or 2 not in tmp:
            continue
        abc = [0, 0, 0, -30]
        for j in range(n):
            if tmp[j] >= 0:
                abc[tmp[j]] += l[j]
                abc[3] += 10
        mp = abc[3]
        mp += abs(abc[0] - a)
        mp += abs(abc[1] - b)
        mp += abs(abc[2] - c)
        ans = min(ans, mp)

    elif len(tmp) < n:
        w = tmp + [0]
        x = tmp + [1]
        y = tmp + [2]
        z = tmp + [-1]
        stack += [w, x, y, z]

print(ans)
'''

Submission status: Accepted

Solution code:
# ＤＦＳ, パターン列挙_各竹の使用パターンを列挙

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

stack = [[0],[1],[2],[-1]]

ans = 10**9
while stack:
    tmp = stack.pop()
    if len(tmp) == n:
        if 0 not in tmp or 1 not in tmp or 2 not in tmp:
            continue
        abc = [0, 0, 0, -30]
        for j in range(n):
            if tmp[j] >= 0:
                abc[tmp[j]] += l[j]
                abc[3] += 10
        mp = abc[3]
        mp += abs(abc[0] - a)
        mp += abs(abc[1] - b)
        mp += abs(abc[2] - c)
        ans = min(ans, mp)

    elif len(tmp) < n:
        w = tmp + [0]
        x = tmp + [1]
        y = tmp + [2]
        z = tmp + [-1]
        stack += [w, x, y, z]

print(ans)

Submission status: Accepted

Solution code:
# ＤＦＳ, パターン列挙_各竹の使用パターンを列挙

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

stack = [[0],[1],[2],[-1]] # 初期化_ここでは竹の使用パターン4つを設置
ptns = [] # パターン候補の器_初期化
 
while stack: # stackが空になるまでループ
    tmp = stack.pop() # パターンの候補を pop
    if len(tmp) == n: # 条件に合えば append
        ptns.append(tmp)
    elif len(tmp) < n: # 条件に合わなければ...
        w = tmp + [0] # パターンの候補を作成して...
        x = tmp + [1] # 〃
        y = tmp + [2] # 〃
        z = tmp + [-1]
        stack += [w, x, y, z]  # 積む

ans = 10**9
for i in range(len(ptns)):
    if 0 not in ptns[i] or 1 not in ptns[i] or 2 not in ptns[i]:
        continue
    abc = [0, 0, 0, -30]
    for j in range(n):
        tmp = ptns[i][j]
        if tmp >= 0:
            abc[tmp] += l[j]
            abc[3] += 10
    mp = abc[3]
    mp += abs(abc[0] - a)
    mp += abs(abc[1] - b)
    mp += abs(abc[2] - c)
    ans = min(ans, mp)

print(ans)

Submission status: Accepted

Solution code:
N,A,B,C=list(map(int,input().split()))
l=[int(input()) for _ in range(N)]
target=sorted([0,A,B,C])
ans=10**10

for i in range(4**N):
    current=[0]*4
    cnt=[0]*4
    cost=0
    for j in range(N):
        b=i%4
        i//=4
        cnt[b]+=1
        current[b]+=l[j]

        if b>0 and cnt[b]>1:
            cost+=10
    
    current[0]=0
    current.sort()
    if current[1]==0:
        continue

    for j in range(1,4):
        cost+=abs(target[j]-current[j])

    ans=min(ans,cost)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,a,b,c=map(int,input().split())
    L=[int(input())for _ in range(n)]
    INF=10**9
    def dfs(cur,aa,bb,cc):
        if cur==n:
            return abs(aa-a)+abs(bb-b)+abs(cc-c)-30 if aa*bb*cc>0 else INF
        ret0=dfs(cur+1,aa,bb,cc)
        ret1=dfs(cur+1,aa+L[cur],bb,cc)+10
        ret2=dfs(cur+1,aa,bb+L[cur],cc)+10
        ret3=dfs(cur+1,aa,bb,cc+L[cur])+10
        return min(ret0,ret1,ret2,ret3)
    print(dfs(0,0,0,0))

if __name__=='__main__':
    main()

Submission status: Accepted

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

INF = 10 ** 9

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

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

Submission status: Accepted

Solution code:
# ABC119C
# Synthetic Kadomatsu
Enter = list(map(int, input().split()))
N = Enter[0]
L = [int(input()) for _ in range(N)]

ans = 10 ** 10

# 4 bist search
for i in range(4**N):
    mask = i
    NowCost = 0
    Group = [[] * 4 for _ in range(4)]
    for j in range(N-1, -1, -1):
        Group[mask%4].append(L[j])
        mask //= 4
    if len(Group[0]) == 0 or len(Group[1]) == 0 or len(Group[2]) == 0:
        continue
    for j in range(3):
        NowCost += 10 * (len(Group[j]) - 1)
        NowCost += abs(sum(Group[j]) - Enter[j+1])
    ans = min(ans, NowCost)
print(ans)

Submission status: Accepted

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

ans = 10 ** 10

# 4bit search
for i in range(4**N):
    mask = i
    NowCost = 0
    Group0 = []
    Group1 = []
    Group2 = []
    NonGroup = []
    for j in range(N-1, -1, -1):
        if mask % 4 == 0:
            Group0.append(L[j])
            mask //= 4
        elif mask % 4 == 1:
            Group1.append(L[j])
            mask //= 4
        elif mask % 4 == 2:
            Group2.append(L[j])
            mask //= 4
        else:
            NonGroup.append(L[j])
            mask //= 4
    if len(Group0) == 0 or len(Group1) == 0 or len(Group2) == 0:
        continue
    NowCost += 10 * (len(Group0) - 1)
    LengthGroup0 = sum(Group0)
    NowCost += 10 * (len(Group1) - 1)
    LengthGroup1 = sum(Group1)
    NowCost += 10 * (len(Group2) - 1)
    LengthGroup2 = sum(Group2)
    NowCost += abs(A - LengthGroup0)
    NowCost += abs(B - LengthGroup1)
    NowCost += abs(C - LengthGroup2)
    ans = min(ans, NowCost)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, a, b, c = map(int, input().split())
lis = []
for i in range(n):
    lis.append(int(input()))

res = 10**9

for g in itertools.product([0, 1, 2, 3], repeat=n):
    s = [[], [], [], []]
    for i, gg in enumerate(g):
        s[gg].append(lis[i])
    if not s[0] or not s[1] or not s[2]:
        continue
    else:
        x, y, z = sorted([sum(s[0]), sum(s[1]), sum(s[2])])
        l, m, n = len(s[0]), len(s[1]), len(s[2])
        pnt = abs(x-c) + abs(y-b) + abs(z-a) + 10*(l+m+n-3)
        res = min(pnt, res)
print(res)

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 sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# ここから書き始める
def dfs(n, i, a_total, b_total, c_total, a_cnt, b_cnt, c_cnt):
    if i == n:
        global ans
        if a_cnt == 0 or b_cnt == 0 or c_cnt == 0:
            return
        a_cost = abs(a - a_total) + max(0, (a_cnt - 1) * 10)
        b_cost = abs(b - b_total) + max(0, (b_cnt - 1) * 10)
        c_cost = abs(c - c_total) + max(0, (c_cnt - 1) * 10)
        cost = a_cost + b_cost + c_cost
        if ans > cost:
            ans = cost
        return
    dfs(n, i + 1, a_total + l[i], b_total, c_total, a_cnt + 1, b_cnt, c_cnt)
    dfs(n, i + 1, a_total, b_total + l[i], c_total, a_cnt, b_cnt + 1, c_cnt)
    dfs(n, i + 1, a_total, b_total, c_total + l[i], a_cnt, b_cnt, c_cnt + 1)
    dfs(n, i + 1, a_total, b_total, c_total, a_cnt, b_cnt, c_cnt)

n, a, b, c = map(int, input().split())
l = [int(input()) for i in range(n)]
ans = INF
dfs(n, 0, 0, 0, 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)]
key=4**N
ans=float("inf")
for i in range(4**N):
 flg=[0]*N 
 for j in range(N):
  if i!=0:
   flg[j]=i%4
  i=int(i/4)
 TA=0
 TB=0
 TC=0
 TD=0
 for k in range(N):
  if flg[k]==0:
   TA+=lst[k]
  elif flg[k]==1:
   TB+=lst[k]
  elif flg[k]==2:
   TC+=lst[k]
  else:
   TD+=1
  if TA!=0 and TB!=0 and TC!=0 :
   ans=min((N-TD-3)*10+abs(A-TA)+abs(B-TB)+abs(C-TC),ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product
N, A, B, C = map(int, sys.stdin.readline().rstrip().split())
L = [int(sys.stdin.readline().rstrip()) for _ in range(N)]
ans = 10**4

for cmb in product(range(4), repeat=N):
    a_sum = 0
    b_sum = 0
    c_sum = 0
    flag_a = 0
    flag_b = 0
    flag_c = 0
    cnt = 0
    for c, l in zip(cmb, L):
        if c == 0:
            a_sum += l
            if flag_a:
                cnt += 1
            else:
                flag_a = 1
        elif c == 1:
            b_sum += l
            if flag_b:
                cnt += 1
            else:
                flag_b = 1
        elif c == 2:
            c_sum += l
            if flag_c:
                cnt += 1
            else:
                flag_c = 1
    if flag_a == flag_b == flag_c == 1:
        ans = min(ans, 10 * cnt + abs(a_sum - A) + abs(b_sum - B) + abs(c_sum - C))
print(ans)

Submission status: Accepted

Solution code:
n, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(n)]
ans = float("INF")
for a in range(2**n):
    d0 = [(a >> b) & 1 for b in range(n)]
    for c in range(2**n):
        d1 = [(c >> d) & 1 for d in range(n)]
        abc = [0] * 3
        ans_ = 0
        for i in range(n):
            if d0[i] == 1 and d1[i] == 1:
                if abc[0]: ans_ += 10
                abc[0] += l[i]
            elif d0[i] == 0 and d1[i] == 1:
                if abc[1]: ans_ += 10
                abc[1] += l[i]
            elif d0[i] == 1 and d1[i] == 0:
                if abc[2]: ans_ += 10
                abc[2] += l[i]
        if abc[0] == 0 or abc[1] == 0 or abc[2] == 0: continue
        ans_ += abs(abc[0]-A)+abs(abc[1]-B)+abs(abc[2]-C)
        ans = min(ans, ans_)
print(ans)

Submission status: Accepted

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

def dfs(i, a, b, c):
    if i == N:
        if a > 0 and b > 0 and c > 0:
            # 最初の一本目の合体において +10 の必要がないのに足しているので、それぞれについて -10 してあげる
            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)

res = dfs(0, 0, 0, 0)
print(res)

Submission status: Accepted

Solution code:
n, a, b, c = map(int, input().split())
l = [int(input()) for i in range(n)]
min_ = 10**18
for i in range(4**n):
  la = []
  lb = []
  lc = []
  for j in range(n):
    i, amari = divmod(i, 4)
    if amari == 1:
      la.append(l[j])
    elif amari == 2:
      lb.append(l[j])
    elif amari == 3:
      lc.append(l[j])
    
    if len(la)>0 and len(lb)>0 and len(lc)>0:
      min_ = min(min_, abs(sum(la)-a)+10*(len(la)-1)+abs(sum(lb)-b)+10*(len(lb)-1)+abs(sum(lc)-c)+10*(len(lc)-1))
      
print(min_)

Submission status: Accepted

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

import itertools
cases = list(itertools.product([0,1,2,3], repeat=N))

out = float("inf")

for case in cases:
    As =[]
    Bs =[]
    Cs =[]
    for i in range(N):
        if case[i]==1:
            As.append(i)
        if case[i]==2:
            Bs.append(i)
        if case[i]==3:
            Cs.append(i)
    LA, LB, LC = len(As),len(Bs),len(Cs)
    if LA*LB*LC==0:
        continue
    point = (LA-1)*10 + (LB-1)*10 + (LC-1)*10

    Ah = 0
    for take in As:
        Ah+=L[take]
    Bh = 0
    for take in Bs:
        Bh+=L[take]
    Ch = 0
    for take in Cs:
        Ch+=L[take]
    point += abs(A-Ah) + abs(B-Bh) + abs(C-Ch)

    if point < out:
        out = point

print(out)

Submission status: Accepted

Solution code:
import itertools

N,A,B,C = map(int,input().split())
Comb = itertools.product([0,1,2,3],repeat=N)

L = []
for i in range(N):
  l = int(input())
  L.append(l)
  
# 各竹について  
# 0 : 使用しない
# 1 : 竹Aの材料にする  
# 2 : 竹Bの材料にする 
# 3 : 竹Cの材料にする
# 竹A,B,Cの作成法 :
# とりあえず全部合成 → 目的の長さに合わせる

ans = float('inf')
for X in Comb:
  tmp = 0
  m_A,m_B,m_C = [],[],[]
  for i in range(N):
    if(X[i] == 1): m_A.append(L[i])
    elif(X[i] == 2): m_B.append(L[i])
    elif(X[i] == 3): m_C.append(L[i])
  # 空の竹リストがないなら    
  if(len(m_A)*len(m_B)*len(m_C) != 0):      
    for take_list,take_len in zip([m_A,m_B,m_C],[A,B,C]):
      tmp += (len(take_list)-1)*10 # 合成
      tmp += (abs(take_len-sum(take_list)))*1 # 延長or短縮
    ans = min(ans,tmp)
  
print(ans)

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 float('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 = [int(input()) for _ in range(N)]
used = [0]*N
global pattern
pattern = []
global ans
ans = float('inf')

def dfs(A):
    global pattern
    global ans
    if len(A) == N:
        pattern.append(A)
        ans = min(ans, MP(A))
        return
    
    for i in range(4):
        A.append(i)
        dfs(A)
        A.pop()

    return 

def MP(A):
    group1 = []
    group2 = []
    group3 = []
    for i in range(N):
        if A[i] == 1:
            group1 += [l[i]]
        elif A[i] == 2:
            group2 += [l[i]]
        elif A[i] == 3:
            group3 += [l[i]]
    if len(group1) == 0 or len(group2) == 0 or len(group3) == 0:
        return float('inf')

    return calc(group1, a)+calc(group2, b)+calc(group3, c)
    
def calc(group, length):
    res = float('inf')
    for i in range(2**len(group)):
        bag = []
        for j in range(len(group)):
            if (i>>j) & 1:
                bag += [group[j]]
        
        if len(bag) == 0:
            continue
        elif len(bag) == 1:
            res = min(res, abs(length - bag[0]))
        else:
            res = min(res, abs(length - sum(group)) + 10*(len(group)-1))
        
    return res

dfs([])
print(ans)

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
ans = INF

for ptn in itertools.product([0,1,2,3], repeat=N):
    x = [0] * 4
    MP = 0
    for take, length in zip(ptn, 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 ans > MP:
        ans = MP
print(ans)

Submission status: Accepted

Solution code:
def dfs(cur, a, b, c):
    """
    深さがNだったら使用MPを評価
    N本の竹を使うときに必要な合成回数はN-1のため，最後に-1*10*3(?)
    1本も竹を使用していなかったら棄却→MPを無限に使うこととしている
    """
    if cur == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else 10 ** 9

    """ 
    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 + banboos[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + banboos[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + banboos[cur]) + 10
    return min(ret0, ret1, ret2, ret3)


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

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

Submission status: Accepted

Solution code:
# 解説を参考に作成


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

    def dfs(n=0, a=0, b=0, c=0, now_mp=0, min_mp=float('inf')):
        if n == N:
            if 0 in [a, b, c]:
                return min_mp
            else:
                return min(abs(A - a) + abs(B - b) + abs(C - c) - 30 + now_mp,
                           min_mp)
        result1 = dfs(n + 1, a, b, c, now_mp, min_mp)
        result2 = dfs(n + 1, a + ls[n], b, c, now_mp + 10, min_mp)
        result3 = dfs(n + 1, a, b + ls[n], c, now_mp + 10, min_mp)
        result4 = dfs(n + 1, a, b, c + ls[n], now_mp + 10, min_mp)
        return min(result1, result2, result3, result4)

    print(dfs())


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools
n,A,B,C=map(int,input().split())
l=[int(input()) for i in range(n)]
ll=[]
for p in itertools.product(['A','B','C','Z'],repeat=n):
  ans=0
  a=0
  b=0
  c=0
  numa=0
  numb=0
  numc=0
  for i in range(n):
    if p[i]=='A':
      a+=l[i]
      numa+=1
    elif p[i]=='B':
      b+=l[i]
      numb+=1
    elif p[i]=='C':
      c+=l[i]
      numc+=1
  ans+=(abs(a-A)+abs(B-b)+abs(C-c)+(numa+numb+numc-3)*10)
  if all(nn!=0 for nn in [numa,numb,numc]):
    ll.append(ans)
print(min(ll))

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, a, b, c = i_map()
    num_list = i_row(n)

    min_mp = INF
    for bin in list(product([0, 1, 2, 3], repeat=n)):
        ac = bin.count(1)
        bc = bin.count(2)
        cc = bin.count(3)
        if ac < 1 or bc < 1 or cc < 1:
            continue
        mp = 0
        if ac >= 2:
            mp += 10 * (ac-1)
        if bc >= 2:
            mp += 10 * (bc-1)
        if cc >= 2:
            mp += 10 * (cc-1)
        sum_a, sum_b, sum_c = 0, 0, 0
        for i in range(n):
            if bin[i] == 1:
                sum_a += num_list[i]
            elif bin[i] == 2:
                sum_b += num_list[i]
            elif bin[i] == 3:
                sum_c += num_list[i]
        mp += abs(a-sum_a)
        mp += abs(b-sum_b)
        mp += abs(c-sum_c)
        min_mp = min(min_mp, mp)
            
    print(min_mp)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = 10**9

for i in range(1, 4 ** n):
    q = bin(i)[2:].zfill(n * 2)
    pattern = [q[2 * j:2 * j + 2] for j in range(n)]
    k = [[], [], []]
    for j in range(n):
        t = int(pattern[j], 2)
        if t == 0:
            continue
        k[t-1].append(l[j])
    if len(k[0]) * len(k[1]) * len(k[2]) == 0:
        continue
    cost = 0
    for j in range(3):
        cost += abs(sum(k[j]) - target[j]) + (len(k[j]) - 1) * 10
    ans = min(cost, ans)

print(ans)

Submission status: Accepted

Solution code:
s=list(map(int, input().split()))
n=s[0]
a=s[1:]
l=[int(input()) for i in range(n)]
num=4**n
ans=1000000000
for i in range(num):
  t=i
  use=[[] for _ in range(4)]
  for j in range(n):
    use[t%4].append(l[j])
    t//=4
  cost=0
  for j in range(3):
    if len(use[j])==0:
      cost=100000000000
    else:
      cost+=(len(use[j])-1)*10+abs(sum(use[j])-a[j])
  ans=min(ans,cost)
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

  ans = INF
  ans = min(ans, dfs(cur+1, a, b, c))
  ans = min(ans, dfs(cur+1, a + l[cur], b, c)+10)
  ans = min(ans, dfs(cur+1, a, b+l[cur], c)+10)
  ans = min(ans, dfs(cur+1, a, b, c+l[cur])+10)
  return ans

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

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import product


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N,A,B,C = list(map(int,_in[0].split(' ')))  # type:list(int)
    l_arr = []
    for i in range(N):
        _ = int(_in[i+1])  # type:int
        l_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = float('inf')
    cand_arr = list(product([0,1,2,3],repeat=N))
    for cand in cand_arr:
        length = [0,0,0,0]
        if (1 in cand) and (2 in cand) and (3 in cand):
            for i,_len in zip(cand,l_arr):
                length[i] += _len
            _cnt = abs(A-length[1])+abs(B-length[2])+abs(C-length[3])+\
                   10*(N-cand.count(0)-3)
            cnt = min(cnt,_cnt)
    ## ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)