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:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, A: int, B: int, C: int, l: "List[int]"):
    e = [A, B, C]

    ret = float('inf')
    for i in range(4 ** N):
        ls = [0, 0, 0, 0]
        cs = [0, 0, 0, 0]
        for j, ll in enumerate(l):
            key = (i >> (2 * j)) & 0x03
            ls[key] += ll
            cs[key] += 10

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

        for i0, i1, i2 in permutations([0, 1, 2], 3):
            cc = cs[0] + abs(e[i0] - ls[0]) - 10
            cc += cs[1] + abs(e[i1] - ls[1]) - 10
            cc += cs[2] + abs(e[i2] - ls[2]) - 10
            if cc < ret:
                ret = cc
    return ret


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]"
    result = solve(N, A, B, C, l)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

def fun(rec,a,b,c):
    if rec == N:
        return abs(A-a) + abs(B-b) + abs(C-c)-30 if a*b*c != 0 else 10e20

    ans =  [fun(rec + 1 ,a,b,c) , fun(rec + 1 ,a+ls[rec],b,c) + 10 ,fun(rec + 1 ,a,b+ls[rec],c) + 10 ,fun(rec + 1 ,a,b,c+ls[rec])+10] 
    return min(ans)
print(fun(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)]
def dfs(d, a, b, c):
  if d == N:
    res = abs(a - A) + abs(b - B) + abs(c - C) - 30
    return 1e9 if min(a, b, c) == 0 else res
  ret = [0] * 4
  ret[0] = dfs(d + 1, a, b, c)
  ret[1] = dfs(d + 1, a + l[d], b, c) + 10
  ret[2] = dfs(d + 1, a, b + l[d], c) + 10
  ret[3] = dfs(d + 1, a, b, c + l[d]) + 10
  return min(ret)
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**9
def magic(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 = magic(cur+1, a, b, c)
    ret1 = magic(cur+1, a+L[cur], b, c) + 10
    ret2 = magic(cur+1, a, b+L[cur], c) + 10
    ret3 = magic(cur+1, a, b, c+L[cur]) + 10
    return min(ret0,ret1,ret2,ret3)
print(magic(0,0,0,0))

Submission status: Accepted

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

INF = 1e10

def solve(cur, a, b, c):
    if cur >= N:
        if min(a, b, c) == 0:
            return INF
        return -30 + sum(map(abs, [a - A, b - B, c - C]))
    return min(
        10 + solve(cur + 1, a + L[cur], b, c),
        10 + solve(cur + 1, a, b + L[cur], c),
        10 + solve(cur + 1, a, b, c + L[cur]),
        solve(cur + 1, a, b, c),
    )

print(solve(0, 0, 0, 0))

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
lst = [int(input()) for _ in range(N)]
#lst.sort(reverse =True) #大きいものが先に来ている

INF = 10 ** 9

def dfs(count, a, b, c): #count: 今回考える棒の番号, a, (b, c): A, (B,C) の棒を作るのに使う棒の長さの合計
    if count == N: #最後まで各竹をa, b, cに割り振り終わったら…
        if min(a,b,c) <= 0: #A, B, C用の竹が少なくともそれぞれ1本以上必要、それが満たされていないとき
            return INF #とりあえず大きな数を返しとく
        else:
            return abs(a-A)+abs(b-B)+abs(c-C)-30 
        #使う棒の合計の長さ(a, b, c)と目標とする長さ(A, B, C)の差の絶対値-各棒1本目のつなぐのに必要なMP(10 * 3)を除く
    ret0 = dfs(count+1, a, b, c) #count番目の竹を使わない-->countのみ1つ進める
    ret1 = dfs(count+1, a+lst[count], b, c) + 10 #count番目の竹をAに使う。つなぐ文、必要なMPを+10する
    ret2 = dfs(count+1, a, b+lst[count], c) + 10 #count番目の竹をBに使う。つなぐ文、必要なMPを+10する
    ret3 = dfs(count+1, a, b, c+lst[count]) + 10 #count番目の竹をCに使う。つなぐ文、必要なMPを+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())
bb = [int(input()) for i in range(n)]
res = []
for j in range (4**n-1) :
  t = str(bin(j))
  tt = t[2:]
  ttt = "0" * (2*n-len(tt)) + tt
  tttt = tuple(ttt)
  ttttt = tuple(map (int,tttt))
  mp = 0
  lg = [0,0,0,0]
  for take in range(n) :
      use = ttttt[take*2]*2 + ttttt[take*2+1]
      mp += 10
      if lg[use] == 0:
          mp -= 10
      lg[use] += bb[take]
      lg[3] = 0 
  if lg[0]*lg[1]*lg[2] == 0 :
      mp=10000000
  mp += abs(a-lg[0])
  mp += abs(b-lg[1])
  mp += abs(c-lg[2])
  res.append(mp)
print (min(res))

Submission status: Accepted

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

patterns = [[0,0,0]]

def check(index, a, b, c, mp):
    # 取らない場合
    if index == N:
        # 終端
        if a > 0 and b > 0 and c > 0:
            cost = abs(A - a) + abs(B - b) + abs(C - c) + mp
        else:
            cost = 1000 * 1000 * 10
        return cost

    cost1 = check(index + 1, a , b, c, mp)
    if a == 0:
        cost2 = check(index + 1, a + L[index] , b, c, mp)
    else:
        cost2 = check(index + 1, a + L[index] , b, c, mp + 10)

    if b == 0:
        cost3 = check(index + 1, a, b + L[index], c, mp)
    else:
        cost3 = check(index + 1, a, b + L[index], c, mp+ 10)

    if c == 0:
        cost4 = check(index + 1, a , b, c + L[index], mp)
    else:
        cost4 = check(index + 1, a , b, c + L[index], mp+10)

    return min([cost1, cost2, cost3, cost4])

print(check(0, 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):
  # N本目の竹まで探索し終わったらreturnする
  if cur == N:
    # min(a, b, c)>0で、一本も選んでいない場合を棄却する
    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 #長さAの竹の材料とする
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10 #長さBの竹の材料とする
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10 #長さCの竹の材料とする
  #minをそのときどき
  return min(ret0, ret1, ret2, ret3)

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

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

    INF = 10**10

    def dfs(depth, a, b, c):
        """ 各竹を、
        ・Aの合成魔法に使う
        ・Bの合成魔法に使う
        ・Cの合成魔法に使う
        ・使わない

        a:= 現在のAの長さ
        b:= 現在のBの長さ
        c:= 現在のCの長さ

        返り値は、MP
        """
        if depth == N:
            if min(a, b, c) > 0:
                return abs(a-A)+abs(b-B)+abs(c-C) - 30 # 必ず1つは選ばないといけないが、1つ選んだときは合成魔法のMPは必要ないので30引く
            else:
                return INF
        
        ans1 = dfs(depth+1, a, b, c)
        ans2 = dfs(depth+1, a+L[depth], b, c) + 10
        ans3 = dfs(depth+1, a, b+L[depth], c) + 10
        ans4 = dfs(depth+1, a, b, c+L[depth]) + 10

        return min(ans1, ans2, ans3, ans4)

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
nabc = input().split()
n = int(nabc[0])
a = int(nabc[1])
b = int(nabc[2])
c = int(nabc[3])
llist = [int(input()) for i in range(n)]


def make_select(idx):
    select = {'a': [], 'b': [], 'c': []}

    for i in range(n):
        bits = (idx>>(i*2)) & 3
        if bits == 1:
            select['a'].append(i)
        if bits == 2:
            select['b'].append(i)
        if bits == 3:
            select['c'].append(i)

    if not select['a'] or not select['b'] or not select['c']:
        return None
    return select


minmp = 10**32


for i in range(4**n):
    select = make_select(i)
    if not select:
        continue

    asum = bsum = csum = 0

    for idx in select['a']:
        asum += llist[idx]
    for idx in select['b']:
        bsum += llist[idx]
    for idx in select['c']:
        csum += llist[idx]

    mp = abs(asum - a) + abs(bsum - b) + abs(csum - c)
    mp += (len(select['a']) - 1) * 10
    mp += (len(select['b']) - 1) * 10
    mp += (len(select['c']) - 1) * 10

    minmp = min(minmp, mp)

print(minmp)

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())
def dfs(i,a,b,c):
    if i == N:
        if a==0 or b==0 or c==0:
            return 100000
        else:
            return abs(A-a)+abs(B-b)+abs(C-c)-30
    else:
         return min(dfs(i+1,a+l[i],b,c)+10, dfs(i+1,a,b+l[i],c)+10, dfs(i+1,a,b,c+l[i])+10, dfs(i+1,a,b,c))

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

Submission status: Accepted

Solution code:
import copy

nabc = input().split()
n = int(nabc[0])
a = int(nabc[1])
b = int(nabc[2])
c = int(nabc[3])
llist = [int(input()) for i in range(n)]


def calc_minmp(lenlist, vals, validx):
    minmp = 9999999999999999999999
    minbit = None

    for i in range(1<<len(lenlist)):
        count = totallen = 0
        for j in range(len(lenlist)):
            if (i>>j) & 1:
                count += 1
                totallen += lenlist[j]
        if count <= 0 or len(lenlist) - (2 - validx) < count:
            continue
        mp = (count - 1) * 10 + abs(totallen - vals[validx])
        if mp <= minmp:
            minmp = mp
            minbit = i

    for i in range(len(lenlist)):
        if minbit & (1<<i):
            lenlist[i] = None
    for i in reversed(range(len(lenlist))):
        if lenlist[i] is None:
            del lenlist[i]

    return minmp


def calc_minmp_for_vals(lenlist, vals, old_minmp):
    lenlist = copy.copy(lenlist)
    mp = calc_minmp(lenlist, vals, 0)
    mp += calc_minmp(lenlist, vals, 1)
    mp += calc_minmp(lenlist, vals, 2)
    return min(mp, old_minmp)


mp = calc_minmp_for_vals(llist, [a, b, c], 99999999999999999999)
mp = calc_minmp_for_vals(llist, [a, c, b], mp)
mp = calc_minmp_for_vals(llist, [b, a, c], mp)
mp = calc_minmp_for_vals(llist, [b, c, a], mp)
mp = calc_minmp_for_vals(llist, [c, a, b], mp)
mp = calc_minmp_for_vals(llist, [c, b, a], mp)

print(mp)

Submission status: Accepted

Solution code:
from itertools import product

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

mp = {}
for ptn in product([0, 1, 2, 3], repeat=N):
    a, b, c = 0, 0, 0
    x = 0
    for i in range(N):
        if ptn[i] == 1:
            if a != 0:
                x += 10
            a += l[i]
        elif ptn[i] == 2:
            if b != 0:
                x += 10
            b += l[i]
        elif ptn[i] == 3:
            if c != 0:
                x += 10
            c += l[i]
    if a * b * c == 0:
        continue
    mp[ptn] = abs(A - a) + abs(B - b) + abs(C - c) + x
print(min(mp.values()))

Submission status: Accepted

Solution code:
import collections
from copy import deepcopy

n,a,b,c=map(int,input().split())
arr=[int(input()) for _ in range(n)]
l=collections.deque()
l.append([[],[],[]])
cnt=0

while 1:
  if cnt==n:
    break
  base=l.popleft()
  if len(base[0])==0 and len(base[1])==0 and len(base[2])==0:
    l.append([[arr[cnt]],[],[]])
    l.append([[],[arr[cnt]],[]])
    l.append([[],[],[arr[cnt]]])
    l.append([[],[],[]])
    cnt+=1
  else:
    tmp1=deepcopy(base)
    tmp1[0].append(arr[cnt])
    l.append(tmp1)
    tmp2=deepcopy(base)
    tmp2[1].append(arr[cnt])
    l.append(tmp2)
    tmp3=deepcopy(base)
    tmp3[2].append(arr[cnt])
    l.append(tmp3)
    tmp4=deepcopy(base)
    l.append(tmp4)

mincost=10**9
for bl in l:
  if len(bl[0])==0 or len(bl[1])==0 or len(bl[2])==0:
    continue
  else:
    tmpcost=abs(sum(bl[0])-a)+abs(sum(bl[1])-b)+abs(sum(bl[2])-c)+10*(len(bl[0])-1+len(bl[1])-1+len(bl[2])-1)
    if mincost>tmpcost:
      mincost=tmpcost
print(mincost)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
l_list=[]
for i in range(N):
    l_list.append(int(input()))
def f(i,a,b,c):
    if i==N:
        if a*b*c==0:
            return 10**10
        else:
            return abs(a-A)+abs(b-B)+abs(c-C)-30
    else:
        addno=f(i+1,a,b,c)
        addA=f(i+1,a+l_list[i],b,c)+10
        addB=f(i+1,a,b+l_list[i],c)+10
        addC=f(i+1,a,b,c+l_list[i])+10
        return(min(addno,addA,addB,addC))
print(f(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(num, a, b, c):
    if N == num:
        return abs(A-a)+abs(B-b)+abs(C-c) - 30 if min(a,b,c)>=1 else 10**10
    ret = []
    ret.append(dfs(num+1, a, b, c))
    ret.append(dfs(num+1, a+l[num], b, c)+10)
    ret.append(dfs(num+1, a, b+l[num], c)+10)
    ret.append(dfs(num+1, a, b, c+l[num])+10)
    return min(ret)

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 = map(int, input().split())
L = []
INF = float('inf')
for i in range(N):
    L.append(int(input()))


def dfs(k, a, b, c):
    if k == N:
        if min(a, b, c) == 0:
            return INF
        else:
            return abs(A - a) + abs(B - b) + abs(C - c) - 30
    else:
        d0 = dfs(k + 1, a, b, c)
        d1 = dfs(k + 1, a + L[k], b, c) + 10
        d2 = dfs(k + 1, a, b + L[k], c) + 10
        d3 = dfs(k + 1, a, b, c + L[k]) + 10
        return min(d0, d1, d2, d3)


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

Submission status: Accepted

Solution code:
def func(n, a, b, c, l):
    # 連結後に増加させても、連結前に増加させてもコストは変わらない
    # 全通り試す（各l[i]をa,b,c,非使用で4分割し
    # そのあといくらコストがかかるか計算）
    def search(now, cost):
        if len(now) == len(l):
            _a = []
            _b = []
            _c = []
            for i in range(len(now)):
                if now[i] == 0:
                    _a.append(l[i])
                elif now[i] == 1:
                    _b.append(l[i])
                elif now[i] == 2:
                    _c.append(l[i])
            if not _a or not _b or not _c:
                return 10**10
            _cost = abs(a - sum(_a)) + abs(b - sum(_b)) + abs(c - sum(_c))
            _cost += (len(_a) - 1 + len(_b) - 1 + len(_c) - 1) * 10
            return _cost
        else:  # まだ分類していないl[i]がある場合
            for i in range(4):
                cost = min(cost, search(now+[i], cost))
            return cost
    cost = search([], 10**10)
    return cost

n, a, b, c = [int(i) for i in input().split()]
a, b, c = sorted([a, b, c])
l = []
for i in range(n):
    l.append(int(input()))
# print("a:{} b:{} c:{}".format(a, b, c))
# print("{}, {}, {}, {}, {}".format(n, a, b, c, sorted(l)))
print(func(n, a, b, c, l))
"""
print(func(5, 80, 90, 100, [21, 30, 40, 80, 98]))
print(func(8, 80, 90, 100, [80, 80, 80, 90, 90, 90, 100, 100]))
print(func(5, 100, 800, 1000, [300, 333, 400, 444, 500, 555, 600, 666]))
"""

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
take = [int(input()) for _ 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, b, c)
    ret1 = dfs(n + 1, a + take[n], b, c) + 10
    ret2 = dfs(n + 1, a, b + take[n], c) + 10
    ret3 = dfs(n + 1, a, b, c + take[n]) + 10
    return min(ret0, ret1, ret2, ret3)


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

Submission status: Accepted

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

def dcm(cou,a,b,c):
    if cou == N:
        if min(a,b,c)>0:
            return abs(A-a)+abs(B-b)+abs(C-c)-30
        else:
            return INF
    
    case0 = dcm(cou+1,a,b,c)
    case1 = dcm(cou+1,a+l[cou],b,c)+10
    case2 = dcm(cou+1,a,b+l[cou],c)+10
    case3 = dcm(cou+1,a,b,c+l[cou])+10
    
    return min(case0,case1,case2,case3)
        
print(dcm(0,0,0,0))

Submission status: Accepted

Solution code:
from itertools import product

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

L = [0] * N
for i in range(N):
    L[i] = int(input())

cost = 10e6
s1 = {0, 1, 2, 3}
s2 = {1, 2, 3}
for i in product([0, 1, 2, 3], repeat=N):
    s = set(i)
    if s != s1 and s != s2:
        continue
    nums = [[], [], [], []]
    for j, indx in enumerate(i):
        nums[indx].append(L[j])
    cost_a = abs(A - sum(nums[1])) + 10 * (len(nums[1]) - 1)
    cost_b = abs(B - sum(nums[2])) + 10 * (len(nums[2]) - 1)
    cost_c = abs(C - sum(nums[3])) + 10 * (len(nums[3]) - 1)
    cost_tmp = cost_a + cost_b + cost_c
    cost = min(cost, cost_tmp)
print(cost)

Submission status: Accepted

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

b = []
for x in range(4**N):
    o = []
    s = -30
    for y in range(N):
        o.append((x//(4**y))%4)
    if (0 in o) and (1 in o) and (2 in o):
        a = [A,B,C]
        for y in range(N):
            if o[y] != 3:
                a[o[y]] -= l[y]
                s += 10
        b.append(sum(map(lambda x: x if x > 0 else -x,a))+s)

print(min(b))

Submission status: Accepted

Solution code:
import functools
import itertools

import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


def count_mp(target, sizes):
    return (len(sizes) - 1) * 10 + abs(target - sum(sizes))


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

ans = INF
for allocs in itertools.product('abc_', repeat=N):
    a = []
    b = []
    c = []
    mp = 0
    for i, al in enumerate(allocs):
        if al == 'a':
            a.append(sizes[i])
        if al == 'b':
            b.append(sizes[i])
        if al == 'c':
            c.append(sizes[i])
    if not a or not b or not c:
        continue
    ans = min(ans, count_mp(A, a) + count_mp(B, b) + count_mp(C, c))
    if ans == 0:
        break
print(ans)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]
#L1～LNはL[0]~L[N-1]で取り出す。よってこれから竹1~Nのことを竹0~N-1と呼ぶ。

#メンバーの選び方[0]~[255]の「[合計初期サイズ, 本数]」を格納するリスト
initialSum = []
for i in range(2**N): #全てのフラグパターンについて計算する
    nowsum = 0
    nowbamboocnt = 0
    for j in range(N): #2^(j+1)乗で割った余りが2^j以上なら、フラグjがTrue
        if i % (2**(j+1)) >= 2**j:
            nowbamboocnt += 1
            nowsum += L[j] #j(0-N-1)本目の竹について見ているので、L[j]が今見ている竹の長さ
    initialSum.append([nowsum, nowbamboocnt])


#A,B,Cが竹を選んだ場合の所要MPを出し、最低値をminに格納する
bambooset = {i for i in range(N)} #存在する竹の組み合わせ
min = 3000 #最低値の初期化

lestbamboo = bambooset.copy() #残っている竹

for i, initSumA in enumerate(initialSum): #i:0~255。initsumA[0]は初期合計サイズ, initsumA[1]は本数
#Aはこのfor文で既に選ばれていると考えればいい。
    if initSumA[1] ==0 or N - initSumA[1] < 2: continue #竹が0とか、残り竹が0,1なら飛ばす
    lestbamboo = bambooset.copy() #再初期化
    for j in range(N): #使った竹はlestbambooからremove
        if i % (2**(j+1)) >= 2**j: #j(0-N-1)本目の竹について考えている
            lestbamboo.remove(j)
    necesMPforA = abs(A - initSumA[0]) + (initSumA[1]-1)*10 #abs(目標-合計)-合成必要MP

    #次はBを計算する。Bが取らなかったものの中からCが取る
    for b in range(2**len(lestbamboo)): #残った竹それぞれにつき取るか取らないか選ぶ
    #2*残り本数通りある。ex.3本残っているとして、b(000とか101とか)で、Bの選び方を示す
        lestbambooList = list(lestbamboo) #リスト化する [0]~[本数-1]。値は竹番号[0-N]
        #lestbambooListは自動的に昇順になっている
        bamboocntB = 0 #Bの本数
        nowsumB = 0
        lestbambooforC = lestbamboo.copy() #Cのための残り竹を入れる
        for k in range(len(lestbambooList)): #2^(k+1)乗で割った余りが2^k以上なら、フラグkがTrue
            if b % (2**(k+1)) >= 2**k: #Bがとる場合
                bamboocntB += 1
                nowsumB += L[lestbambooList[k]] #竹番号はlestbambooList[k]に入っている
                lestbambooforC.remove(lestbambooList[k])
        if bamboocntB == 0: continue #0本だと駄目なので飛ばす

        for m in range(2**len(lestbambooforC)): #残った竹それぞれにつき取るか取らないか
        #このfor文終了1回につき、ABCそれぞれの組み合わせが1つ終了！
        # →このループの終了時にminの判定を行う
            lestbambooforCList = list(lestbambooforC) #やっぱりリスト化
            bamboocntC = 0
            nowsumC = 0
            for n in range(len(lestbambooforCList)):
                if m % (2**(n+1)) >= 2**n: #Cがとる場合
                    bamboocntC += 1
                    nowsumC += L[lestbambooforCList[n]] #竹番号はlestbambooListforC[n]に入っている
            if bamboocntC == 0: continue #0本だと駄目なので飛ばす

            nowTotalSum = necesMPforA + abs(B - nowsumB) + (bamboocntB-1)*10 + abs(C - nowsumC) + (bamboocntC-1)*10
            #minの判定！
            if nowTotalSum < min: min = nowTotalSum

print(min)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]
#L1～LNはL[0]~L[N-1]で取り出す。よってこれから竹1~Nのことを竹0~N-1と呼ぶ。

#作られるべきA,B,Cが自らの材料として選んだ竹を、集合memA, memB, memCに格納？

#メンバーの選び方[0]~[255]の「[合計初期サイズ, 本数]」を格納するリスト
initialSum = []
for i in range(2**N): #全てのフラグパターンについて計算する
    nowsum = 0
    nowbamboocnt = 0
    for j in range(N): #2^(j+1)乗で割った余りが2^j以上なら、フラグjがTrue
        if i % (2**(j+1)) >= 2**j:
            nowbamboocnt += 1
            nowsum += L[j] #j(0-N-1)本目の竹について見ているので、L[j]が今見ている竹の長さ
    initialSum.append([nowsum, nowbamboocnt])

#テスト用→ print(initialSum)

#A,B,Cが竹を選んだ場合の所要MPを出し、最低値とその時の組み合わせをminに格納する
bambooset = {i for i in range(N)} #存在する竹の組み合わせ
min = 3000 #最低値の初期化

lestbamboo = bambooset.copy() #残っている竹

for i, initSumA in enumerate(initialSum): #i:0~255。initsumA[0]は初期合計サイズ, initsumA[1]は本数
#Aはこのfor文で既に選ばれていると考えればいい。
    if initSumA[1] ==0 or N - initSumA[1] < 2: continue #竹が0とか、残り竹が0,1なら飛ばす
    lestbamboo = bambooset.copy() #再初期化
    for j in range(N): #使った竹はlestbambooからremove
        if i % (2**(j+1)) >= 2**j: #j(0-N-1)本目の竹について考えている
            lestbamboo.remove(j)
    necesMPforA = abs(A - initSumA[0]) + (initSumA[1]-1)*10 #abs(目標-合計)-合成必要MP

    #次はBを計算する。Bが取らなかったものの中からCが取る
    for b in range(2**len(lestbamboo)): #残った竹それぞれにつき取るか取らないか選ぶ
    #2*残り本数通りある。ex.3本残っているとして、b(000とか101とか)で、Bの選び方を示す
        lestbambooList = list(lestbamboo) #リスト化する [0]~[本数-1]。値は竹番号[0-N]
        #lestbambooListは自動的に昇順になっている
        bamboocntB = 0 #Bの本数
        nowsumB = 0
        lestbambooforC = lestbamboo.copy() #Cのための残り竹を入れる
        for k in range(len(lestbambooList)): #2^(k+1)乗で割った余りが2^k以上なら、フラグkがTrue
            if b % (2**(k+1)) >= 2**k: #Bがとる場合
                bamboocntB += 1
                nowsumB += L[lestbambooList[k]] #竹番号はlestbambooList[k]に入っている
                lestbambooforC.remove(lestbambooList[k])
        if bamboocntB == 0: continue #0本だと駄目なので飛ばす

        for m in range(2**len(lestbambooforC)): #残った竹それぞれにつき取るか取らないか
        #このfor文終了1回につき、ABCそれぞれの組み合わせが1つ終了！
        # →このループの終了時にminの判定を行う
            lestbambooforCList = list(lestbambooforC) #やっぱりリスト化
            bamboocntC = 0
            nowsumC = 0
            for n in range(len(lestbambooforCList)):
                if m % (2**(n+1)) >= 2**n: #Cがとる場合
                    bamboocntC += 1
                    nowsumC += L[lestbambooforCList[n]] #竹番号はlestbambooListforC[n]に入っている
            if bamboocntC == 0: continue #0本だと駄目なので飛ばす

            nowTotalSum = necesMPforA + abs(B - nowsumB) + (bamboocntB-1)*10 + abs(C - nowsumC) + (bamboocntC-1)*10
            #minの判定！
            if nowTotalSum < min: min = nowTotalSum

print(min)

Submission status: Accepted

Solution code:
from itertools import product

N, A, B, C = map(int, input().split())
target = {'A': A, 'B': B, 'C': C}
L = [int(input()) for _ in range(N)]

mp = 10**9
cand = ['A', 'B', 'C', 'discard']
for t in product(cand, repeat=N):
    prepared = {'A': [], 'B': [], 'C': []}
    for i, p in enumerate(t):
        if p != 'discard':
            prepared[p].append(L[i])
    if prepared['A'] == [] or prepared['B'] == [] or prepared['C'] == []:
        continue
    temp = 0
    for p in ['A', 'B', 'C']:
        temp += abs(sum(prepared[p]) - target[p]) + (len(prepared[p]) - 1)*10
    if temp < mp:
        mp = temp
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(i, a, b, c):
    if i == N:
        if min(a, b, c) > 0:
            return abs(A - a) + abs(B - b) + abs(C - c) - 30
        else:
            return float('inf')
    
    tmp0 = dfs(i + 1, a, b, c)
    tmpa = dfs(i + 1, a + L[i], b, c) + 10
    tmpb = dfs(i + 1, a, b + L[i], c) + 10
    tmpc = dfs(i + 1, a, b, c + L[i]) + 10
    ans = min(tmp0, tmpa, tmpb, tmpc)
    
    return ans

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

Submission status: Accepted

Solution code:
def rec (i,a,b,c):
    if i==N:
        if a==0 or b==0 or c==0:
            return INF
        else:
            return abs(a-A)+abs(b-B)+abs(c-C)
    res = rec(i+1,a,b,c)
    
    res = min(res,rec(i+1,a+L[i],b,c)+(10 if a>0 else 0))
    res = min(res,rec(i+1,a,b+L[i],c)+(10 if b>0 else 0))
    res = min(res,rec(i+1,a,b,c+L[i])+(10 if c>0 else 0))
    
    return res
N,A,B,C = list(map(int,input().split()))
INF=10**8
L = [int(input()) for _ in range(N)]
print(rec(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)]
def dfs(cnt,A,B,C):
    if cnt == n:
        if min(A,B,C) == 0:
            return float('inf')
        else:
            return abs(a-A)+abs(b-B)+abs(c-C)-30
    else:
        ret1 = dfs(cnt+1,A+l[cnt],B,C)+10
        ret2 = dfs(cnt+1,A,B+l[cnt],C)+10
        ret3 = dfs(cnt+1,A,B,C+l[cnt])+10
        ret4 = dfs(cnt+1,A,B,C)
        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())
l = [int(input()) for i in range(n)]
def dfs(cnt,A,B,C):
    if cnt == n:
        if min(A,B,C) == 0:
            return float('inf')
        else:
            return abs(a-A)+abs(b-B)+abs(c-C)-30
    else:
        ret1 = dfs(cnt+1,A+l[cnt],B,C)+10
        ret2 = dfs(cnt+1,A,B+l[cnt],C)+10
        ret3 = dfs(cnt+1,A,B,C+l[cnt])+10
        ret4 = dfs(cnt+1,A,B,C)
        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())
l = [int(input()) for _ in range(N)]


def calc_mp(v):
    if v[0] == 0 or v[1] == 0 or v[2] == 0:
        return 10 ** 9
    return abs(A - v[0]) + abs(B - v[1]) + abs(C - v[2]) - 30


def dfs(n, v):
    if n == N:
        return calc_mp(v)
    ret0 = dfs(n + 1, (v[0] + l[n], v[1], v[2])) + 10
    ret1 = dfs(n + 1, (v[0], v[1] + l[n], v[2])) + 10
    ret2 = dfs(n + 1, (v[0], v[1], v[2] + l[n])) + 10
    ret3 = dfs(n + 1, (v[0], v[1], v[2]))

    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 i in range(N)]

def dfs(i, a, b, c):
    if i == N:
        if min(a, b, c) > 0:
            return abs(A - a) + abs(B - b) + abs(C - c) - 30
        else:
            return float('inf')
        
    n1 = 10 + dfs(i + 1, a + L[i], b, c)
    n2 = 10 + dfs(i + 1, a, b + L[i], c)
    n3 = 10 + dfs(i + 1, a, b, c + L[i])
    n4 = dfs(i + 1, a, b, c)
    
    return min(n1, n2, n3, n4)
    
print(dfs(0, 0, 0, 0))

Submission status: Accepted

Solution code:
from itertools import*
n,a,b,c,*l=map(int,open(0).read().split())
d=[a,b,c]
ans=float("inf")
for i in product(range(4),repeat=n):
    take=[[],[],[]]
    for k,j in enumerate(i):  #0を捨てる
        if j!=0:
            take[j-1].append(l[k])
    if all(take):
        take2=list(map(sum,take))
        #print(sum(abs(s-t)for s,t in zip(d,take2)),(sum(map(len,take))-3)*10)
        ans=min(ans,sum(abs(s-t)for s,t in zip(d,take2))+(sum(map(len,take))-3)*10)
print(ans)

Submission status: Accepted

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

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

print(magic(0, 0, 0, 0))

Submission status: Accepted

Solution code:
N,A,B,C = map(int,input().split())
l = [int(input()) for _ in range(N)]
lnum = [0] * N
Alist = [A,B,C]
ans = 2**30+1
for i in range(4**N):
    cnt = -30
    tmp = i
    for j in range(N):
        lnum[j] = tmp%4
        tmp //= 4
    
    if not(1 in lnum and 2 in lnum and 3 in lnum):
        continue
    x = [0] * 3
    for j in range(N):
        if lnum[j] != 0:
            x[lnum[j]-1] += l[j]
            cnt += 10
    for j in range(3):
        cnt += abs(Alist[j]-x[j])
    
    ans = min(ans,cnt)
    
print(ans)