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:
def B10N(X,B):
    if X//B!=0: return B10N(X//B,B)+str(X%B)
    return str(X%B)

N,A,B,C = (int(X) for X in input().split())
Li = [int(input()) for X in range(0,N)]
CostM = pow(10,9)
for T in range(0,pow(4,N)):
    Cho = list(B10N(T,4).zfill(N))
    if Cho.count('1')>0 and Cho.count('2')>0 and Cho.count('3')>0:
        Cost = 0
        ALi = [Li[X] for X,Y in enumerate(Cho) if Y=='1']
        BLi = [Li[X] for X,Y in enumerate(Cho) if Y=='2']
        CLi = [Li[X] for X,Y in enumerate(Cho) if Y=='3']
        SyC = (len(ALi)+len(BLi)+len(CLi)-3)*10
        LeC = abs(sum(ALi)-A)+abs(sum(BLi)-B)+abs(sum(CLi)-C)
        if SyC+LeC<CostM: CostM = SyC+LeC
print(CostM)

Submission status: Accepted

Solution code:
from functools import lru_cache
N, A, B, C, *L = map(int, open(0).read().split())


@lru_cache(None)
def popcnt(n):
    return bin(n).count('1')


@lru_cache(None)
def synth(bit):
    length = 0
    for i in range(N):
        if bit >> i & 1:
            length += L[i]
    return length


ans = 1 << 60
for bit1 in range(1, 1 << N):
    if popcnt(bit1) >= N-1:
        continue
    length1 = synth(bit1)

    for bit2 in range(1, 1 << N):
        if bit1 & bit2:
            continue
        if popcnt(bit1 | bit2) == N:
            continue
        length2 = synth(bit2)

        for bit3 in range(1, 1 << N):
            if bit1 & bit3 or bit2 & bit3:
                continue

            length3 = synth(bit3)
            c, b, a = sorted([length1, length2, length3])

            cost = 10*(popcnt(bit1 | bit2 | bit3)-3) + abs(C-c) + abs(B-b) + abs(A-a)
            if cost < ans:
                ans = cost

print(ans)

Submission status: Accepted

Solution code:
n,a,b,c=map(int,input().split())
l=[int(input())for _ in range(n)]
def dfs(i,x,y,z):
 if i==n:return abs(a-x)+abs(b-y)+abs(c-z)-30if min(x,y,z)>0else 10**9
 return min(dfs(i+1,x,y,z),dfs(i+1,x+l[i],y,z)+10,dfs(i+1,x,y+l[i],z)+10,dfs(i+1,x,y,z+l[i])+10)
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 ** 9
for groups in product(range(4), repeat=N):
    length_a = 0
    length_b = 0
    length_c = 0
    cost_a = -10
    cost_b = -10
    cost_c = -10

    for group, length in zip(groups, L):
        if group == 1:
            length_a += length
            cost_a += 10
        elif group == 2:
            length_b += length
            cost_b += 10
        elif group == 3:
            length_c += length
            cost_c += 10

    if 0 in {length_a, length_b, length_c}:
        continue

    ans = min(ans, sum([
        abs(A - length_a),
        abs(B - length_b),
        abs(C - length_c),
        cost_a,
        cost_b,
        cost_c,
    ]))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product, permutations

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

ans = 10 ** 9
for groups in product(range(4), repeat=N):
    items = []
    group_a = []
    group_b = []
    group_c = []

    for group, length in zip(groups, L):
        if group == 0:
            items.append((length, 0))
        elif group == 1:
            group_a.append(length)
        elif group == 2:
            group_b.append(length)
        elif group == 3:
            group_c.append(length)

    if group_a:
        items.append((sum(group_a), (len(group_a) - 1) * 10))
    if group_b:
        items.append((sum(group_b), (len(group_b) - 1) * 10))
    if group_c:
        items.append((sum(group_c), (len(group_c) - 1) * 10))

    if len(items) < 3:
        continue

    for one, two, three in permutations((A, B, C), r=3):
        cost = 0
        _items = list(items)

        _items = sorted(_items, key=lambda x: (abs(x[0] - one), x[1]))
        cost += abs(_items[0][0] - one) + _items[0][1]
        _items.pop(0)

        _items = sorted(_items, key=lambda x: (abs(x[0] - two), x[1]))
        cost += abs(_items[0][0] - two) + _items[0][1]
        _items.pop(0)

        _items = sorted(_items, key=lambda x: (abs(x[0] - three), x[1]))
        cost += abs(_items[0][0] - three) + _items[0][1]

        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)]
def f(X):
  global N,A,B,C,L
  if len(X)==N:
    a,b,c=0,0,0
    for i in range(N):
      a+=X[i][0]
      b+=X[i][1]
      c+=X[i][2]
    if min(a,b,c)==0:
      return 10**16
    else:
      return abs(A-a)+abs(B-b)+abs(C-c)
  return min(f(X+[[0,0,0]]),f(X+[[L[len(X)],0,0]])+10,f(X+[[0,L[len(X)],0]])+10,f(X+[[0,0,L[len(X)]]])+10)

print(f([])-30)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter

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

bb = list(itertools.product(le, repeat=n))
new = []
ans = 1145141919810

for ll in bb:
    aa = 0
    con = [0]*4
    amo = [0]*4
    for i in range(n):
        con[ll[i]] += l[i]
        amo[ll[i]] += 1
        
    if con[1] > 0 and con[2] > 0 and con[3] > 0:
        for j in range(1,4):
            aa += (amo[j] - 1) * 10
        aa += abs(con[1] - a)
        aa += abs(con[2] - b)
        aa += abs(con[3] - c)
        
        ans = min(ans,aa)
        
    else:
        continue
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

INF = 10 ** 9

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


def estimate(lst):
    if any(not p for p in lst):
        return INF

    ret = 0
    for p, g in zip(lst, A):
        ret += abs(g - sum(p)) + (len(p) - 1) * 10
    return ret


ans = INF
for prd in product(range(4), repeat=N):
    pieces = [[] for _ in range(3)]
    for bamboo_ind, target_kadomatsu in enumerate(prd):
        if target_kadomatsu == 3: continue
        pieces[target_kadomatsu].append(L[bamboo_ind])
    if ans > (res := estimate(pieces)):
        ans = res
print(ans)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
l=[int(input()) for _ in range(N)]
inf=10**18
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
  res0 = dfs(cur+1,a,b,c)
  res1 = dfs(cur+1,a+l[cur],b,c)+10
  res2 = dfs(cur+1,a,b+l[cur],c)+10
  res3 = dfs(cur+1,a,b,c+l[cur])+10
  return min(res0,res1,res2,res3)
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
from itertools import product

n,a,b,c,*L = map(int,open(0).read().split())

li1 = [1,2,3,4]
ans = 10**10
for v in product(li1,repeat = n):
    num = 0
    A,B,C = [],[],[]
    for i in range(n):
        if v[i] == 1:
            A.append(L[i])
        elif v[i] == 2:
            B.append(L[i])
        elif v[i] == 3:
            C.append(L[i])

    if A and B and C:
        num +=abs(sum(A)-a) + max(0,(len(A)-1)*10) + abs(sum(B)-b) + max(0,(len(B)-1)*10)+ abs(sum(C)-c) + max(0,(len(C)-1)*10)
        ans = min(ans,num)

print(ans)

Submission status: Accepted

Solution code:
n,a,b,c,*L = map(int,open(0).read().split())
L.sort(reverse = True)

from itertools import product
from copy import deepcopy
li1 = [4,1,2,3]
ans = 10**10
for v in product(li1,repeat = n):
    #print(v)
    num = 0
    A,B,C,NO = [],[],[],[]
    for i in range(n):
        if v[i] == 1:
            #if L[i] not in (a,b,c):
            A.append(L[i])
        elif v[i] == 2:
            #if L[i] not in (a,b,c):
            B.append(L[i])
        elif v[i] == 3:
            #if L[i] not in (a,b,c):
            C.append(L[i])
        elif v[i] == 4:
            NO.append(L[i])
    if A and B and C:
        num +=abs(sum(A)-a) + max(0,(len(A)-1)*10) + abs(sum(B)-b) + max(0,(len(B)-1)*10)+ abs(sum(C)-c) + max(0,(len(C)-1)*10)
        ans = min(ans,num)
    #print(num,ans,A,B,C,max(0,(len(A)-1)*10),max(0,(len(B)-1)*10))
print(ans)

Submission status: Accepted

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


def dfs(times, a, b, c):  
    if times == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    no_pattern = dfs(times + 1, a, b, c)
    a_pattern = dfs(times + 1, a + L[times], b, c) + 10
    b_pattern = dfs(times + 1, a, b + L[times], c) + 10
    c_pattern = dfs(times + 1, a, b, c + L[times]) + 10

    return min(no_pattern, a_pattern, b_pattern, c_pattern)


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

Submission status: Accepted

Solution code:
import sys
from itertools import product
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, A, B, C = map(int, input().split())
    goal = [A, B, C]
    L = list(int(input()) for _ in range(n))

    res = f_inf
    for pattern in product([0, 1, 2, 3], repeat=n):
        cnt = [0] * 3
        length = [0] * 3
        for idx, p in enumerate(pattern):
            if p != 0:
                length[p - 1] += L[idx]
                cnt[p - 1] += 1
        mp = 0
        for i in range(3):
            if cnt[i] == 0:
                break
            mp += abs(goal[i] - length[i]) + (cnt[i] - 1) * 10
        else:
            res = min(res, mp)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B, C = mapint()
Ls = [int(input()) for _ in range(N)]
ans = 10**18
def dfs(a, b, c, idx, magic):
    global ans
    if idx==N:
        if a==0 or b==0 or c==0:
            return
        magic -= 30
        magic += abs(A-a)
        magic += abs(B-b)
        magic += abs(C-c)
        ans = min(ans, magic)
        return
    nx = Ls[idx]
    dfs(a+nx, b, c, idx+1, magic+10)
    dfs(a, b+nx, c, idx+1, magic+10)
    dfs(a, b, c+nx, idx+1, magic+10)
    dfs(a, b, c, idx+1, magic)

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())
abc = [C, B, A]
lst = [int(input()) for _ in range(N)]

ans = []
for l in product([0, 1, 2, 3], repeat=N):
    cnt = [[], [], [], []]
    for i, ll in enumerate(l):
        cnt[ll].append(lst[i])
    mp = 0
    p = []
    for i in cnt[:3]:
        if len(i) != 0: mp += (len(i) - 1) * 10
        p.append(sum(i))
    p.sort()
    if p[0]!=0:
        for i in range(3):
            mp += abs(p[i] - abc[i])
        ans.append(mp)
print(min(ans))

Submission status: Accepted

Solution code:
from itertools import permutations,product
N,A,B,C = map(int,input().split())
L = [int(input()) for _ in range(N)]
G = {0:[],1:[],2:[]}
cmin = 10**5
for x in permutations(range(N),3):
    for y in product(range(4),repeat=N-3):
        G[0] = [x[0]]
        G[1] = [x[1]]
        G[2] = [x[2]]
        G[3] = []
        Ind = list(range(N))
        Ind.remove(x[0])
        Ind.remove(x[1])
        Ind.remove(x[2])
        for i in range(N-3):
            G[y[i]].append(Ind[i])
        cA = 0
        nA = len(G[0])
        cA = (nA-1)*10
        xA = 0
        for j in range(nA):
            xA += L[G[0][j]]
        cA += abs(A-xA)
        cB = 0
        nB = len(G[1])
        cB = (nB-1)*10
        xB = 0
        for j in range(nB):
            xB += L[G[1][j]]
        cB += abs(B-xB)
        cC = 0
        nC = len(G[2])
        cC = (nC-1)*10
        xC = 0
        for j in range(nC):
            xC += L[G[2][j]]
        cC += abs(C-xC)
        cmin = min(cmin,cA+cB+cC)
print(cmin)

Submission status: Accepted

Solution code:
n,a,b,c=map(int,input().split())
bam=[]
for i in range(n):
  bam.append(int(input()))
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
ans=10**18
for i in range(4**n):
  s=base10toN(i, 4)
  slist=[]
  for i in range(len(s)):
    slist.append(s[i])
  slist.reverse()
  for i in range(n-len(s)):
    slist.append('0')
  slist.reverse()
  s1=[]
  s2=[]
  s3=[]
  for i in range(n):
    if slist[i]=='1':
      s1.append(bam[i])
    if slist[i]=='2':
      s2.append(bam[i])
    if slist[i]=='3':
      s3.append(bam[i])
  if len(s1)==0 or len(s2)==0 or len(s3)==0:
    continue
  anscan=abs(sum(s1)-a)+abs(sum(s2)-b)+abs(sum(s3)-c)+10*(len(s1)-1)+10*(len(s2)-1)+10*(len(s3)-1)
  ans=min(ans,anscan)
print(ans)

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N, A, B, C = LI()
    L = [I()for _ in range(N)]
    loop = (1<<(2*N))
    ans = inf
    for l in range(loop):
        cost = 0
        bamboo_A = 0
        bamboo_B = 0
        bamboo_C = 0
        for j in range(N):
            if l&(1<<(2*j))>0:
                if l&(1<<(2*j+1))>0:
                    cost += 10
                    bamboo_A += L[j]
                else:
                    cost += 10
                    bamboo_B += L[j]
            else:
                if l&(1<<(2*j+1))>0:
                    cost += 10
                    bamboo_C += L[j]
        if bamboo_A==0 or bamboo_B==0 or bamboo_C==0:
            continue
        cost += abs(A-bamboo_A) + abs(B-bamboo_B) + abs(C-bamboo_C) - 30
        ans = min(ans,cost)

    print(ans)
    return

def examD():
    N = I()
    P = LI()
    O_ = [-1]*N
    start = P[0]-1
    for i in range(N):
        O_[P[i]-1] = i
    #print(O_,start)
    A = [1]*N
    B = [1]*N
    for i in range(start+1,N):
        cur = O_[i]-O_[i-1]
        if cur>0:
            A[i] = A[i-1] + (cur+1)
            B[i] = B[i-1] - 1
        else:
            A[i] = A[i-1] + 1
            B[i] = B[i-1] - (-cur+1)
    for i in range(start)[::-1]:
        cur = O_[i]-O_[i+1]
        if cur>0:
            B[i] = B[i+1] + (cur+1)
            A[i] = A[i+1] - 1
        else:
            B[i] = B[i+1] + 1
            A[i] = A[i+1] - (-cur+1)
    if A[0]<1:
        add = (1-A[0])
        for i in range(N):
            A[i] += add
    if B[-1]<1:
        add = (1-B[-1])
        for i in range(N):
            B[i] += add

    print(" ".join(map(str,A)))
    print(" ".join(map(str,B)))
    return

def examE():
    return

def examF():
    ans = 0
    print(ans)
    return


from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
9
7 3 9 1 8 4 5 6 2
"""

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

N,A,B,C = map(int,input().split())
LIS = []
for i in range(N):
  temp = int(input())
  LIS.append(temp)
M = [0,1,2,3]

X = list(itertools.product(M, repeat=N))
INF = float("inf")
ans = INF
#print(X)
for L in X:
  ts = set(L)
  dic = defaultdict(int)
  #print(ts,L)
  if 1 not in ts or 2 not in ts or 3 not in ts:
    continue
  temp = [-1,0,0,0]
  for i,v in enumerate(L):
    temp[v] += LIS[i]
    dic[v] += 1
  temp = temp[1:]
  temp.sort(reverse = True)
  atemp = abs(temp[0]-A)+abs(temp[1]-B)+abs(temp[2]-C)
  atemp += 10*(dic[1]+dic[2]+dic[3]-3)
  ans = min(atemp,ans)
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 i in range(4**n):
  T = [0]*4
  C = [0]*4
  for j, l in enumerate(L):
    T[(i>>(2*j))&3] += l
    C[(i>>(2*j))&3] += 1
  ta, tb, tc = T[1:]
  if ta == 0 or tb == 0 or tc == 0:
    continue
  temp = 0
  temp += max(C[1]-1, 0)
  temp += max(C[2]-1, 0)
  temp += max(C[3]-1, 0)
  temp *= 10
  temp += abs(a-ta) + abs(b-tb) + abs(c-tc)
  ans = min(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, a, b, c =map(int, input().split())
ans = float("inf")
take = [int(input()) for i in range(n)]

for pattern in itertools.product(range(4), repeat=n):
    abc = [0]*3
    mp=0
    for i in range(n):
      if pattern[i]==3:
        continue
      else:
        if abc[pattern[i]] != 0:
          mp+=10
        abc[pattern[i]]+=take[i]
    
    mp+=abs(a-abc[0])
    mp+=abs(b-abc[1])
    mp+=abs(c-abc[2])
    for i in range(3):
      if abc[i]==0:
        mp=float("inf")
        break
    ans = min(ans, mp)
    
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:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

ans = float('inf')
for pattern in itertools.product(range(4), repeat=n):
    cnt = [0] * 4
    length = [0] * 4
    mp = 0
    for i, v in enumerate(pattern):
        if cnt[v] != 0 and 0 <= v <= 2:
            mp += 10
        cnt[v] += 1
        length[v] += l[i]
    if cnt[0] > 0 and cnt[1] > 0 and cnt[2] > 0:
        mp += abs(a - length[0]) + abs(b - length[1]) + abs(c - length[2])
        ans = min(ans, mp)

print(ans)

Submission status: Accepted

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


def test(n, a, b, c, na, nb, nc):
    """
    :param n: 使用している竹の本数
    :param a: 竹aの長さ
    :param b: 竹bの長さ
    :param c: 竹cの長さ
    :param na: 竹aに使用した本数
    :param nb: 竹bに使用した本数
    :param nc: 竹cに使用した本数
    :return: 消費MP
    """
    if n == N:
        # 最終MPの確定
        if min(na, nb, nc) == 0:
            return 10**9
        else:
            mp = 0
            mp += (na-1) * 10 if na else 0
            mp += (nb-1) * 10 if nb else 0
            mp += (nc-1) * 10 if nc else 0
            mp += abs(A-a) + abs(B-b) + abs(C-c)
            return mp
    else:
        mp1 = test(n+1, a, b, c, na, nb, nc)  # 使用しない
        mp2 = test(n+1, a+L[n], b, c, na+1, nb, nc)  # 竹aに適用
        mp3 = test(n+1, a, b+L[n], c, na, nb+1, nc)  # 竹bに適用
        mp4 = test(n+1, a, b, c+L[n], na, nb, nc+1)  # 竹cに適用
        return min(mp1, mp2, mp3, mp4)


print(test(0, 0, 0, 0, 0, 0, 0))

Submission status: Accepted

Solution code:
#bit全探索の亜種(4種全探索)
#itertools.product([0,1,2,3],repeat=N)

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

ans = 10**10
for ABCD in itertools.product([0,1,2,3],repeat=N):
    tmp = [[] for i in range(4)]
    for i in range(0,N,1):
        tmp[ABCD[i]].append(l[i])
    score = 0
    owaowari = False
    for i in range(3):#Dはくっ付ける必要なし
        if len(tmp[i])==0:
            owaowari = True
            break
        score+=10*max(len(tmp[i])-1,0)
    if owaowari: continue
    score+=abs(A-sum(tmp[0]))
    score+=abs(B-sum(tmp[1]))
    score+=abs(C-sum(tmp[2]))
    ans = min(ans,score)


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()))
    
def dfs(bamboo, a, b, c):
    if bamboo == N:
        if min(a, b, c) > 0:
            return abs(A-a) + abs(B-b) + abs(C-c) - 30
        else:
            return 10**10
    else:
        ans1 = dfs(bamboo+1, a, b, c)
        ans2 = dfs(bamboo+1, a+l[bamboo], b, c) + 10
        ans3 = dfs(bamboo+1, a, b+l[bamboo], c) + 10
        ans4 = dfs(bamboo+1, a, b, c+l[bamboo]) + 10
        return min(ans1, ans2, ans3, ans4)
        
print(dfs(0, 0, 0, 0))

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n,a,b,c = lr()
l = [ir() for i in range(n)]
l.sort(reverse=True)

def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

ans = inf

for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            now = [l[i],l[j],l[k]]
            ret = [0 for w in range(5-(n-3))]
            pre = 0
            for g in range(n):
                if g!=i and g!=j and g!=k:
                    ret.append(l[g])
            for h in range(4**(n-3)):
                now = [l[i], l[j], l[k]]
                pre = 0
                judge = base10to(h, 4)
                tmp = ''
                for w in range(5-len(judge)):
                    tmp = ''.join([tmp,'0'])
                judge = ''.join([tmp,judge])

                for p,t in enumerate(judge):
                    if t == '1':
                        now[0]+=ret[p]
                        pre+=10
                    elif t == '2':
                        now[1]+=ret[p]
                        pre+=10
                    elif t == '3':
                        now[2]+=ret[p]
                        pre+=10
                now.sort(reverse=True)
                ans = min(ans,pre+abs(a-now[0])+abs(b-now[1])+abs(c-now[2]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,A,B,C = I()
l = [i() 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 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())
from itertools import product
l = [int(input()) for i in range(N)]
ans = []
for i in product(range(4), repeat=N):
  a = 0
  b = 0
  c = 0
  d = 0
  for j in range(N):
    if i[j]:
      d += 1
      if i[j] == 1:
        a += l[j]
      elif i[j] == 2:
        b += l[j]
      else:
        c += l[j]
  if a * b * c:
    ans += [abs(A - a) + abs(B - b) + abs(C - c) + (d - 3) * 10]
print(min(ans))

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
l = [int(input()) for i 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')
    r1 = dfs(cur+1,a,b,c)
    r2 = dfs(cur+1,a+l[cur],b,c) +10
    r3 = dfs(cur+1,a,b+l[cur],c) + 10
    r4 = dfs(cur+1,a,b,c+l[cur]) + 10
    return min(r1,r2,r3,r4)
print(dfs(0,0,0,0))
#全てのバリエーション試す、dfs

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 = 1001001001
for x in product(range(4), repeat=n):
    s = [0] * 4
    t = -3
    for i in range(n):
        t += x[i] < 3
        s[x[i]] += l[i]
    s.pop()
    if 0 in s:
        continue
    ans = min(ans, t * 10 + abs(s[0] - a) + abs(s[1] - b) + abs(s[2] - c))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N,A,B,C=map(int,input().split())
l=[]
for _ in range(N):
    l.append(int(input()))
ans=10**18
for i in product(range(4),repeat=N):
    mp=0
    bamboo=[0,0,0]
    for j in range(N):
        s=i[j]
        if s==3:
            continue
        else:
            if bamboo[s]!=0:
                mp+=10
            bamboo[s]+=l[j]
    if bamboo[0]==0 or bamboo[1]==0 or bamboo[2]==0:
        continue
    mp+=abs(A-bamboo[0])
    mp+=abs(B-bamboo[1])
    mp+=abs(C-bamboo[2])
    ans=min(ans,mp)
print(ans)

Submission status: Accepted

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

def rec(i, a, b, c):
  if i == N:
    if not a or not b or not c: return float('inf')
    return abs(a-A) + abs(b-B) + abs(c-C)
  
  ret = rec(i+1, a, b, c)
  
  ret = min(ret, rec(i+1, a+L[i], b, c) + (10 if a else 0))
  ret = min(ret, rec(i+1, a, b+L[i], c) + (10 if b else 0))
  ret = min(ret, rec(i+1, a, b, c+L[i]) + (10 if c else 0))
  
  return ret

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, A, B, C = getNM()
L = getArray(N)

def counter(array):
    if (1 in array) and (2 in array) and (3 in array):
        opt = [0, 0, 0, 0]
        # 合成に10pかかる
        cnt = 0
        for i in range(len(array)):
            if opt[array[i]] > 0:
                cnt += 1
            if array[i] >= 1:
                opt[array[i]] += L[i]

        res = cnt * 10
        res += abs(opt[1] - A)
        res += abs(opt[2] - B)
        res += abs(opt[3] - C)

        return res

    else:
        return float('inf')

ans = float('inf')
def four_pow(i, array):
    global ans
    if i == N:
        ans = min(ans, counter(array))
        return
    # 4 ** Nループ
    for j in range(4):
        new_array = array + [j]
        four_pow(i + 1, new_array)

four_pow(0, [])
print(ans)

"""
4 ** Nループ
N = 5
L = [1, 1, 1, 1, 1]
cnt = 0
def four_pow(i, array):
    global cnt
    if i == N:
        cnt += 1
        return
    # ここの4を変えてrootを変更
    for j in range(4):
        new_array = array + [j]
        four_pow(i + 1, new_array)

four_pow(0, [])
# 1024
print(cnt)
"""