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:
a, b, c, l_list = 0, 0, 0, []


def dfs(l_key, a_sum, b_sum, c_sum):
    if l_key == len(l_list):
        if min(a_sum, b_sum, c_sum) > 0:
            return abs(a - a_sum) + abs(b - b_sum) + abs(c - c_sum) - 30
        else:
            return 1 << 20

    l_value = l_list[l_key]
    ret0 = dfs(l_key + 1, a_sum, b_sum, c_sum)
    ret1 = dfs(l_key + 1, a_sum + l_value, b_sum, c_sum) + 10
    ret2 = dfs(l_key + 1, a_sum, b_sum + l_value, c_sum) + 10
    ret3 = dfs(l_key + 1, a_sum, b_sum, c_sum + l_value) + 10

    return min(ret0, ret1, ret2, ret3)


def main():
    global a, b, c, l_list

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

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


main()

Submission status: Accepted

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

#竹の合成を全パターン、例えば1番の竹をA,B,C,使わないのどれかに定める。
#なので全パターンは4^8=65536で計算できる。

def dfs(cur,a,b,c):
#cursorを使い、注目してる竹をどこに追加するか選択。
#このやり方だと竹を一本も選ばない可能性があるのでその場合はINFを入れる。
    if cur==N:
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else INF
#合成が完了したら伸ばすor縮むは絶対値の差を取ることで計算可能
    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:
def compute():
    from sys import stdin
    N, A, B, C = list(map(int, stdin.readline().split()))
    l = list(int(stdin.readline().split()[0]) for _ in range(N))

    dp = {}
    abclist = [A, B, C]
    def f(bamboo, remain, abc):
        if remain == 0:
            if abc >= 2:
                return 0
            # print(bin(bamboo), remain, abc)
            return f(bamboo, abclist[abc+1], abc+1)

        args = (bamboo, remain, abc)
        if args in dp:
            return dp[args]
        dp[args] = 10000

        for x in range(N):
            if (bamboo & (1<<x)) == 0:
                nexbam = (bamboo | (1<<x))
                mp = abs(remain-l[x])
                dp[args] = min(dp[args], mp + f(nexbam, 0, abc))
                dp[args] = min(dp[args], 10 + f(nexbam, remain-l[x], abc))

        return dp[args]

    print(f(0, abclist[0], 0))


if __name__ == "__main__":
    compute()

Submission status: Accepted

Solution code:
from itertools import product


def main():
    tmp = [0] * 4
    N, A, B, C = map(int, input().split())
    L = [int(input()) for _ in range(N)]
    ans = float("inf")
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j or j == k or k == i:
                    continue
                tmp = [0, A-L[i], B-L[j], C-L[k]]
                rem = [L[x] for x in range(N) if x not in (i, j, k)]
                for p in product([0, 1, 2, 3], repeat=len(rem)):
                    tmp2 = [x for x in tmp]
                    for pi in range(len(p)):
                        tmp2[p[pi]] -= rem[pi]
                    swaps = len(list(filter(lambda x: x != 0, p)))
                    ans = min(ans, sum(map(abs, tmp2[1:])) + 10 * swaps)
                ans = min(ans, sum(map(abs, tmp[1:])))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
z = list(map(int,input().split()))
n = z[0]
l = [int(input()) for _ in range(n)]

ans = float('inf')
loop = 0
while loop < 4**n:
    ps = [loop // (4**j) % 4 for j in range(n)]
    loop += 1
    s = [[], [], [], []]
    for cnt,p in enumerate(ps):
        s[p].append(l[cnt])
    if not all(s[1:]):
        continue
    score = [(len(s[i]) - 1) * 10 + abs(sum(s[i]) - z[i]) for i in range(4)]
    ans = min(ans, sum(score[1:]))

print(ans)

Submission status: Accepted

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

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

def dfs(cur,a,b,c):
    if cur == N:
        s = abs(A-a)+abs(B-b)+abs(C-c)-30 if min(a,b,c) > 0 else 10**9
        return s
    s_0 = dfs(cur+1,a,b,c)
    s_a = dfs(cur+1,a+bms[cur],b,c) + 10
    s_b = dfs(cur+1,a,b+bms[cur],c) + 10
    s_c = dfs(cur+1,a,b,c+bms[cur]) + 10
    return min(s_0,s_a,s_b,s_c)

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

Submission status: Accepted

Solution code:
#%%
import itertools

#%%

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



iterobj = itertools.product(range(4),repeat=N)

ans = 10**8

for use in iterobj:

    if 1 in use and 2 in use and 3 in use:

        synth = [0,0,0,0]

        for m, u in  zip(materials, use):
            synth[u] += m

        mp = 10 * (use.count(1) + use.count(2) + use.count(3) - 3)

        mp += abs(A-synth[1]) + abs(B-synth[2]) + abs(C-synth[3])

        ans = min(ans, mp)

print(ans)

Submission status: Accepted

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

def dfs(depth, a, b, c):
	if depth == N:
		if a == 0 or b == 0 or c == 0:
			return 1e9
		return abs(A - a) + abs(B - b) + abs(C - c)
	
	x = dfs(depth + 1, a, b, c)
	w = dfs(depth + 1, a, b, c + inputs[depth]) + 10 * (c != 0)
	y = dfs(depth + 1, a + inputs[depth], b, c) + 10 * (a != 0)
	z = dfs(depth + 1, a, b + inputs[depth], c) + 10 * (b != 0)
	
	return min(x, y, z, w)

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

Submission status: Accepted

Solution code:
import numpy as numpy

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

def dfs(n,a,b,c):
  if n == N:
    return INF if min(a, b, c) == 0 else abs(a - A) + abs(b - B) + abs(c - C) - 30
  res0 = dfs(n + 1, a, b, c)
  res1 = dfs(n + 1, l[n] + a, b, c) + 10
  res2 = dfs(n + 1, a, l[n] + b, c) + 10
  res3 = dfs(n + 1, a, b, l[n] + c) + 10
  return min(res0, res1, res2, res3)

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

Submission status: Accepted

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


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

    return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))

Submission status: Accepted

Solution code:
from itertools import product
N, A, B, C = map(int, input().split())
L = []
for i in range(N):
  L.append(int(input()))
  
hand = ['n', 'a', 'b', 'c']

ans = 1e12
for h in product(hand, repeat=N):
  if len(set(h) & set(['a', 'b', 'c'])) < 3:
    continue
  cost = 0
  work_k = {'a':0, 'b':0, 'c':0}
  #print(h)
  for i in range(N):
    #print(i, h[i], L[i], work_k['a'])
    if h[i] == 'n':
      continue
    if work_k[h[i]] > 0:
      cost += 10
    work_k[h[i]] = work_k[h[i]] + L[i]
    
  cost += abs(A - work_k['a'])
  cost += abs(B - work_k['b'])
  cost += abs(C - work_k['c'])
  
  ans = min(cost, ans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

# goals = [1000,800,100]
# ls = [300,333,400,444,500,555,600,666]
# goals = [100, 90, 80]
# ls = [98, 40,30,21,80]

def count(x,ls):
    try:
        x.index(0)
        x.index(1)
        x.index(2)        
    except:
        return False
    A = np.zeros(len(goals))
    for i,l in enumerate(ls):
        add_ind = x[i]
        if add_ind==3:
            pass
        else:
            A[add_ind] += l
    combine_MP = 0
    for i in range(3):
        combine_MP += 10*(x.count(i)-1)
    return A, combine_MP
    
    
score_min = 100000
for N in range(4**8):
    x = []
    for j in range(len(ls)):
        x.append(N % 4)
        N = N // 4 
    try:
        A, combine_MP = count(x,ls)
        score = np.abs(A-np.array(goals)).sum() + combine_MP
        if score_min >= score:
            score_min = score
    except:
        pass
print(int(score_min))

Submission status: Accepted

Solution code:
def dfs(i, A, B, C):
    global ans
    if i == n:
        if A and B and C:
            s = 0
            ABC = [A, B, C]
            for i in range(3):
                s += (len(ABC[i]) - 1) * 10 + abs(sum(ABC[i]) - abc[i])
            ans = min(ans, s)
    else:
        dfs(i + 1, A + [l[i]], B, C)
        dfs(i + 1, A, B + [l[i]], C)
        dfs(i + 1, A, B, C + [l[i]])
        dfs(i + 1, A, B, C)

n, a, b, c = map(int, input().split())
l = [int(input()) for i in range(n)]
abc = [a, b, c]
ans = float("inf")
dfs(0, [], [], [])
print(ans)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
l = []
for i in range(N):
    x = int(input())
    l.append(x)
ans = float("inf")
def dfs(depth, li):
    if depth == N:
        if len(li[0]) > 0 and len(li[1]) > 0 and len(li[2]) > 0:
            global ans
            x = abs(sum(li[0]) - A) + abs(sum(li[1]) - B) + abs(sum(li[2]) - C) + max(0, 10*(len(li[0])-1)) + max(0, 10*(len(li[1])-1)) + max(0, 10*(len(li[2])-1))
            if x < ans:
                ans = x

    else:
        dfs(depth + 1, [li[0]+[l[depth]]]+li[1:])
        dfs(depth + 1, li[:1]+[li[1]+[l[depth]]]+li[2:])
        dfs(depth + 1, li[:2]+[li[2]+[l[depth]]]+li[3:])
        dfs(depth + 1, li[:3]+[li[2]+[l[depth]]])


dfs(0, [[],[],[],[]])
print(ans)

Submission status: Accepted

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


def dfs(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 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:
from itertools import product
n, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(n)]
ans = 10**9
for v in product([0, 1, 2, 3], repeat=n):
    a, b, c = 0, 0, 0
    cost = 0
    for i in range(n):
        if v[i] == 0:
            if a > 0:
                cost += 10
            a += l[i]
        elif v[i] == 1:
            if b > 0:
                cost += 10
            b += l[i]
        elif v[i] == 2:
            if c > 0:
                cost += 10
            c += l[i]
    if min(a, b, c) > 0:
        cost += abs(a-A) + abs(b-B) + abs(c-C)
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
n, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(n)]
inf = float("inf")
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:
want = [0,0,0]
ans = []
N,want[0],want[1],want[2] = map(int,input().split())
L = []
for _ in range(N):
    L.append(int(input()))
table = [0,1,2,-1]
import itertools as it
c = list(it.product(table, repeat=N))
for x in c:
    ABC = [0,0,0,0]
    cnt = -3
    for i in range(len(x)):
        ABC[x[i]] += L[i]
        if x[i] != -1:
            cnt += 1
    t = ABC.pop(-1)
    if 0 in ABC:
        continue
    val = sum(map(lambda x:abs(x[0]-x[1]),list(zip(ABC,want))))
    val += 10*cnt
    ans.append(val)
print(min(ans))

Submission status: Accepted

Solution code:
want = [0,0,0]
ans = []
N,want[0],want[1],want[2] = map(int,input().split())
L = []
for _ in range(N):
    L.append(int(input()))

table = [0,1,2,-1]
import itertools as it
c = list(it.product(table, repeat=N))
for x in c:
    A = 0
    B = 0
    C = 0
    cnt = -3
    z = list(zip(x,L))
    for y in z:
        if y[0] == 0:
            A += y[1]
            cnt += 1
        elif y[0] == 1:
            B += y[1]
            cnt += 1
        elif y[0] == 2:
            cnt += 1
            C += y[1]
        else:
            pass
    if A*B*C == 0:
        continue
    ans.append(abs(A-want[0])+abs(B-want[1])+abs(C-want[2])+cnt*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)]
INF = 10 ** 9
def dfs(cnt, a, b, c):
    if cnt == N:
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else INF
    ret1=dfs(cnt+1,a+l[cnt],b,c)+10
    ret2=dfs(cnt+1,a,b+l[cnt],c)+10
    ret3=dfs(cnt+1,a,b,c+l[cnt])+10
    ret4=dfs(cnt+1,a,b,c)
    return min(ret1,ret2,ret3,ret4)

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

Submission status: Accepted

Solution code:
n, a, b, c = map(int, input().split())
index=0
listL = []
while index < n:
    l = int(input())
    listL.append(l)
    index+=1
stateL  = [0]*n

def calculater(listL, stateL, a, b, c):
    oneL = [0, 0, 0]  # oneCount, Length, MP
    twowL = [0, 0, 0]
    threeL = [0, 0, 0]
    index = 0
    while index < len(stateL):
        if stateL[index] == 1:
            oneL[0] += 1
            oneL[1] += listL[index]
        elif stateL[index] == 2:
            twowL[0] += 1
            twowL[1] += listL[index]
        elif stateL[index] == 3:
            threeL[0] += 1
            threeL[1] += listL[index]
        index += 1
    oneL[2] += 10*(oneL[0]-1)+abs(a-oneL[1])
    twowL[2] += 10*(twowL[0]-1)+abs(b-twowL[1])
    threeL[2] += 10*(threeL[0]-1)+abs(c-threeL[1])
    return oneL[2]+twowL[2]+threeL[2]

def loopMaker(n, stateL, minMP):
    if n >= len(listL):
        return minMP
    else:
        index=0
        while index < 4:
            stateL[n] = index
            if n == len(stateL)-1:
                if 1 in stateL and 2 in stateL and 3 in stateL:
                    mp = calculater(listL, stateL, a, b, c)
                else:
                    mp = 10000
                if mp < minMP:
                    minMP = mp
            minMP = loopMaker(n+1, stateL, minMP)
            index+=1
        return minMP

minMP = loopMaker(0, stateL, 10000)
print(minMP)

Submission status: Accepted

Solution code:

import numpy as np

N, A, B, C = map(int, input().split(' '))
ls = []
for _ in range(N):
    ls.append(int(input()))
n = 0
INF = 10 ** 9

def dfs(n, a, b, c):
    if n == N:
        return INF if min(a, b, c) == 0 else abs(a-A) + abs(b-B) + abs(c-C) - 30
    res0 = dfs(n+1, a, b, c)
    res1 = dfs(n+1, a+ls[n], b, c) + 10
    res2 = dfs(n+1, a, b+ls[n], c) + 10
    res3 = dfs(n+1, a, b, c+ls[n]) + 10
    return min(res0, res1, res2, res3)

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

Submission status: Accepted

Solution code:
import sys
N,A,B,C = [int(n) for n in input().split()]
# N = int(input())
l = [int(input()) for _ in range(N)]
# S = str(input())
# T = str(input())
INF = 10 **18
def dfs(p,a,b,c):
    if p == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a,b,c) > 0  else INF
    ans0 = dfs(p+1,a,b,c)
    ans1 = dfs(p+1,a+l[p],b,c) + 10
    ans2 = dfs(p+1,a,b+l[p],c) + 10
    ans3 = dfs(p+1,a,b,c+l[p]) + 10
    return min(ans0,ans1,ans2,ans3)

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

Submission status: Accepted

Solution code:
n, a, b, c = [int(x) for x in input().split()]
l = [int(input()) for i in range(n)]


label = ['a', 'b', 'c', 'd']
list_init = []
for i in label:
    for j in label:
        list_init.append([i, j])

def extend(list):
    if n == 2:
        return list
    list_new = []
    for i in list[:]:
        for j in label:
            i.append(j)
            list_new.append(i[:])
            i.pop()
    if len(list_new[0]) == n:
        return list_new
    else:
        return extend(list_new[:])

list_created = extend(list_init[:])
mp = []
INF = 10 ** 9
for i in list_created:
    s = set(i)
    try: s.remove('d')
    except KeyError: pass
    if len(s) < 3:
        mp.append(INF)
        continue

    la, lb, lc = 0, 0, 0
    na, nb, nc = 0, 0, 0
    for j in range(len(i)):
        if i[j] == 'a':
            la += l[j]
            na += 1
        elif i[j] == 'b':
            lb += l[j]
            nb += 1
        elif i[j] == 'c':
            lc += l[j]
            nc += 1
    mp.append(abs(la-a) + abs(lb-b) + abs(lc-c) + 10*(na + nb + nc - 3))

print(min(mp))

Submission status: Accepted

Solution code:
import numpy as np
n,A,B,C=list(map(int,input().split(" ")))
l_list = [0]*n
for i in range(n):
    l_list[i] = int(input())
    
flags = [0]*n

anss = []

def f(d):
    if d < n:
        for i in [0,1,2,3]:
            flags[d] = i
            f(d+1)
    else:
        if not (flags.count(1)>0 and flags.count(2)>0 and flags.count(3)>0):
            return
        tA = A
        tB = B
        tC = C
        for i in range(n):
            if flags[i] == 1:
                tA -= l_list[i]
            elif flags[i] == 2:
                tB -= l_list[i]
            elif flags[i] == 3:
                tC -= l_list[i]
        ans = 0
        ans += max(0,(flags.count(1)-1)*10)
        ans += max(0,(flags.count(2)-1)*10)
        ans += max(0,(flags.count(3)-1)*10)
        ans += abs(tA)+abs(tB)+abs(tC)
        anss.append(ans)
f(0)
print(min(anss))

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 calc(take, a, b, c):
    if take == N:
        return abs(a-A)+abs(b-B)+abs(c-C) -30 if min(a,b,c)>0 else INF
    ret0 = calc(take+1, a, b, c)
    ret1 = calc(take+1, a+l[take], b, c) + 10
    ret2 = calc(take+1, a, b+l[take], c) + 10
    ret3 = calc(take+1, a, b, c+l[take]) + 10
    return min(ret0, ret1, ret2, ret3)
    
print(calc(0,0,0,0))

Submission status: Accepted

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


def dfs(depth, a, b, c):
    if depth == N:
        # 最初は竹を結合していないためABC各々で１０ずつ合計３０のマイナス
        return abs(A - a) + abs(B - b) + abs(C - c) - 30 if min(a, b, c) > 0 else INF
    ret0 = dfs(depth + 1, a, b, c)  # depth本目の竹を使わない
    ret1 = dfs(depth + 1, a + bamboo[depth], b, c) + 10  # depth本目の竹をAに使う
    ret2 = dfs(depth + 1, a, b + bamboo[depth], c) + 10  # depth本目の竹をBに使う
    ret3 = dfs(depth + 1, a, b, c + bamboo[depth]) + 10  # depth本目の竹をCに使う
    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)]
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
  else:
    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 itertools

N,a,b,c = map(int,input().split())
L = list(int(input()) for i in range(N))

products = itertools.product(list(range(4)), repeat=N)

ans = float("inf")

for prod in products :
    A = []
    B = []
    C = []
    
    for i in range(len(prod)) :
        if prod[i] == 1 :
            A.append(L[i])
        elif prod[i] == 2 :
            B.append(L[i])
        elif prod[i] == 3 :
            C.append(L[i])
    if len(A) * len(B) * len(C) == 0 :
        continue
    
    cost = 0
    
    for li in [A,B,C] :
        cost += (len(li)-1)*10
    cost += abs(a-sum(A)) + abs(b-sum(B)) + abs(c-sum(C))
    ans = min(ans,cost)
print(ans)

Submission status: Accepted

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

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

ans = float("inf")
for p in products:
    scores = [[0, 0], [0, 0], [0, 0], [0, 0]]
    for i in range(len(p)):
        scores[p[i]][0] += L[i]
        scores[p[i]][1] += 1
    temp = [elem[0] for elem in scores[:3]]
    cost = sum([10 * (elem[1] - 1) for elem in scores[:3] if elem[1] >= 1])
    if 0 in temp:
        continue
    sorted(temp)
    cost += sum([abs(target[i] - temp[i]) for i in range(3)])
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:

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

INF = 10 ** 9


def dfs(cursor, a, b, c):  # cursor:カーソル a,b,c:現在の竹の長さ
    if cursor == N:  # cursorが最後まで行ったら終了する。
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    # abs(a - A) + abs(b - B) + abs(c - C) - 30 でなぜ30を減じているのかというと、
    # dfs(0,0,0)
    # dfs(0,0,0,0)で始まる以上、最初に選ばれるa,b,cを決定する際にもコストが10増加してしまうからである。
    # また、全探索を行う中で、a,b,cの初期値が0,0,0である以上、a,b,cのどれかが0のまま終了する場合が存在する。
    # この場合はa,b,cに竹が対応してないと言えるため、解にはならない、そこで三項演算子を利用して
    # その場合についてコストをINFとしている

    # 以下は4**Nで展開される再起処理となる。
    # カーソルの当たっている竹に対して、(A or B or Cに合成する) or (合成しない)の場合に分ける
    no_compound_pattern = dfs(cursor+1, a, b, c)
    compound_a_pattern = dfs(cursor+1, a + L[cursor], b, c)+10
    compound_b_pattern = dfs(cursor+1, a, b + L[cursor], c)+10
    compound_c_pattern = dfs(cursor+1, a, b, c + L[cursor])+10

    # 結果的に以下の値が返るのはそれぞれのパターンのコストが決定されてからなので
    # 以下のコードは最終的なコストの最小値
    return min(no_compound_pattern, compound_a_pattern, compound_b_pattern, compound_c_pattern)


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

Submission status: Accepted

Solution code:
L_MAX = 1000
N, A, B, C = map(int, input().split())
l = [None] * N
for i in range(N):
    l[i] = int(input())
D = [A, B, C]

mp_min = 3 * L_MAX
for bit in range(4 ** N):
    bamboos = [[], [], []]
    b = bit
    #print("b =", b)
    for i in range(N):
        if b % 4 < 3:
            bamboos[b % 4].append(l[i])
            #print("append l[{}] = {} to bamboos[{}]".format(i, l[i], b % 3))
        b //= 4 
    if any(map(lambda x: x == [], bamboos)):
        continue

    #for i in range(3):
    #    print("bamboos[{}] = {}".format(i, bamboos[i]))

    mp = 0
    for i in range(3):
        mp += abs(D[i] - sum(bamboos[i])) + 10 * (len(bamboos[i]) - 1)
    #print("mp =", mp)
    mp_min = min(mp_min, mp)
print(mp_min)

Submission status: Accepted

Solution code:
from itertools import product
n,*X=map(int,input().split())
L=[int(input()) for _ in range(n)]
P=product(range(4),repeat=n)
ans=float("inf")
for i in P:
    cnt=[0]*3
    length=[0]*3
    for k in range(n):
        if i[k]==3:
            continue
        cnt[i[k]]+=1
        length[i[k]]+=L[k]
    if min(cnt)>0:
        tmp=sum([abs(length[i]-X[i])+10*(cnt[i]-1) for i in range(3)])
        ans=min(ans,tmp)
print(ans)

Submission status: Accepted

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


def f(a, b, c, i):
    if i == N:
        if min(a, b, c) == 0:
            return float('inf')
        return abs(A - a) + abs(B - b) + abs(C - c) - 30
    al = f(a + L[i], b, c, i + 1) + 10
    bl = f(a, b + L[i], c, i + 1) + 10
    cl = f(a, b, c + L[i], i + 1) + 10
    dl = f(a, b, c, i + 1)
    return min(al, bl, cl, dl)


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


main()

Submission status: Accepted

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

def dfs(i, a, b, c):
    if i == N:
        if min(a, b, c) > 0:
            return abs(A - a) + abs(B - b) + abs(C - c) - 30
        else:
            return INF
    res0 = dfs(i + 1, a, b, c)
    res1 = dfs(i + 1, a + L[i], b, c) + 10
    res2 = dfs(i + 1, a, b + L[i], c) + 10
    res3 = dfs(i + 1, a, b, c + L[i]) + 10
    return min(res0, res1, res2, res3)

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

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
    if cur == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if 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)]
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))
#example answer

Submission status: Accepted

Solution code:
N, A, B, C = map(int, raw_input().split())
l = [input() for _ in range(N)]
 
def cost(X, x):
  t = 0
  c = 0
  for i in range(N):
    if x>>i&1:
      t += l[i]
      c += 1
  return (c-1)*10 + abs(X-t)
 
ans = 10000
for a in range(1, 1<<N):
  ac = cost(A, a)
  for b in range(1, 1<<N):
    if (a&b)==0:
      bc = cost(B, b)
      for c in range(1, 1<<N):
        if ((a|b)&c)==0:
          cc = cost(C, c)
          ans = min(ans, ac+bc+cc)
print ans

Submission status: Accepted

Solution code:
minmp = 10000000
def main():
    def dfs(depth, pt):

        #深さmaxまでいったらMPを計算する
        if depth==n:
            mp_tmp = 0
            all_used = True
            for k in range(3):
                if pt.count(k) == 0:
                    all_used = False
                    break

                sum_tmp = 0
                mp_tmp += (pt.count(k) - 1)*10
                for l in range(n):
                    if pt[l] == k:
                        sum_tmp += moto[l]
                
                mp_tmp += abs(sum_tmp-take[k])

            if all_used == True:
                global minmp
                minmp = min(minmp,mp_tmp)
            
            return

        #次のパターンを試す
        for i in range(4):
            pt[depth] = i
            dfs(depth+1, pt)

        return

    #入力をとる
    take = [0]*3
    n,take[0],take[1],take[2] = map(int,input().split())
    moto = [int(input()) for i in range(n)]

    pt  = [3]*n
    for i in range(n):
        dfs(i,pt)

    print(minmp)

main()

Submission status: Accepted

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

def rec(idx,a,b,c):
    if idx == N:
        if a == 0 or b == 0 or c == 0:
            return float('inf')
        else:
            return abs(A-a) + abs(B-b) + abs(C-c)
    
    p1 = rec(idx+1,a,b,c)
    p2 = rec(idx+1,a+l[idx],b,c)
    if a != 0: p2 += 10 
    p3 = rec(idx+1,a,b+l[idx],c)
    if b != 0: p3 += 10
    p4 = rec(idx+1,a,b,c+l[idx])
    if c != 0: p4 += 10

    return min([p1,p2,p3,p4])

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

Submission status: Accepted

Solution code:
minmp = 10000000
def dfs(depth, pt):

    if depth==n:
        mp_tmp = 0
        all_used = True
        for k in range(3):
            if pt.count(k) == 0:
                all_used = False
                break

            sum_tmp = 0
            mp_tmp += (pt.count(k) - 1)*10
            for l in range(n):
                if pt[l] == k:
                    sum_tmp += moto[l]
            
            mp_tmp += abs(sum_tmp-take[k])

        if all_used == True:
            global minmp
            minmp = min(minmp,mp_tmp)
            return
        else:
            return

    for i in range(4):
        pt[depth] = i
        dfs(depth+1, pt)

    return

#入力をとる
n,a,b,c = map(int,input().split())
moto = [int(input()) for i in range(n)]


take = []
take.append(a)
take.append(b)
take.append(c)

pt  = [3]*n
for i in range(n):
    dfs(i,pt)

print(minmp)

Submission status: Accepted

Solution code:
import itertools
N, *A = map(int,input().split())
l = [int(input()) for i in range(N)]
li =  itertools.product(range(4), repeat=N)

ans = float("inf")
for i in li:
  cnt = [0]*3
  length = [0]*3
  for k in range(N):
    if i[k] == 3: 
      continue
    cnt[i[k]] += 1
    length[i[k]] += l[k]
  if min(cnt) > 0:
    cost = sum([abs(length[i]-A[i]) +10*cnt[i] for i in range(3)]) -30
    ans = min(ans, cost)
  
print(ans)

Submission status: Accepted

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


def dfs(cur, a, b, c):
    if cur == n:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    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)]
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))