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


def main():
    N, A, B, C = map(int, input().split())
    l = [int(input()) for _ in range(N)]
    ans = 10**9
    for i in range(4**N):
        # N本の竹がA,B,Cのどれに使われるか
        cost = [[] for _ in range(3)]
        tmp = i
        j = 0
        while j < N:
            if tmp % 4 < 3:
                cost[tmp % 4].append(l[j])
            j += 1
            tmp //= 4

        if len(cost[0]) == 0 or len(cost[1]) == 0 or len(cost[2]) == 0:
            continue

        tmpa = 0
        D = [A, B, C]
        # MPの計算
        for i in range(3):
            tmpa += abs(sum(cost[i]) - D[i]) + 10*(len(cost[i])-1)
        ans = min(ans, tmpa)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(cnt,a,b,c):
    if cnt == N:
        _sum = abs(A-a) + abs(B-b) + abs(C-c) - 30
        return _sum if min(a,b,c) > 0 else 10**9
    ret0 = dfs(cnt+1, a, b, c)
    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
    return min(ret0,ret1,ret2,ret3) 
    
N,A,B,C,*l = map(int,open(0).read().split())
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)]

import itertools
set123 = set([1,2,3])
ans = 10 ** 10
for i in itertools.product([0,1,2,3], repeat=n):
    if len(set(i) & set123) < 3:
        continue
    mp = 0
    ai = 0
    bi = 0
    ci = 0
    for j in range(n):
        if i[j] == 0:
            continue
        if i[j] == 1:
            if ai > 0:
                mp += 10
            ai += l[j]
        if i[j] == 2:
            if bi > 0:
                mp += 10
            bi += l[j]
        if i[j] == 3:
            if ci > 0:
                mp += 10
            ci += l[j]
    mp += abs(ai - a)
    mp += abs(bi - b)
    mp += abs(ci - c)
    ans = min(ans, mp)
print(ans)

Submission status: Accepted

Solution code:

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

L=[]
for i in range(N):
    l=int(input())
    L.append(l)
L=sorted(L, reverse=True)

combs=[]
for b in range(4**N):
    nowlist=[[],[],[],[]]
    for i in range(N):
        mod=b%4
        nowlist[mod].append(L[i])
        b=b//4
    combs.append(nowlist)

#print(combs)

abc=[A,B,C]

ans=float("INF")
for c in combs:
    now=0
    for i in range(3):
        cn=c[i]
        n=abc[i]
        if len(cn)==0:
            break
        now+=(len(cn)-1)*10
        now+=abs(sum(cn)-n)
        if i==2:
            ans=min(ans, now)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

L = [0] * N
l = []
for _ in range(N):
    L[_] = int(input())
for _ in range(4):
    l.append(_)

X = []
ans = float('inf')


def clear(X):
    global ans
    if len(X) == N:
        Z = [0]*4
        Znum = [0]*4
        for num, i in enumerate(X):
            Znum[i] += 1
            Z[i] += L[num]
        if 0 in Znum[1:]:
            return True
        ansi = abs(A - Z[1]) + abs(B - Z[2]) + abs(C - Z[3]) + (N - Znum[0] - 3) * 10
        ans = min(ans, ansi)
        return True
    else:
        for j in range(4):
            X.append(l[j])
            clear(X)
            X.pop()


clear(X)
print(ans)

Submission status: Accepted

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

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

ans = []
def dfs(idx, a, b, c, mp10):
    if idx==N:
        if a and b and c:
            ans.append(abs(A-a)+abs(B-b)+abs(C-c)+mp10*10)
    else:
        dfs(idx+1, a, b, c, mp10)
        dfs(idx+1, a+L[idx], b, c, mp10+1)
        dfs(idx+1, a, b+L[idx], c, mp10+1)
        dfs(idx+1, a, b, c+L[idx], mp10+1)

dfs(0, 0, 0, 0, -3)

print(min(ans))

Submission status: Accepted

Solution code:
def main():
    from itertools import product

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

    ans = 3000
    for prod in product([0, 1, 2, 3], repeat=N):
        t = [[] for _ in range(3)]
        for i, x in enumerate(prod):
            if x == 3: continue
            t[x].append(i)
        if (not t[0]) or (not t[1]) or (not t[2]): continue

        cost = sum(len(t[i]) - 1 for i in range(3)) * 10
        a = sum(L[i] for i in t[0])
        b = sum(L[i] for i in t[1])
        c = sum(L[i] for i in t[2])
        cost += abs(A - a) + abs(B - b) + abs(C - c)
        if ans > cost:
            ans = cost

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
n, a, b, c = map(int, input().split())
l = []
for i in range(n):
    l.append(int(input()))
ans = 10**6
f = lambda li, k: abs(sum(li)-k)+10*(len(li)-1)
for i in range(4**n):
    li = [[] for _ in range(4)]
    for j in range(n):
        li[(i//(4**j))%4].append(l[j])
    if len(li[0])*len(li[1])*len(li[2])==0:
        continue
    ans = min(ans, f(li[0], a)+f(li[1], b)+f(li[2], c))
print(ans)

Submission status: Accepted

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

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

tnum = 0
ans = float("inf")
target = [A,B,C]
for i in range(4**N):
  #N本の竹の行き先の振り分け
  wake = [[],[],[],[]]
  ts = "0"*(N-len(tots(i,4)))+tots(i,4)
  for j in range(N):
    wake[int(ts[j])].append(l[j])
  if 0 == len(wake[0]) or 0 == len(wake[1]) or 0 == len(wake[2]):
    continue 
  #合成して行き先との長さの差をたしわせる
  c = 0
  for j in range(3):
    c +=abs(target[j] - sum(wake[j]))      
  tnum = len(wake[0])+len(wake[1])+len(wake[2])
  ans = min(ans,c+10*(tnum-3))  

if A in l and B in l and C in l:
  ans = 0
print(ans)

Submission status: Accepted

Solution code:
def dfs(i, a, b, c, plus):
    global ans

    if i == n:
        if a and b and c:
            mp = abs(a - A) + abs(b - B) + abs(c - C) + (plus - 3) * 10
            ans = min(ans, mp)

    else:
        dfs(i + 1, a, b, c, plus)
        dfs(i + 1, a + l[i], b, c, plus + 1)
        dfs(i + 1, a, b + l[i], c, plus + 1)
        dfs(i + 1, a, b, c + l[i], plus + 1)


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

ans = float("inf")

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, A, B, C = map(int, input().split())
L = [int(input()) for i in range(N)]
INF = 10 ** 30
def calc(p):
    if sum(list(set(p))) < 6:
        return INF
    a, b, c = 0, 0, 0
    ac, bc, cc = 0, 0, 0
    for i, v in enumerate(p):
        if v == 1:
            a += L[i]
            ac += 1
        elif v == 2:
            b += L[i]
            bc += 1
        elif v == 3:
            c += L[i]
            cc += 1
    return abs(A-a) + abs(B-b) + abs(C-c) + (ac+bc+cc-3) * 10

ans = INF
for p in product(range(4), repeat=N):
    ans = min(ans, calc(p))
print(ans)

Submission status: Accepted

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

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

ans = 10 ** 18
for alloc in product(range(4), repeat=N):
    La = 0
    Lb = 0
    Lc = 0
    use_a = 0
    use_b = 0
    use_c = 0
    for i, f in enumerate(alloc):
        if f == 0:
            La += L[i]
            use_a += 1
        elif f == 1:
            Lb += L[i]
            use_b += 1
        elif f == 2:
            Lc += L[i]
            use_c += 1
        else:
            pass

    if not all([use_a, use_b, use_c]):
        continue

    score = 0
    score += 10 * (use_a - 1)
    score += 10 * (use_b - 1)
    score += 10 * (use_c - 1)
    score += abs(A - La)
    score += abs(B - Lb)
    score += abs(C - Lc)
    ans = min(ans, score)

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#-30は最初に選んだもの
    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に使うために合成するとして
    return min(ret0, ret1, ret2, ret3)

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

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 = 10**18
for state in product(range(4), repeat=N):
    K = [[] for _ in range(4)]
    for i, l in enumerate(L):
        K[state[i]].append(l)

    cost = 0
    for d, D in zip((A, B, C), K):
        if len(D) == 0:
            cost += 10**18
        cost += (len(D) - 1) * 10
        cost += abs(d - sum(D))
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


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

    """
    解答方針は正しかったが、選んだ竹のA,B,Cへの割り振り方の実装にてこずったので、
    潔く模範解答を写経することにする。
    こういう全列挙は再帰を使うと超あっさり書けるのは聞いてたけど、まだ実践力が足らぬ。。
    再帰を木構造に書き表せたら自然にdfsと結びつくのか！
    """

    def dfs(cur, a, b, c):
        if cur == N: # 全ての竹をチェックし終わった時
            if min(a, b, c) > 0: # a, b, cのどれにもベースの竹が取れている時
                return abs(a - A) + abs(b - B) + abs(c - C) - 30 # 最初の0本から1本への合成にはMP10は使わないので最後に引く
            else:
                return 10**10
        ret0 = dfs(cur + 1, a, b, c)                # curの竹を使わない時
        ret1 = dfs(cur + 1, a + L[cur], b, c) + 10  # curの竹をaに繋いだ時
        ret2 = dfs(cur + 1, a, b + L[cur], c) + 10  # curの竹をbに繋いだ時
        ret3 = dfs(cur + 1, a, b, c + L[cur]) + 10  # curの竹をcに繋いだ時
        return min(ret0, ret1, ret2, ret3)

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





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**4
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,A,B,C = LI()
    l = [NI() for _ in range(N)]
    x = [0] * 3
    ans = INF
    for p in itertools.combinations(range(N),3):
        q = []
        for i in range(N):
            if not i in p: q.append(i)
        for i in range(4**(N-3)):
            for j in range(3): x[j] = l[p[j]]
            mp = 0
            r = i
            for j in range(N-3):
                k = r % 4
                if k > 0:
                    x[k-1] += l[q[j]]
                    mp += 10
                r //= 4
            for a,b,c in itertools.permutations(x):
                ans = min(ans,mp+abs(A-a)+abs(B-b)+abs(C-c))

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**4
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,A,B,C = LI()
    l = [NI() for _ in range(N)]
    m = [i for i in range(N)]
    x = [0, 0, 0]
    ans = INF
    for p in itertools.combinations(m,3):
        q = []
        for i in range(N):
            if not i in p: q.append(i)
        for i in range(4**(N-3)):
            for j in range(3): x[j] = l[p[j]]
            mp = 0
            r = i
            for j in range(N-3):
                k = r % 4
                if k > 0:
                    x[k-1] += l[q[j]]
                    mp += 10
                r //= 4
            for a,b,c in itertools.permutations(x):
                ans = min(ans,mp+abs(A-a)+abs(B-b)+abs(C-c))

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)
 
 
def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
 

    def calc_min_mp(L, a, b, c):
        ans = inf
        quaternary = product(range(4), repeat=n)
        for pattern in quaternary:
            if pattern.count(1) and pattern.count(2) and pattern.count(3):
                needed_mp =  (n - pattern.count(0) - 3) * 10    # 合成魔法の使用回数
                base_abc = [0, 0, 0]    # base_a, base_b, base_c
                for i, num in enumerate(pattern):
                    if num != 0:
                        base_abc[num - 1] += L[i]
                needed_mp += abs(a - base_abc[0]) + abs(b - base_abc[1]) + abs(c - base_abc[2])
                ans = min(ans, needed_mp)
        return ans
 
    
    
    n, a, b, c = mi()
    L = [ii() for _ in range(n)]
 
    print(calc_min_mp(L, a, b, c))
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, A, B, C = map(int, input().split())
    L = [int(input()) for _ in range(N)]
    P = product(range(4), repeat=N)

    # 0 -> not used
    # 1 -> A
    # 2 -> B
    # 3 -> C
    ans = INF
    for pattern in P:
        mp = 0
        a = 0
        b = 0
        c = 0
        for i, p in enumerate(pattern):
            if p == 0:
                continue
            elif p == 1:
                if a != 0:
                    mp += 10
                a += L[i]
            elif p == 2:
                if b != 0:
                    mp += 10
                b += L[i]
            else:
                if c != 0:
                    mp += 10
                c += L[i]

        if a == 0 or b == 0 or c == 0:
            continue

        mp += abs(A - a)
        mp += abs(B - b)
        mp += abs(C - c)

        if mp < ans:
            ans = mp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]
INF = 10**9


def dfs(pos, a_tmp, b_tmp, c_tmp):
    if pos == n:
        if min(a_tmp, b_tmp, c_tmp) > 0:
            return abs(a-a_tmp)+abs(b-b_tmp)+abs(c-c_tmp)-30
        else:
            return INF
    res0 = dfs(pos+1, a_tmp, b_tmp, c_tmp)
    res1 = dfs(pos+1, a_tmp+l[pos], b_tmp, c_tmp)+10
    res2 = dfs(pos+1, a_tmp, b_tmp+l[pos], c_tmp)+10
    res3 = dfs(pos+1, a_tmp, b_tmp, c_tmp+l[pos])+10
    return min(res0, res1, res2, res3)


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')
# ----------------------------------------------------------- #

n, A, B, C = Is()
L = IR(n)

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    INF = 10**18    

    # 最小消費MP
    def rec(i, a, b, c):# i:現在使った本数　a,b,c：現在の竹の長さ
        # 全て竹使ったら理想とのズレを魔法1,2で埋めてく
        if i == N:
            if not a or not b or not c:
                return INF
            return abs(a-A)+abs(b-B)+abs(c-C)
        
        # 竹不採用
        res = rec(i+1, a, b, c)
        # a採用
        if a >= 1:
            res = min(res, rec(i+1, a+L[i], b, c)+10)
        else:
            res = min(res, rec(i+1, a+L[i], b, c))
        # b採用
        if b >= 1:
            res = min(res, rec(i+1, a, b+L[i], c)+10)
        else:
            res = min(res, rec(i+1, a, b+L[i], c))
        
        # c採用
        if c >= 1:
            res = min(res, rec(i+1, a, b, c+L[i])+10)
        else:
            res = min(res, rec(i+1, a, b, c+L[i]))

        return res

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

    print(rec(0, 0, 0, 0))

resolve()

Submission status: Accepted

Solution code:
from itertools import product
def solve():
    N,A,B,C = map(int,input().split())
    models = [A,B,C]
    l = [int(input()) for _ in range(N)]

    comb = list(product([-1,0,1,2],repeat=N))

    mn = float('inf')
    for c in comb:
        sm = 0
        for i in range(3):
            elements = []
            for j in range(N):
                if c[j] == i:
                    elements.append(l[j])
            
            if len(elements) == 0:
                break
            sm += (len(elements) - 1) * 10
            sm += abs(models[i] - sum(elements))
        else:
            mn = min(mn, sm)
    
    print(mn)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

AMP=0
BMP=0
CMP=0
MP=10**5

def dfs(S,N,l,A,B,C):
    A_l=0
    B_l=0
    C_l=0
    A_cnt=0
    B_cnt=0
    C_cnt=0
    if len(S)==N:
        #calcurlate length and merge MP
        for n in range(N):
            if S[n]==0:
                pass
            elif S[n]==1:
                A_l+=l[n]
                A_cnt+=1
            elif S[n]==2:
                B_l+=l[n]
                B_cnt+=1
            else:
                C_l+=l[n]
                C_cnt+=1
        #calculate lengthen and shorten MP
        global MP
        if A_cnt>=1 and B_cnt>=1 and C_cnt>=1:
            MP=min(MP,(A_cnt-1+B_cnt-1+C_cnt-1)*10+abs(A-A_l)+abs(B-B_l)+abs(C-C_l))
        return
    else:
        for n in range(4):
            S.append(n)
            dfs(S,N,l,A,B,C)
            S.pop()

dfs([],N,l,A,B,C)
print(MP)

Submission status: Accepted

Solution code:
import itertools
N, A, B, C = map(int, input().split())
ln = [int(input()) for _ in range(N)]
bit = itertools.product([0, 1, 2, 3], repeat=N)
ans = 10000
for bi in bit:
    cnt = 0
    a = []
    b = []
    c = []
    for i in range(N):
        if bi[i] == 1:
            a.append(ln[i])
        elif bi[i] == 2:
            b.append(ln[i])
        elif bi[i] == 3:
            c.append(ln[i])
    if len(a) == 0 or len(b) == 0 or len(c) == 0:
        continue
    cnt += 10*(max(len(a)-1, 0)+max(len(b)-1, 0)+max(len(c)-1, 0))
    temp = [sum(a), sum(b), sum(c)]
    temp.sort()
    cnt += abs(temp[0]-C) + abs(temp[1]-B) + abs(temp[2]-A)
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

for i in range(n):
    l[i]=int(input())

ans+=abs(l[0]-a)
ans+=abs(l[1]-b)
ans+=abs(l[2]-c)

    
for i in range(4**n):
    ch=0
    mp=0
    s=[0]*4
    for j in range(n):
        for k in range(3):
            if (i>>2*j) % 2**2 ==k:
                if s[k]==0:
                    0
                else:
                    mp+=10
                s[k]+=l[j]
                    
    for p in range(3):
        if s[p]==0:
            #invalid
            ch=1
    if ch==1:
        0
        #invalid
    else:
        mp+=abs(int(s[0]-a))
        mp+=abs(int(s[1]-b))
        mp+=abs(int(s[2]-c))
        if mp<ans:
            ans=mp
            s_ans=s
            j_ans=j
    #print('bin(j),ch,s,mp',bin(i),ch,s,mp,abs(int(s[0]-a)),abs(int(s[1]-b)),abs(int(s[2]-c)))
    
print(ans)
#print(bin(j_ans),s_ans)

Submission status: Accepted

Solution code:
def check(s,e,t):
    global ans
    if(not s or not e or not t):
        return
    ans=min(ans,(len(s)-1)*10+abs(A-sum(s))+(len(e)-1)*10+abs(B-sum(e))+(len(t)-1)*10+abs(C-sum(t)))

def dfs(s,e,t,i):
    if(i==N):
        check(s,e,t)
        return
    dfs(s,e,t,i+1)
    dfs(s+[l[i]],e,t,i+1)
    dfs(s,e+[l[i]],t,i+1)
    dfs(s,e,t+[l[i]],i+1)

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

ans=10**18
dfs([],[],[],0)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: int, B: int, C: int, l: "List[int]"):
    m = None
    for p in product(range(4), repeat=N):
        a = {i for i in range(N) if p[i] == 0}
        b = {i for i in range(N) if p[i] == 1}
        c = {i for i in range(N) if p[i] == 2}
        if not a or not b or not c:
            continue
        md = (
            abs(sum(l[ai] for ai in a) - A) + 10 * (len(a) - 1) +
            abs(sum(l[bi] for bi in b) - B) + 10 * (len(b) - 1) +
            abs(sum(l[ci] for ci in c) - C) + 10 * (len(c) - 1)
        )
        if m is None or m > md:
            m = md

    print(m)


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:
def calc_mp(ls, target):
    ret = 0
    ret += 10 * (len(ls) - 1)
    val = sum(ls)
    ret += abs(val - target)
    return ret


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

pattern = []

for i in range(4 ** n):
    tmp = [0] * n
    val = i
    for j in range(n):
        tmp[j] = val % 4
        val = val // 4
    pattern.append(tmp)

ret = 10 ** 100

for item in pattern:
    if 1 not in item or 2 not in item or 3 not in item:
        continue
    else:
        ones = []
        twos = []
        threes = []
        for i in range(n):
            if item[i] == 1:
                ones.append(l_ls[i])
            elif item[i] == 2:
                twos.append(l_ls[i])
            elif item[i] == 3:
                threes.append(l_ls[i])
        mp = 0
        mp += calc_mp(ones, a)
        mp += calc_mp(twos, b)
        mp += calc_mp(threes, c)
        ret = min(ret, mp)

print(ret)

Submission status: Accepted

Solution code:
# Problem C - Synthetic Kadomatsu

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

# dfs search
class DFS:

    def __init__(self, l_list, N, A, B, C):
        self.l_list = l_list
        self.N = N
        self.A = A
        self.B = B
        self.C = C
        self.INF = float('INF')
        self.ans = float('INF')

    def get_ans(self):
        return self.ans

    def dfs(self, n, a, b, c):
        if n==self.N:
            if not a==0 and not b==0 and not c==0:
                return abs(a-self.A) + abs(b-self.B) + abs(c-self.C)
            else:
                return self.INF

        # 今ある竹を利用しない場合
        self.ans = min(self.ans, self.dfs(n+1, a, b, c))

        # A, B, C を利用する場合
        if a==0:
            self.ans = min(self.ans, self.dfs(n+1, a+self.l_list[n], b, c))
        else:
            self.ans = min(self.ans, self.dfs(n+1, a+self.l_list[n], b, c) + 10)

        if b==0:
            self.ans = min(self.ans, self.dfs(n+1, a, b+self.l_list[n], c))
        else:
            self.ans = min(self.ans, self.dfs(n+1, a, b+self.l_list[n], c) + 10)

        if c==0:
            self.ans = min(self.ans, self.dfs(n+1, a, b, c+self.l_list[n]))
        else:
            self.ans = min(self.ans, self.dfs(n+1, a, b, c+self.l_list[n]) + 10)

        return self.ans

# calc
dfs_obj = DFS(l_list, N, A, B, C)
dfs_obj.dfs(0, 0, 0, 0)

# output
print(dfs_obj.get_ans())

Submission status: Accepted

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
ln = [None] * n
for i in range(n):
    ln[i] = (int(input()))


def dfs(i, ap, bp, cp):
    pattern = [ap, bp, cp]
    if i >= n and [] not in pattern:
        mp = 0
        for p in pattern:
            mp += max([0, len(p) - 1]) * 10
        mp += abs(a - sum(pattern[0]))
        mp += abs(b - sum(pattern[1]))
        mp += abs(c - sum(pattern[2]))
        return mp
    elif i >= n:
        return float('inf')
    else:
        return min([
            dfs(i + 1, ap + [ln[i]], bp, cp),
            dfs(i + 1, ap, bp + [ln[i]], cp),
            dfs(i + 1, ap, bp, cp + [ln[i]]),
            dfs(i + 1, ap, bp, cp)
        ])


result = dfs(0, [], [], [])
print(result)

Submission status: Accepted

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

def cost(group,target):
    res = 10*(len(group)-1)
    return res + abs(sum(group)-target)

ans = []
for i in range(1<<(2*N)):
    groupA = []
    groupB = []
    groupC = []
    for j in range(N):
        s = i>>(2*j)
        if (s & 3) == 3:
            groupA.append(L[j])
        elif (s & 2) == 2:
            groupB.append(L[j])
        elif (s & 1) == 1:
            groupC.append(L[j])
    
    if len(groupA)==0 or len(groupB)==0 or len(groupC)==0:
        pass
    else:
        ans.append(cost(groupA,A)+cost(groupB,B)+cost(groupC,C))
print(min(ans))