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:
#template
from collections import Counter
def inputlist(): return [int(k) for k in input().split()]
def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)
#template
ans = 10**18
N,A,B,C = inputlist()
l = [0]*N
for i in range(N):
    l[i] = int(input())

n = 4**N

def count(li,n):
    co = 0
    co += (len(li)-1)*10
    co += abs(sum(li) - n)
    return co

for i in range(n+1):
    k = base10to(i,4)
    if len(k) < N:
        d = N-len(k)
        for j in range(d):
            k = '0'+k
    c = Counter(list(k))
    if c['1'] < 1 or c['2'] < 1 or c['3'] < 1:
        continue
    ans_k = 0
    la = []
    lb = []
    lc = []
    for j in range(N):
        if k[j] == '1':
            la.append(l[j])
        if k[j] == '2':
            lb.append(l[j])
        if k[j] == '3':
            lc.append(l[j])
    ans_k += count(la,A) + count(lb,B) + count(lc,C)
    ans = min(ans,ans_k)
print(ans)

Submission status: Accepted

Solution code:
def base_10_to_n(X, n):
    if (int(X/n)):
        return base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

def f(a,la,A):
    if la == 0:
        return 1e12
    return (la-1)*10 + abs(a-A)

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

ans = 1e12
for i in range(4**N+1):
    tmp = list(base_10_to_n(i,4).zfill(N))
    a,la,b,lb,c,lc = 0,0,0,0,0,0
    for s,t in zip(tmp,l):
        if s == "1":
            a += t
            la += 1
        elif s == "2":
            b += t
            lb += 1
        elif s == "3":
            c += t
            lc += 1
    ans = min(ans,f(a,la,A)+f(b,lb,B)+f(c,lc,C))

print(ans)

Submission status: Accepted

Solution code:
def base_10_to_n(X, n):
    if (int(X/n)):
        return base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

def f(a,A):
    if len(a) == 0:
        return 1e12
    return (len(a)-1)*10 + abs(sum(a)-A)

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

ans = 1e12
for i in range(4**N+1):
    tmp = list(base_10_to_n(i,4).zfill(N))
    a,b,c = [],[],[]
    for s,t in zip(tmp,l):
        if s == "1":
            a.append(t)
        elif s == "2":
            b.append(t)
        elif s == "3":
            c.append(t)
    ans = min(ans,f(a,A)+f(b,B)+f(c,C))

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(cnt,a,b,c):
    if cnt == N:
    #30引くのは元のa,b,cだけならコストかからんから
        return abs(A-a)+abs(B-b) + abs(C-c)-30 if min(a,b,c)>0 else INF
    
    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)


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)]

ans = float('inf')
for i in range(2**n):
    for j in range(2**n):
        where = [0]*n
        x,y = i,j
        b = 0
        while x > 0 or y > 0:
            where[b] += (x&1) + 2*(y&1)
            b += 1
            x,y = x >> 1 , y >> 1
        cnt = -30
        ABC = [0,0,0]
        for x,w in enumerate(where):
            if w == 0:continue
            ABC[w-1] += L[x]
            cnt += 10
        if 0 in ABC:continue
        ans = min(ans, cnt + abs(ABC[0] - A) + abs(ABC[1] - B) + abs(ABC[2] - C))
print(ans)

Submission status: Accepted

Solution code:
import math
N, A, B, C = 5, 100, 90, 80
ARR = [
    98,
    40,
    30,
    21,
    80
]

# N,A,B,C = 8, 100, 90, 80
# ARR = [
#     100,
#     100,
#     90,
#     90,
#     90,
#     80,
#     80,
#     80,
# ]


# N,A,B,C,= 8, 1000, 800, 100
# ARR = [
#     300,
#     333,
#     400,
#     444,
#     500,
#     555,
#     600,
#     666,
# ]

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

def calculate(n, arr, a, b, c):
    result = []
    for i in range(4 ** n):
        materialA = set()
        materialB = set()
        materialC = set()
        materialNone = set()
        for j in range(n):
            s = (i >> 2 * j & 1)
            t = (i >> (2 * j + 1) & 1)
            if (s == 0) and (t == 0):
                materialA.add(j)
            if (s == 1) and (t == 0):
                materialB.add(j)
            if (s == 0) and (t == 1):
                materialC.add(j)
            if (s == 1) and (t == 1):
                materialNone.add(j)

        ok, mp = judge(n, arr, a, b, c, materialA, materialB, materialC, materialNone)
        if ok:
            result.append(mp)
    print(int(min(result)))

def judge(n, arr, a, b, c, materialA, materialB, materialC, materialNone):


    if materialNone == n:
        return False, -1

    if len(materialA) == 0:
        return False, -1

    if len(materialB) == 0:
        return False, -1

    if len(materialC) == 0:
        return False, -1

    mpA = 0
    a = a - calculateResult(arr,materialA)
    mpA += math.fabs(a)
    if len(materialA) > 1:
        mpA += 10 * (len(materialA) - 1)

    mpB = 0
    b = b - calculateResult(arr,materialB)
    mpB += math.fabs(b)
    if len(materialB) > 1:
        mpB += 10 * (len(materialB) - 1)

    mpC = 0
    c = c - calculateResult(arr,materialC)
    mpC += math.fabs(c)
    if len(materialC) > 1:
        mpC += 10 * (len(materialC) - 1)


    return True,mpA+mpB+mpC

def calculateResult(arr,material):
    result = 0
    for m in material:
        result = result + arr[m]
    return result

calculate(N, ARR, A, B, C)

Submission status: Accepted

Solution code:
import math
N, A, B, C = 5, 100, 90, 80
ARR = [
    98,
    40,
    30,
    21,
    80
]

# N,A,B,C = 8, 100, 90, 80
# ARR = [
#     100,
#     100,
#     90,
#     90,
#     90,
#     80,
#     80,
#     80,
# ]


# N,A,B,C,= 8, 1000, 800, 100
# ARR = [
#     300,
#     333,
#     400,
#     444,
#     500,
#     555,
#     600,
#     666,
# ]

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

def calculate(n, arr, a, b, c):
    result = []
    for i in range(4 ** n):
        materialA = set()
        materialB = set()
        materialC = set()
        materialNone = set()
        for j in range(n):
            s = (i >> 2 * j & 1)
            t = (i >> (2 * j + 1) & 1)
            if (s == 0) and (t == 0):
                materialA.add(j)
            if (s == 1) and (t == 0):
                materialB.add(j)
            if (s == 0) and (t == 1):
                materialC.add(j)
            if (s == 1) and (t == 1):
                materialNone.add(j)

        ok, mp = judge(n, arr, a, b, c, materialA, materialB, materialC, materialNone)
        if ok:
            result.append(mp)
    print(int(min(result)))

def judge(n, arr, a, b, c, materialA, materialB, materialC, materialNone):


    if materialNone == n:
        return False, -1

    if len(materialA & materialB) > 0:
        return False, -1

    if len(materialA & materialC) > 0:
        return False, -1

    if len(materialB & materialC) > 0:
        return False, -1

    if len(materialA) == 0:
        return False, -1

    if len(materialB) == 0:
        return False, -1

    if len(materialC) == 0:
        return False, -1

    mpA = 0
    a = a - calculateResult(arr,materialA)
    mpA += math.fabs(a)
    if len(materialA) > 1:
        mpA += 10 * (len(materialA) - 1)

    mpB = 0
    b = b - calculateResult(arr,materialB)
    mpB += math.fabs(b)
    if len(materialB) > 1:
        mpB += 10 * (len(materialB) - 1)

    mpC = 0
    c = c - calculateResult(arr,materialC)
    mpC += math.fabs(c)
    if len(materialC) > 1:
        mpC += 10 * (len(materialC) - 1)


    return True,mpA+mpB+mpC

def calculateResult(arr,material):
    result = 0
    for m in material:
        result = result + arr[m]
    return result

calculate(N, ARR, A, B, C)

Submission status: Accepted

Solution code:

def solve():

    N, A, B, C = map(int, input().split())
    llist = [int(input()) for i in range(N)]
    inf = 10**9

    def dfs(cursol, a, b, c):
        # すべての竹に対して合成魔法を試したら、不足分は延長 or 短縮魔法を使う
        if cursol == N:
            return abs(A-a)+abs(B-b)+abs(C-c)-30 if min(a, b, c) > 0 else inf

        return min(
            dfs(cursol+1, a, b, c),
            # 合成魔法を使っているので+10が必要
            dfs(cursol+1, a+llist[cursol], b, c)+10,
            dfs(cursol+1, a, b+llist[cursol], c)+10,
            dfs(cursol+1, a, b, c+llist[cursol])+10
        )

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
l=[int(input()) for _ in range(N)]
INF=10**9
def chk(i,a,b,c):
    if i==N:
        if min(a,b,c)>0:
            return abs(A-a)+abs(B-b)+abs(C-c)-30
        else:
            return INF
    r0=chk(i+1,a,b,c)
    r1=chk(i+1,a+l[i],b,c)+10
    r2=chk(i+1,a,b+l[i],c)+10
    r3=chk(i+1,a,b,c+l[i])+10
    return min(r0,r1,r2,r3)
print(chk(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本を合成するのに必要な合成回数はn-1回なので、A,B,Cに対して1回ずつ余分に１０を足している
    # よって１０＊３を引いてあげる
    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 = [int(input()) for _ in range(n)]
def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
ans =  10**6
for i in range(4**n):
  s = Base_10_to_n(i, 4)
  s = s.zfill(n)
  l_temp = [0, 0, 0]
  cnt = [0, 0, 0]
  for num, j in enumerate(s):
    if int(j):
      l_temp[int(j)-1] += l[num]
      cnt[int(j)-1] += 1
  if 0 in cnt:
    continue
  else:
    ans_temp = 10*(sum(cnt)-3) +abs(A-l_temp[0]) + abs(B-l_temp[1]) + abs(C-l_temp[2])
    ans = min(ans, ans_temp) 
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
l=[int(input()) for _ in range(N)]
INF=10**9
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF 
  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:
def dfs(now1, now2, now3, d):
    if d==N:
        if min(now1, now2, now3)==0:
            return 10**18
            
        return abs(A-now1)+abs(B-now2)+abs(C-now3)
        
    res = 10**18
    res = min(res, dfs(now1+l[d], now2, now3, d+1)+10)
    res = min(res, dfs(now1, now2+l[d], now3, d+1)+10)
    res = min(res, dfs(now1, now2, now3+l[d], d+1)+10)
    res = min(res, dfs(now1, now2, now3, d+1))
    
    return res

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

Submission status: Accepted

Solution code:
def solve(i, al, bl, cl, nu):
    if i == N:
        lal, lbl, lcl = len(al), len(bl), len(cl)
        if lal == 0 or lbl == 0 or lcl == 0:
            return
        mp = 0
        mp += 10*(len(al)-1) if len(al) > 1 else 0
        mp += 10*(len(bl)-1) if len(bl) > 1 else 0
        mp += 10*(len(cl)-1) if len(cl) > 1 else 0
        mp += abs(sum(al)-A)
        mp += abs(sum(bl)-B)
        mp += abs(sum(cl)-C)
        global min_mp
        min_mp = min(min_mp, mp)
        return
    solve(i+1, al+[L[i]], bl, cl, nu)
    solve(i+1, al, bl+[L[i]], cl, nu)
    solve(i+1, al, bl, cl+[L[i]], nu)
    solve(i+1, al, bl, cl, nu+[L[i]])


N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]
min_mp = 10**10
solve(0, [], [], [], [])
print(min_mp)

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 = [int(input()) for i in range(N)]

from itertools import product

ans = 10**10
for pro in product([0,1,2,3], repeat= N):
    cost,lena,lenb,lenc = -30,0,0,0
    for i in range(N):
        if pro[i] == 1:
            lena += L[i]
            cost += 10
        elif pro[i] == 2:
            lenb += L[i]
            cost += 10
        elif pro[i] == 3:
            lenc += L[i]
            cost += 10
    if lena == 0 or lenb == 0 or lenc == 0:
        continue
    cost += abs(A-lena) + abs(B-lenb) + abs(C-lenc)
    ans = min(ans,cost)
print(ans)

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()))

dp_a = [-1] * (2 ** n)
dp_b = [-1] * (2 ** n)
dp_c = [-1] * (2 ** n)

for i in range(1, n-1):
    for j in combinations(range(n), i):
        indices = [1 << k for k in j]
        index = sum(indices)
        if i == 1:
            dp_a[index] = abs(l[j[0]] - a)
            dp_b[index] = abs(l[j[0]] - b)
            dp_c[index] = abs(l[j[0]] - c)
        else:
            dp_a[index] = min([dp_a[index - indices[k]] for k in range(i)])
            dp_a[index] = min(dp_a[index], abs(sum([l[k] for k in j]) - a) + 10 * (i-1))

            dp_b[index] = min([dp_b[index - indices[k]] for k in range(i)])
            dp_b[index] = min(dp_b[index], abs(sum([l[k] for k in j]) - b) + 10 * (i - 1))

            dp_c[index] = min([dp_c[index - indices[k]] for k in range(i)])
            dp_c[index] = min(dp_c[index], abs(sum([l[k] for k in j]) - c) + 10 * (i - 1))

ans = 10 ** 10
for i in range(1, 2 ** n):
    for j in range(1, 2 ** n):
        if i | j != i + j:
            continue
        for k in range(1, 2 ** n):
            if i + j + k == 2 ** n - 1 and i | j | k == 2 ** n - 1:
                ans = min(ans, dp_a[i] + dp_b[j] + dp_c[k])

print(ans)

Submission status: Accepted

Solution code:
N,A,B,C=map(int,input().split())
l=[int(input()) for i in range(N)]
D=0
a=0
b=0
c=0
mp=10**5
#4^8=2^16=10^16*0.3010=10^5?
for i in range(4**N):
  a=0
  b=0
  c=0
  x=0
  y=0
  z=0
  for j in range(N):
    if(i&1<<2*j and i&1<<(2*j+1)):
      #A-=[l[j]
      a+=l[j]
      x+=1
    elif(i&1<<2*j and ~(i&1<<(2*j+1))):
      b+=l[j]
      y+=1
    elif(~(i&1<<2*j) and (i&1<<(2*j+1))):
      c+=l[j]
      z+=1
  if(a==0 or b==0 or c==0):
    continue

  mp=min(mp,abs(A-a)+abs(B-b)+abs(C-c)+(x+y+z-3)*10)
  if(mp==110):
    print("a={}".format(a)+"b={}".format(b)+"c={}".format(c))
print(mp)

Submission status: Accepted

Solution code:
# solution

from itertools import product
nim, a, b, c = map(int, input().split())
array = []
for i in range(nim):
  array.append(int(input()))

abc = [0,a,b,c]
ch = [0,1,2,3]
cal = []

for i in product(ch,repeat=nim):
  calc = 0
  su = [0,0,0,0]
  ct = [0,0,0,0]
  temp = list(i)
  for j in range(nim):
    su[temp[j]] += array[j]
    ct[temp[j]] += 1
  if (ct[1]==0)|(ct[2]==0)|(ct[3]==0):
    continue
  for k in range(1,4):
    calc += abs(abc[k]-su[k])
    calc += max((ct[k]-1),0)*10
  cal.append(calc)
    
print(min(cal))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nは最大8まで、Aに使う竹はどれ？
N, A, B, C = lr()
bamboo = [ir() for _ in range(N)]
answer = 10 ** 5
for pattern in itertools.product(range(4), repeat=N):
    use = [0] * 3
    mp = 0
    for p, bam in zip(pattern, bamboo):
        if p == 3:
            continue
        if use[p] != 0:
            mp += 10
        use[p] += bam
    if use.count(0) != 0:
        continue
    mp += abs(A-use[0]) + abs(B-use[1]) + abs(C-use[2])
    if mp < answer:
        answer = mp

print(answer)
# 23

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# N本の竹それぞれA, B, C, 使わないか
N, A, B, C = lr()
bamboo = [ir() for _ in range(N)]
answer = 10 **  5
for pattern in itertools.product(range(4), repeat=N):
    mp = 0
    Alist = []; Blist = []; Clist = []
    for i, p in enumerate(pattern):
        if p == 0:
            Alist.append(bamboo[i])
        elif p == 1:
            Blist.append(bamboo[i])
        elif p == 2:
            Clist.append(bamboo[i])
    if len(Alist) == 0 or len(Blist) == 0 or len(Clist) == 0:
        continue
    mp += 10 * (len(Alist) + len(Blist) + len(Clist) - 3)
    mp += abs(A - sum(Alist)) + abs(B - sum(Blist)) + abs(C - sum(Clist))
    if mp < answer:
        answer = mp

print(answer)
# 04

Submission status: Accepted

Solution code:
N,*ABC=map(int,input().split())
M=3
ans=10**9
L=[]
for i in range(N):
  l=int(input())
  if l in ABC:
    ABC.remove(l)
    N-=1
    M-=1
  else:
    L.append(l)
if M==0:
  print(0)
  exit(0)
for x in range((M+1)**N):
  _=0
  abc=[0]*(M+1)
  for i in range(N):
    if x%(M+1)!=M and abc[x%(M+1)]>0:
      abc[x%(M+1)]+=L[i]
      _+=10
    else:
      abc[x%(M+1)]+=L[i]
    x=x//(M+1)
  if min(abc[:M])==0:
    continue
  for i in range(M):
    _+=abs(ABC[i]-abc[i])
  ans=min(ans,_)
  
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

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

min_mp = 10**10

for i in range(4**n):
    mp = 0
    li = [0]*4
    count_li = [0]*4
    s = Base_10_to_n(i,4).zfill(n)

    for j,k in enumerate(s):
        li[int(k)] += l[j]
        count_li[int(k)] += 1

    if 0 in li[:-1]:
        continue

    mp += abs(a-li[0])
    mp += abs(b-li[1])
    mp += abs(c-li[2])

    for item in count_li[:3]:
        if item >= 2:
            mp += 10*(item-1)
            
    min_mp = min(min_mp,mp)

print(min_mp)

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:
        if min(a,b,c) > 0:
            return abs(a-A) + abs(b-B) + abs(c-C) -10*3 
        else:
            return 10**9
    c0 = dfs(cur+1,a,b,c)
    c1 = dfs(cur+1,a+l[cur],b,c) +10
    c2 = dfs(cur+1,a,b+l[cur],c) +10
    c3 = dfs(cur+1,a,b,c+l[cur]) +10
    return min(c0,c1,c2,c3)

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

Submission status: Accepted

Solution code:
n, *abc = [int(x) for x in input().split()]
l = [int(input()) for i in range(n)]
A = 0; B = 1; C = 2;

minmp = 10 ** 9
for k in range(2 ** (2 * n)):
    mat = [[], [], [], []]  # mat[0]:= Aの材料, mat[1]:=Bの材料, mat[2]:=Cの材料
    # for i = 0, ..., N-1
    # kの 2*i & 2*i+1ビット目が 0b00: l[i]はAに使う
    #     ↑lsbから             0b01: l[i]はBに使う
    #                         0b10: l[i]はCに使う
    #                         0b11: l[i]は使わない
    for i in range(n):
        mat[k & (0b11)].append(l[i])
        k >>= 2

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

    mp = 0
    for j in range(3):
        mp += 10 * (len(mat[j]) - 1)
        mp += 1 * abs(abc[j] - sum(mat[j]))

    minmp = min(minmp, mp)

print(minmp)

Submission status: Accepted

Solution code:
n, *abc = [int(x) for x in input().split()]
l = [int(input()) for i in range(n)]
A = 0; B = 1; C = 2;

minmp = 10 ** 9
for k in range(2 ** (2 * n)):
    mat = [[], [], [], []]  # mat[0]:= Aの材料, mat[1]:=Bの材料, mat[2]:=Cの材料
    # for i = 0, ..., N-1
    # kの 2*i & 2*i+1ビット目が 0b00: l[i]はAに使う
    #     ↑lsbから             0b01: l[i]はBに使う
    #                         0b10: l[i]はCに使う
    #                         0b11: l[i]は使わない
    for i in range(n):
        mat[(k >> 2 * i) & (0b11)].append(l[i])

    if len(mat[0]) == 0 or len(mat[1]) == 0 or len(mat[2]) == 0:
        continue
        
    mp = 0
    for j in range(3):
        mp += 10 * (len(mat[j]) - 1)
        mp += 1 * abs(abc[j] - sum(mat[j]))

    minmp = min(minmp, mp)

print(minmp)

Submission status: Accepted

Solution code:
n,a,b,c = map(int, input().split())
a,b,c = sorted([a,b,c])
l = [int(input()) for i in range(n)]
ans = 10 ** 18
for i in range(4 ** n):
  LEN = [0,0,0,0]
  num = [0,0,0,0]
  for j,v in enumerate(l):
    index = (i >> (j * 2)) & 3
    LEN[index] += v
    num[index] += 1
  if num[0] and num[1] and num[2]:
    mp = (sum(num[:3])-3) * 10
    d = sorted(LEN[:3])
    mp += abs(d[0]-a) + abs(d[1]-b) + abs(d[2]-c)
    ans = min(ans, mp)
print(ans)

Submission status: Accepted

Solution code:
N, A, B, C = [int(i) for i in input().split()]
L = [int(input()) for _ in range(N)]
ans = float("inf")
for i in range(2 ** (N * 2)):
    a = b = c = 0
    cnt = 0
    for j in range(N):
        bit = i & 3
        if bit == 1:
            a += L[j]
        elif bit == 2:
            b += L[j]
        elif bit == 3:
            c += L[j]
        if bit:
            cnt += 1
        i >>= 2
    if a and b and c:
        ans = min(ans, (cnt - 3) * 10 + abs(A - a) + abs(B - b) + abs(C - c))
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(i, x, y, z):
    if i == n:
        cand = abs(a - x) + abs(b - y) + abs(c - z) - 30 if min(x, y, z) > 0 else INF
        return cand

    temp0 = dfs(i + 1, x + l[i], y, z) + 10
    temp1 = dfs(i + 1, x, y + l[i], z) + 10
    temp2 = dfs(i + 1, x, y, z + l[i]) + 10
    temp3 = dfs(i + 1, x, y, z)
    return min(temp0, temp1, temp2, temp3)

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

Submission status: Accepted

Solution code:
n,*a=map(int,input().split())
l=[int(input()) for i in range(n)]
ans=float("inf")
for i in range(4**n):
  table=[0 for g in range(3) ]
  temp=i
  pre=0

  for j in range(n):

    if temp%4==3:temp//=4;continue
    if table[temp%4]:
      table[temp%4]+=l[j]
      pre+=10
    else:table[temp%4]=l[j]
    temp//=4
  if 0 in table:continue
  for g in range(3):
    pre+=abs(a[g]-table[g])
  ans=min(ans,pre)
print(ans)

Submission status: Accepted

Solution code:
import sys
inf = float('inf')

n, A, B, C, *l = map(int, sys.stdin.read().split())

def cost(a, b, c, cnt, i):
    if i == n:
        if not (a and b and c): return inf
        return abs(A - a) + abs(B - b) + abs(C - c) + 10 * (cnt - 3)
    return min(cost(a, b, c, cnt, i+1), 
               cost(a+l[i], b, c, cnt+1, i+1),
               cost(a, b+l[i], c, cnt+1, i+1),
               cost(a, b, c+l[i], cnt+1, i+1))

def main():
    print(cost(0, 0, 0, 0, 0))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
inf = float('inf')

n, A, B, C, *l = map(int, sys.stdin.read().split())

@lru_cache(None)
def cost(a, b, c, cnt, i):
    if i == n:
        if not (a and b and c): return inf
        return abs(A - a) + abs(B - b) + abs(C - c) + 10 * (cnt - 3)
    return min(cost(a, b, c, cnt, i+1), 
               cost(a+l[i], b, c, cnt+1, i+1),
               cost(a, b+l[i], c, cnt+1, i+1),
               cost(a, b, c+l[i], cnt+1, i+1))

def main():
    print(cost(0, 0, 0, 0, 0))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import product

n, *abc = map(int, sys.stdin.readline().split())
*l, = map(int, sys.stdin.read().split())

def main():
    cand = []
    for p in product([0, 1, 2, 3], repeat=n):
        group = [[] for _ in range(4)]
        for i in range(n):
            group[p[i]].append(l[i])
        cost = 0
        for i in range(1, 4):
            if not group[i]: 
                break
            cost += 10 * (len(group[i]) - 1)
            group[i] = sum(group[i])
        else:
            group = group[1:]
            for i in range(3):
                cost += abs(abc[i] - group[i])
            cand.append(cost)
        
    print(min(cand))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,A,B,C = readInts()
    L = [] * n
    for i in range(n):
        l = int(input())
        L.append(l)

    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)
            # 一番最後まで行ったら、その差が延長魔法や短縮魔法を使うMPであるからこうする

        # 今ある竹を採用しない場合
        res = rec(i+1, a, b, c)

        # A,B,Cを使う場合 (どこにどれを足す？)
        # 1本目はコストなし、2本目からコスト10
        res = min(res,rec(i+1,a+L[i],b,c) + (10 if a >= 1 else 0)) # aにL[i]を足す
        res = min(res,rec(i+1,a,b+L[i],c) + (10 if b >= 1 else 0)) # bにL[i]を足す
        res = min(res,rec(i+1,a,b,c+L[i]) + (10 if c >= 1 else 0)) # cにL[i]を足す
        return res

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


if __name__ == '__main__':
  main()

Submission status: Accepted

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


def dfs(depth, a, b, c):
    if depth == N:
        # A, B, C いずれも竹は1本以上必ず使っていないとだめ
        if min(a, b, c) > 0:
            # 合体が終わったあとで差を計算してそれがコストになる
            return abs(a-A) + abs(b-B) + abs(c-C) - 30
        else:
            return INF

    # 今ある竹を採用しない場合
    ret0 = dfs(depth + 1, a, b, c)

    # A, B, C を使う場合
    # 先にまとめて合体してあとで -30 することによって調整
    ret1 = dfs(depth + 1, a + l[depth], b, c) + 10
    ret2 = dfs(depth + 1, a, b + l[depth], c) + 10
    ret3 = dfs(depth + 1, a, b, c + l[depth]) + 10
    return min(ret0, ret1, ret2, ret3)


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

Submission status: Accepted

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

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



def dfs(count,a,b,c):
    if count==n:
        if min(a,b,c)>0:
            return abs(a-A)+abs(b-B)+abs(c-C)-30
        else:
            return 10**9+1
    x = dfs(count+1, a, b, c)
    y = dfs(count+1, a+l[count], b, c)+10
    z = dfs(count+1, a, b+l[count], c)+10
    w = dfs(count+1, a, b, c+l[count])+10
    return min(x,y,z,w)



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

Submission status: Accepted

Solution code:
def f(i):
    global ans
    if i == n:
        w, x, y, z = 0, 0, 0, 0
        for i in range(n):
            if s[i] == 1:
                x += l[i]
            elif s[i] == 2:
                y += l[i]
            elif s[i] == 3:
                z += l[i]
            else:
                w += 1
        if x > 0 and y > 0 and z > 0:
            mp = abs(a - x) + abs(b - y) + abs(c - z) + 10 * (n - w - 3)
            ans = min(ans, mp)
        return
    s[i] = 0
    f(i + 1)
    s[i] = 1
    f(i + 1)
    s[i] = 2
    f(i + 1)
    s[i] = 3
    f(i + 1)

n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]
s = [3] * n
ans = 114514
f(0)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

def dfs():
    stack = [(0,0,0,0,0)]
    ans = float("inf")

    while stack:
        current, c_a, c_b, c_c, score = stack.pop()

        if current == N:
            if c_a > 0 and c_b > 0 and c_c > 0:
                ans = min(ans, abs(A - c_a) + abs(B - c_b) + abs(C - c_c) + score - 30)
            continue

        stack.append((current+1, c_a, c_b, c_c, score))
        stack.append((current+1, c_a+l[current], c_b, c_c, score+10))
        stack.append((current+1, c_a, c_b+l[current], c_c, score+10))
        stack.append((current+1, c_a, c_b, c_c+l[current], score+10))

    return ans
print(dfs())

Submission status: Accepted

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

m = 10 ** 6
for choice in range(1, 4 ** (N + 1)):
    bucket = [[] for _ in range(4)]
    #print(choice)
    for j in range(N):
        temp = (choice // 4 ** j) % 4
        bucket[temp].append(l[j])
        #print(temp)
    #print(bucket)
    if bucket[0] and bucket[1] and bucket[2]:
        pass
    else:
        continue
    cost = 0
    for i in range(4):
        if i <= 2 and bucket[i]:
            if len(bucket[i]) >= 2:
                total = sum(bucket[i])
                cost += 10 * (len(bucket[i]) - 1)
            else:
                total = bucket[i][0]
            cost += abs(total - ABC[i])
    m = min(m, cost)
print(m)