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:
from collections import deque
import copy
n, a, b, c = map(int,input().split())
bamboos = []
for _ in range(n):
    bamboos.append(int(input()))

groups =deque()
groups.append([[bamboos[0]],[],[],[]])

for i in range(1,n):
    groups2 = deque()
    while len(groups)>0:
        group = groups.popleft()
        for j in range(4):
            group2 = copy.deepcopy(group)
            group2[j].append(bamboos[i])
            groups2.append(group2) 
    groups = groups2
def unite(g1,g2,g3,g4):
    kouho = []
    l1 = len(g1)
    l2 = len(g2)
    l3 = len(g3)
    l4 = len(g4)
    
    if len(g2)>0 and len(g3)>0 and len(g4)>0:
        unite_score = (l2 +l3 +l4-3)*10
        kouho.append([sum(g2),sum(g3),sum(g4),unite_score])
    if len(g1)>0 and len(g3)>0 and len(g4)>0:
        unite_score = (l1 +l3 +l4-3)*10
        kouho.append([sum(g1),sum(g3),sum(g4),unite_score])
    if len(g2)>0 and len(g1)>0 and len(g4)>0:
        unite_score = (l2 +l1 +l4-3)*10
        kouho.append([sum(g2),sum(g1),sum(g4),unite_score])
    if len(g2)>0 and len(g3)>0 and len(g1)>0:
        unite_score = (l2 +l3 +l1-3)*10
        kouho.append([sum(g2),sum(g3),sum(g1),unite_score])
    return kouho
        

def solve(a,b,c,groups):
    ans = float("inf")
    for comb_4 in groups:
        kouhos = unite(comb_4[0],comb_4[1],comb_4[2],comb_4[3])
        for kouho in kouhos:
            score = kouho.pop()
            bam = kouho
            bam.sort()
            x = bam[2]
            y = bam[1]
            z = bam[0]
            score += abs(a-x) +abs(b-y)+abs(c-z)
            ans = min(ans,score)
    print(ans)
solve(a,b,c,groups)

Submission status: Accepted

Solution code:
A = [0,0,0]
N,A[0],A[1],A[2] = map(int,input().split())
L = [int(input()) for _ in range(N)]
#print(L)

ans = 10 ** 9
for i in range(4**N):
  G = [[] for _ in range(4)]
  for j in range(N):
    G[(i//(4**j))%4].append(L[j])
  #print(G)
  mp = 0
  for j in range(3):
    if len(G[j]) == 0:
      mp = 10 ** 9
      break
    mp += (len(G[j])-1)*10
    mp += abs(sum(G[j])-A[j])
  ans = min(ans,mp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

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

def dfs(idx,a,b,c):
    if idx == N:
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c) > 0 else float('inf')
    first = 10+dfs(idx+1,a+LS[idx],b,c)
    second = 10+dfs(idx+1,a,b+LS[idx],c)
    third = 10+dfs(idx+1,a,b,c+LS[idx])
    fourth = dfs(idx+1,a,b,c)
    return min(first,second,third,fourth)

def main():
    """ main """
    print(dfs(0,0,0,0))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def dfs(a, b, c, n):
    res = float("inf")
    if n == N:
        if a > 0 and b > 0 and c > 0:
            return abs(A - a) + abs(B - b) + abs(C - c) - 30
        else:
            return float("inf")
    l = l_list[n]
    res = min(res, dfs(a, b, c, n + 1))
    res = min(res, dfs(a + l, b, c, n + 1) + 10)
    res = min(res, dfs(a, b + l, c, n + 1) + 10)
    res = min(res, dfs(a, b, c + l, n + 1) + 10)
    return res


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

Submission status: Accepted

Solution code:
def main():
    N, *ABCnum = (int(i) for i in input().split())
    l = [int(input()) for _ in range(N)]
    ans = 10 ** 6
    from itertools import product
    for pattar in product(range(4),repeat=N):
        ABC = [[] for i in range(3)]
        for i,g in enumerate(pattar):
            if g == 0:
                ABC[0].append(l[i])
            elif g == 1:
                ABC[1].append(l[i])
            elif g == 2:
                ABC[2].append(l[i])
        cur = 0
        if not ABC[0] or not ABC[1] or not ABC[2]:
            continue
        for i in range(3):
            cur += abs(ABCnum[i] - sum(ABC[i])) + 10*(len(ABC[i]) - 1)
        ans = min(ans,cur)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,A,B,C = map(int,input().split())
L = [int(input()) for _ in range(N)]
INF = 10**9
def dfs(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:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

def dfs(cur, a, b, c):
    if cur == N:
        # 竹を使ってないと駄目
        if min(a, b, c) == 0:
            return INF
        else:
            return abs(a-A) + abs(b-B) + abs(c-C)

    ret0 = dfs(cur+1, a, b, c)
    # 最初の一本目はカウント除外、２本めからMP10
    ret1 = dfs(cur+1, a + L[cur], b, c) + (10 if a > 0 else 0)
    ret2 = dfs(cur+1, a, b + L[cur], c) + (10 if b > 0 else 0)
    ret3 = dfs(cur+1, a, b, c + L[cur]) + (10 if c > 0 else 0)

    return min(ret0, ret1, ret2, ret3)

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

Submission status: Accepted

Solution code:
import sys
import queue

#+++++

def aaa(ll,a,b,c):
	ret=a+b+c
	for i,v1 in enumerate(ll):
		t1=abs(a-v1)
		if ret < t1:
			continue
		for j,v2 in enumerate(ll):
			if i==j:
				continue
			t2=t1 + abs(b-v2)
			if ret < t2:
				continue
			for k,v3 in enumerate(ll):
				if i==k or j==k:
					continue
				t3 = t2 + abs(c-v3)
				ret=min(ret, t3)
	return ret		

def mk_str(ll):
	ll.sort()
	return '_'.join([str(v) for v in ll])


def main():
	n , a, b, c = map(int, input().split())
	est=lambda ll:aaa(ll,a,b,c)
	
	bb=[]
	for i in range(n):
		bb.append(int(input()))
	
	cl=set()
	ol=queue.PriorityQueue()
	
	st=bb
	ee=est(st)
	cc=0
	cl.add(mk_str(bb))
	ol.put((ee+cc, (cc, bb)))	
	while True:
		if ee == 0:
			return cc
		
		#to goal no join
		rr=cc+ee
		ol.put((rr, (rr, [a,b,c])))
		
		#join 1
		if len(st) > 3:
			cc+=10
			for i, v in enumerate(st):
				kk=st[:]
				m=kk.pop(i)
				for j, _ in enumerate(kk):
					kkk=kk[:]
					kkk[j]+=m
					stk=mk_str(kkk)
					if stk not in cl:
						cl.add(stk)
						ol.put((cc, (cc, kkk)))
		v,(cc, st) = ol.get()
		ee = est(st)
				
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
import queue

#+++++


def aaa(ll,a,b,c):
	ret=a+b+c
	for i,v1 in enumerate(ll):
		if v1==0:
			continue
		t1=abs(a-v1)
		if ret < t1:
			continue
		for j,v2 in enumerate(ll):
			if v2==0:
				continue
			if i==j:
				continue
			t2=t1 + abs(b-v2)
			if ret < t2:
				continue
			for k,v3 in enumerate(ll):
				if v3==0:
					continue
				if i==k or j==k:
					continue
				t3 = t2 + abs(c-v3)
				ret=min(ret, t3)
	return ret		

def mk_str(ll):
	ll.sort()
	return '_'.join([str(v) for v in ll])


def main():
	n , a, b, c = map(int, input().split())
	est=lambda ll:aaa(ll,a,b,c)
	
	bb=[]
	for i in range(n):
		bb.append(int(input()))
	
	cl=set()
	ol=queue.PriorityQueue()
	

	
	st=bb
	ee=est(st)
	cc=0
	cl.add(mk_str(bb))
	ol.put((ee+cc, (cc, bb)))	
	while True:
		if ee == 0:
			return cc
		
		#to goal no join
		rr=cc+ee
		ol.put((rr, (rr, [a,b,c])))
		
		
		
		#join 1
		if len(st) > 3:
			cc+=10
			for i, v in enumerate(st):
				kk=st[:]
				m=kk.pop(i)
				for j, _ in enumerate(kk):
					kkk=kk[:]
					kkk[j]+=m
					stk=mk_str(kkk)
					if stk not in cl:
						cl.add(stk)
						ol.put((cc, (cc, kkk)))
		v,(cc, st) = ol.get()
		ee = est(st)
				
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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:
    if min(a, b, c) > 0:
      return abs(a-A) + abs(b-B) + abs(c-C) - 30
    else:
      return INF
  ret0 = dfs(cur+1, a, b, c) # 初動
  ret1 = dfs(cur+1, a+l[cur], b, c) + 10 # 合成時コスト10MP
  ret2 = dfs(cur+1, a, b+l[cur], c) + 10 # 合成時コスト10MP
  ret3 = dfs(cur+1, a, b, c+l[cur]) + 10 # 合成時コスト10MP
  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)]

m = []
def dfs(depth, x, y, z, count):
  if depth == n:
    if min(x, y, z) > 0:
       return abs(a-x)+abs(b-y)+abs(c-z)+10*count-30
    else:
      return float('Inf')
  ret0 = dfs(depth+1, x, y, z, count)
  ret1 = dfs(depth+1, x+l[depth], y, z, count+1)
  ret2 = dfs(depth+1, x, y+l[depth], z, count+1)
  ret3 = dfs(depth+1, x, y, z+l[depth], count+1)
  return min(ret0, ret1, ret2, ret3)

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

Submission status: Accepted

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

m = []
def dfs(depth, x, y, z, count):
  if depth == n:
    if min(x, y, z) > 0:
       return abs(a-x)+abs(b-y)+abs(c-z)+10*count-30
    else:
      return float('Inf')
  ret0 = dfs(depth+1, x, y, z, count)
  ret1 = dfs(depth+1, x+l[depth], y, z, count+1)
  ret2 = dfs(depth+1, x, y+l[depth], z, count+1)
  ret3 = dfs(depth+1, x, y, z+l[depth], count+1)
  return min(ret0, ret1, ret2, ret3)

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

Submission status: Accepted

Solution code:
N,A,B,C,*L=map(int,open(0).read().split())
ans=float("inf")
for i in range(2**(N*2)):
	a=b=c=0
	mp=0
	for j,x in enumerate(L):
		f=(i>>2*j)&3
		if f==0:
			if a:mp+=10
			a+=x
		elif f==1:
			if b:mp+=10
			b+=x
		elif f==2:
			if c:mp+=10
			c+=x
	if any([a==0,b==0,c==0]):
		continue
	mp+=abs(A-a)+abs(B-b)+abs(C-c)
	if ans>mp:
		ans=mp
	if ans==0:
		break
print(ans)

Submission status: Accepted

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

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 getlist():
	return list(map(int, input().split()))

N, A, B, C = getlist()
L = []
for i in range(N):
	L.append(int(input()))

ans = float("inf")
for i in range(1 << 2 * len(L)):
    a = []
    b = []
    c = []
    for j in range(len(L)):
    	if ((i >> 2 * j) & 1) == 1:
    		if ((i >> 2 * j + 1) & 1) == 1:
    			a.append(L[j])
    		else:
    			b.append(L[j])
    	else:
    		if ((i >> 2 * j + 1) & 1) == 1:
    			c.append(L[j])
    	v = 0
    	if len(a) != 0 and len(b) != 0 and len(c) != 0:
    		v += 10 * (len(a) - 1)
    		v += 10 * (len(b) - 1)
    		v += 10 * (len(c) - 1)
    		v += abs(sum(a) - A) + abs(sum(b) - B) + abs(sum(c) - C)
    		ans = min(ans, v)

print(ans)

Submission status: Accepted

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

def dfs(depth, l):
    global ans, now
    if depth == n:
        tmp = 0
        for i in range(3):
            if now[i][1] == 0:
                return
            tmp += abs(abc[i] - now[i][0]) + 10 * (now[i][1] - 1)
        ans = min(ans, tmp)
        return
    for i in range(4):
        now[i][0] += l[depth]
        now[i][1] += 1
        dfs(depth + 1, l)
        now[i][0] -= l[depth]
        now[i][1] -= 1

dfs(0, l)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N, A, B, C = list(map(int, input().split()))
l_list = []

for _ in range(N):
    l = int(input().split()[0])
    l_list.append(l)


def cost(no, a_len, b_len, c_len):
    if no == N:
        # 最後のノードでは
        # 差分を延長魔法 or 短縮魔法で補う
        if min(a_len, b_len, c_len) <= 0:
            # 竹の長さを0以下にすることはできないので
            # このパターンはありえない
            return float("inf")

        a_cost = abs(a_len - A)
        b_cost = abs(b_len - B)
        c_cost = abs(c_len - C)
        # 最初にA,B,Cを選ぶときは余分に+10されているので、減らす
        return sum([a_cost, b_cost, c_cost]) - 30

    l = l_list[no]
    a_cost = 10 + cost(no + 1, a_len + l, b_len, c_len)
    b_cost = 10 + cost(no + 1, a_len, b_len + l, c_len)
    c_cost = 10 + cost(no + 1, a_len, b_len, c_len + l)
    d_cost = cost(no + 1, a_len, b_len, c_len)

    # このノードより上（以前）のルートは同じなので、
    # この時点で最小のものを1つだけ返せば良い
    return min([a_cost, b_cost, c_cost, d_cost])


ans = cost(0, 0, 0, 0)
print(ans)

Submission status: Accepted

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

def ten2four(x, n):
  output=str()
  for i in range(n-1, 0, -1):
    output+=str(x//(4**i))
    x=x%(4**i)
    
  output+=str(x)
  return output

p=4**N
minmp=abs(A-l[0])+abs(B-l[1])+abs(C-l[2])
for i in range(p):
  tempa=0
  tempb=0
  tempc=0
  tempmp=0
  
  pat=ten2four(i, N)
  
  x=sum([pat[j]=='1' for j in range(N)])
  y=sum([pat[j]=='2' for j in range(N)])
  z=sum([pat[j]=='3' for j in range(N)])
  
  if x>0 and y>0 and z>0:
    for j in range(N):
      if pat[j]=='1':
        tempa+=l[j]
      elif pat[j]=='2':
        tempb+=l[j]
      elif pat[j]=='3':
        tempc+=l[j]
      else:
        pass
      
    tempmp=10*(x+y+z-3)+abs(A-tempa)+abs(B-tempb)+abs(C-tempc)

    if minmp>tempmp:
      minmp=tempmp
            
print(minmp)

Submission status: Accepted

Solution code:
from itertools import product


def main():
    n, *target = map(int, input().split())
    arr = [int(input()) for i in range(n)]

    tests = product(range(4), repeat=n) #0:使わない　i:竹iの材料に使う
    test_arr = [[] for _ in range(3)]
    min_cost = float("inf")

    for test in tests: #パターンで全探索
        cost = 0

        if 1 not in test or 2 not in test or 3 not in test:
            continue

        for i in range(3):
            test_arr[i] = [arr[x] for x in range(n) if test[x] == i + 1]
            cost += (len(test_arr[i]) - 1) * 10  #test_arr[i]の竹を全部合成するのに要するMP
            cost += abs(sum(test_arr[i]) - target[i]) #延長・縮小により合成した竹の長さをtarget[i]に調整するにに要するMP

        if min_cost > cost:
            min_cost = cost

    print(min_cost)


main()

Submission status: Accepted

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

INF = 10 ** 9


def dfs(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:
n,A,B,C = map(int,input().split())
D = [A,B,C]
def nex(time):
  for i in range(n):
    if time[i] < 3:
      time[i] += 1
      break
    else:
      time[i] = 0
  else:
    time = 'over'
  return time
boo = []
for _ in range(n):
  boo.append(int(input()))
can = []
time = [0 for _ in range(n)]
while time != 'over':
  d = [0,0,0]
  tmp = (n-3) * 10
  for i in range(n):
    if time[i] < 3:
      d[time[i]] += boo[i]
    else:
      tmp -= 10
  for k in range(3):
    tmp += abs(D[k] - d[k])
  if d[0] * d[1] * d[2] != 0:
    can.append(tmp)
  time = nex(time)
print(min(can))

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:
#!/usr/bin/env python3
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:
import bisect
n,a,b,c=map(int,input().split())
l=[int(input()) for x in range(n)]
l.sort()
total=4**n
ans=999999999
for i in range(total):
    fora=[]
    forb=[]
    forc=[]
    nonused=[]
    temp_i = i
    for j in range(n):
        temp=temp_i%4
        if(temp==0):
            fora.append(l[j])
        elif(temp==1):
            forb.append(l[j])
        elif(temp==2):
            forc.append(l[j])
        else:
            nonused.append(l[j])
        temp_i = temp_i // 4
    if(len(fora)==0 or len(forb)==0 or len(forc)==0):
        continue
    else:
        mp=0
        mp+=10*(len(fora)-1)
        len_fora=sum(fora)
        mp+=abs(a-len_fora)

        mp+=10*(len(forb)-1)
        len_forb=sum(forb)
        mp+=abs(b-len_forb)

        mp+=10*(len(forc)-1)
        len_forc=sum(forc)
        mp+=abs(c-len_forc)

        if(ans > mp):
            ans = mp
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy
N, A, B, C = map(int,input().split())
t = sorted([A,B,C])
A = t[0]
B = t[1]
C = t[2]
l = []
for i in range(N):
    l.append(int(input()))
dic = {}

def calc(ls):
    dic[tuple(ls)] = 0
    Asublist = [np.abs(i-A) for i in ls]
    res = min(Asublist)
    idx = Asublist.index(res)
    ls.remove(ls[idx])

    Bsublist = [np.abs(i-B) for i in ls]
    tmp = min(Bsublist)
    res += tmp
    idx = Bsublist.index(tmp)
    ls.remove(ls[idx])

    Csublist = [np.abs(i-C) for i in ls]
    tmp = min(Csublist)
    res += tmp
    idx = Csublist.index(tmp)
    ls.remove(ls[idx])

    return res + 10*(N - (len(ls)+3))

def rec(ls, num, maxcomb, minval):
    if num > maxcomb:
        return minval
    for i in range(0, len(ls)-1):
        for j in range(i+1, len(ls)):
            tmp = [ls[i]+ls[j]]
            tmp = tmp + [ls[k] for k in range(len(ls)) if k!=i and k!=j]
            if tuple(tmp) in dic.keys():
                continue
            tmp2 = calc(copy.deepcopy(tmp))
            if minval > tmp2:
                minval = tmp2
            if num < maxcomb:
                tmp3 = rec(copy.deepcopy(tmp), num+1, maxcomb, minval)
                if minval > tmp3:
                    minval = tmp3
    return minval
minval = rec(l, 1, N-3, calc(copy.deepcopy(l)))
print(minval)

Submission status: Accepted

Solution code:
INF = 10 ** 5

A = [0] * 3
N,A[0],A[1],A[2] = map(int,input().split())

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

can = [0] * (4 ** N)

for x in range(4 ** N):
    union = [-1] * 4
    bef = [0] * 4 #4番めはどこにも入れない
    xx = x
    for i in range(N):
        where = xx % 4
        xx //= 4
        bef[where] += l[i]
        union[where] += 1
    #print(x,bef)
    if -1 in union[:3]:
        can[x] = INF
        continue
    deffer = 0
    for j in range(3):
        deffer += abs(bef[j]-A[j])
    can[x] = deffer + sum(union[:3]) * 10

print(min(can))

Submission status: Accepted

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

def dfs(depth,a,b,c):
    if depth == n:
        if min(a,b,c) > 0:
            return abs(a-A)+abs(b-B)+abs(c-C) - 30
        else:
            return 10**9
        
    numA = dfs(depth+1,a+l[depth],b,c) + 10
    numB = dfs(depth+1,a,b+l[depth],c) + 10
    numC = dfs(depth+1,a,b,c+l[depth]) + 10
    numX = dfs(depth+1,a,b,c)
    return min(numA,numB,numC,numX)
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
#18:51
n,A,B,C = map(int,input().split())
D = [A,B,C]
l = []
for _ in range(n):
  l.append(int(input()))
l.sort(reverse=True)
def nex(time):
  for i in range(n-1,-1,-1):
    if time[i] < 3:
      time[i] += 1
      break
    else:
      time[i] = 0
  else:
    time = 'over'
  return time
#print(nex([0,0,0,0]),nex([0,3,3,3]),nex([3,3,3,3]))
can = []
time = [0 for _ in range(n)]
while time != 'over':
  ans = (n-3) * 10
  d = [0,0,0]
  for i in range(n):
    t = time[i]
    if t == 3:
      ans -= 10
    else:
      d[t] += l[i]
  if all(d[k] != 0 for k in range(3)):
    for k in range(3):
      ans += abs(D[k] - d[k])
    can.append([ans,d])
  time = nex(time)
print(min(can,key=lambda x:x[0])[0])

Submission status: Accepted

Solution code:
import bisect

def solve():
  n,a,b,c = (int(i) for i in input().split())
  l = [int(input()) for _ in range(n)]
  ans = 10**15
  for bita in range(2**n):
    for bitb in range(2**n):
      if bita&bitb: continue
      for bitc in range(2**n):
        if bitc&bitb:continue
        if bitc&bita:continue
        if bita == 0 or bitb == 0 or bitc == 0: continue
        lenkado = [0]*3
        stime = [0]*3
        for k in range(n):
            if 1&(bita>>k): 
              lenkado[0] += l[k]
              stime[0] += 1
            elif 1&(bitb>>k): 
              lenkado[1] += l[k]
              stime[1] += 1
            elif 1&(bitc>>k): 
              lenkado[2] += l[k]
              stime[2] += 1
        tmp = abs(a-lenkado[0])+abs(b-lenkado[1]) + abs(c-lenkado[2])
        for i in range(3):
          tmp += max(0,stime[i]-1)*10
        ans = min(ans,tmp)
  print(ans)     
solve()

Submission status: Accepted

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


def dfs1(i, p1=[], p2=[], p3=[], ans=[]):
    #print(i)
    if i == N:
        if len(p1) != 0 and len(p2) != 0 and len(p3)!= 0:
            ans.append([p1, p2, p3])
        return ans
    l = L[i]
    ans = dfs1(i+1, p1+[l], p2, p3, ans)
    ans = dfs1(i+1, p1, p2+[l], p3, ans)
    ans = dfs1(i+1, p1, p2, p3+[l], ans)
    ans = dfs1(i+1, p1, p2, p3, ans)
    return ans

def dfs2(R, L=[], ans=[]):
    if len(L) == 3:
        ans.append(L)
        return ans
    for r in R:
        if not r in L:
            ans = dfs2(R, L+[r], ans)
    return ans

indexes = dfs2([0, 1, 2])

ans = int(1E18)
for (p1, p2, p3) in dfs1(0):
    S = [sum(p1), sum(p2), sum(p3)]
    for i1, i2, i3 in indexes:
        p = abs(A-S[i1]) + abs(B-S[i2]) + abs(C-S[i3]) + (len(p1)+len(p2)+len(p3) - 3)*10
        ans = min(ans, p)

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:
N,A,B,C = map(int,input().split())
L = []
for i in range(N):
    L.append(int(input()))

def dfs(cnt,a,b,c):
    if cnt==N:
        if a>0 and b>0 and c>0:
            return abs(a-A)+abs(b-B)+abs(c-C)-30
        else:
            return float('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 i in range(N)]
inf=10**9
def magic(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
    
    ret0 = magic(cur+1, a, b, c)
    ret1 = magic(cur+1, a+l[cur], b, c) + 10
    ret2 = magic(cur+1, a, b+l[cur], c) + 10
    ret3 = magic(cur+1, a, b, c+l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)

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

Submission status: Accepted

Solution code:
from itertools import combinations
from itertools import permutations

def find(X, L, remain=3):
    dis_min = abs(X-min(L))
    stock = min(L)
    for n in range(1, len(L)-remain+2):
        for x in combinations(L, n):
            if abs(X - sum(x)) + 10*(n-1) < dis_min:
                dis_min = abs(X - sum(x)) + 10*(n-1)
                stock = x
    if type(stock) == type(1):
        L.remove(stock)
    else:
        for x in stock:
            L.remove(x)
    return dis_min, stock, L

if __name__ == '__main__':
    N, A, B, C = map(int, input().split())
    L_ini = [int(input()) for _ in range(N)]
    
    S_min = 10**12
    for ABC in permutations([A, B, C], 3):
        L = L_ini.copy()
        S_dis = 0
        for i, X in enumerate(ABC):
            dis, stock, L = find(X, L, 3-i)
            S_dis += dis
        S_min = min(S_min, S_dis)
    print(S_min)

Submission status: Accepted

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

# まず深さ優先探索で扱い方の全通りを列挙する
# 引数depth本分の竹を選んど時の、A,B,Cでそれぞれ扱う竹の総和を引数a,b,cで表す。
def dfs(depth,a,b,c,):
  # 全部の竹の配分が完了したら、A,B,Cに合わせるのに何MP必要か計算する
  if depth == n:
    if min(a,b,c) > 0:
      return abs(a-A) + abs(b-B) + abs(c-C) - 30
    else:
      return 10**9
  # 分岐は４つに別れるためdfsも4つ再帰する
  # 適用する場合 = 合成する場合となるので+10する
  # 初回に余分な+10はreturn時に-30で打ち消す
  # l[depth]の竹をaに適用する場合
  numA = dfs(depth+1,a+l[depth],b,c) + 10
  # l[depth]の竹をbに適用する場合
  numB = dfs(depth+1,a,b+l[depth],c) + 10
  # l[depth]の竹をcに適用する場合
  numC = dfs(depth+1,a,b,c+l[depth]) + 10
  # l[depth]の竹を適用しない場合
  numX = dfs(depth+1,a,b,c)
  return min(numA,numB,numC,numX)
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, a, b, c = LI()
L = IR(n)


def recur(ai, bi, ci, i):
    if i == n:
        return abs(a - ai) + abs(b -bi) + abs(c - ci) - 30 if ai > 0 and bi > 0 and ci > 0 else INF
    l1 = recur(ai + L[i], bi, ci, i+1) + 10
    l2 = recur(ai, bi + L[i], ci, i+1) + 10
    l3 = recur(ai, bi, ci + L[i], i+1) + 10
    l4 = recur(ai, bi, ci, i+1)
    return min(l1, l2, l3, l4)



print(recur(0, 0, 0, 0))

Submission status: Accepted

Solution code:
#N, A, B, C = map(int, inputs[0].split())
#L = [int(i) for i in inputs[1:]]

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

def dfs(cnt,a,b,c):
    if cnt == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30if min(a,b,c) > 0 else 1e9
    r0 = dfs(cnt+1,a,b,c)
    r1 = dfs(cnt+1,a+L[cnt],b,c) + 10
    r2 = dfs(cnt+1,a,b+L[cnt],c) + 10
    r3 = dfs(cnt+1,a,b,c+L[cnt]) + 10
    return min(r0,r1,r2,r3)

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 = 1e9

def calc(x):
    a = []
    b = []
    c = []
    res = 0
    for n in range(N):
        m = (((3<<(2*n)) & x) >> (2*n))
        if m == 1:
            a.append(L[n])
        elif m == 2:
            b.append(L[n])
        elif m == 3:
            c.append(L[n])
    for l, t in zip([a, b, c], [A, B, C]):
        if len(l) == 0:
            return INF
        res += 10*max(len(l)-1, 0) + abs(sum(l) - t)
    return res

ans = INF
for x in range(pow(4, N)):
    ans = min(ans, calc(x))
print(ans)