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:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
def inpl(): return list(map(int, input().split()))

li = list(map(int, input().split()))
N, A, B, C = li[0], li[1], li[2], li[3]
l = sorted([ int(input()) for i in range(N) ])

INF = 1e9

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

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

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
def inpl(): return list(map(int, input().split()))

li = list(map(int, input().split()))
N, A, B, C = li[0], li[1], li[2], li[3]
l = sorted([ int(input()) for i in range(N) ])

ans = 1e9

# 0~3のデカルト積
# 0~3の組み合わせ全部
for X in product(range(4), repeat=N):
    # [[未使用], [Aの作成に使う], [Bの作成に使う], [Cの作成に使う]]
    # 作成の際使う竹は必ず合成する
    P = [[] for _ in range(4)]
    for i, x in enumerate(X):
        P[x].append(l[i])

    # A, B, Cを合成する竹がない場合スキップ
    if min(map(len, P[1:])) == 0:
        continue

    tmp = 0
    for q, d in zip(P[1:], [A, B, C]):
        tmp += 10*(len(q)-1) + abs(d-sum(q))
    if tmp < ans:
        ans = min(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random



def to_4digit(i,n):
    digits = [0 for i in range(n)]
    digit = 0
    while(i>=1):
        digits[digit] = i%4
        digit += 1
        i//=4
    return digits

def main():
    n,a,b,c = map(int,input().split())
    l = []
    for i in range(n):
        l.append(int(input()))
    print(solve(n,a,b,c,l))

def solve(n,a,b,c,l):
    ans = 10**20
    for i in range(4**n-1):
        choice = to_4digit(i,n)
        abc = [0 for i in range(3)]
        mp = 0
        # print(choice)
        for j in range(len(choice)):
            if choice[j]==3:#trash
                pass
            else:
                if abc[choice[j]]!=0:
                    mp += 10
                abc[choice[j]] += l[j]
        if 0 in abc:
            pass
        else:
            mp += abs(abc[0]-a)+abs(abc[1]-b)+abs(abc[2]-c)
            if ans>mp:
                ans = mp


        # print(ans)
    return ans


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
def inpl(): return list(map(int, input().split()))

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

ans = float("INF")

for X in product(range(4), repeat=N):#4**n,無ABC,[0,1,3,1,2,3,0]
    P = [[] for _ in range(4)]
    for i, x in enumerate(X):
        P[x].append(L[i])

    if min(map(len, P[1:])) == 0:
        continue

    tmp = 0
    for Q, D in zip(P[1:], [A, B, C]):
        tmp += 10*(len(Q)-1) + abs(D-sum(Q))#2つを1つにするのに10かかる
    if tmp < ans:
        ans = min(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
def dfs(i, A, B, C):
    global ans
    if i == n:
        if A and B and C:
            ans = min(ans, abs(a - sum(A)) + abs(b - sum(B)) + abs(c - sum(C)) + (len(A) + len(B) + len(C) - 3) * 10)
    else:
        dfs(i + 1, A, B, C)
        dfs(i + 1, A + [L[i]], B, C)
        dfs(i + 1, A, B + [L[i]], C)
        dfs(i + 1, A, B, C + [L[i]])

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

Submission status: Accepted

Solution code:
def dfs(i, A, B, C):
    global ans
    if i == n:
        if A and B and C:
            ans = min(ans, abs(a - sum(A)) + abs(b - sum(B)) + abs(c - sum(C)) + (len(A) + len(B) + len(C) - 3) * 10)
    else:
        # a の肉焼き器に乗せるか、 b の肉焼き器に乗せるか
        dfs(i + 1, A, B, C)
        dfs(i + 1, A + [L[i]], B, C)
        dfs(i + 1, A, B + [L[i]], C)
        dfs(i + 1, A, B, C + [L[i]])

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

Submission status: Accepted

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

INF = 10 ** 5

def dfs(current, a, b, c):
    if current == N:
        if min(a, b, c) > 0:
            return abs(a - A) + abs(b - B) + abs(c - C) - 30
        else:
            return INF

    ret0 = dfs(current + 1, a, b, c)
    ret1 = dfs(current + 1, a + l_list[current], b, c) + 10
    ret2 = dfs(current + 1, a, b + l_list[current], c) + 10
    ret3 = dfs(current + 1, a, b, c + l_list[current]) + 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()))
MP = float('inf')
n = 4  
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)

for X in range(4**N):
  STR = Base_10_to_n(X,n).zfill(N)
  nU = []
  uA = []
  uB = []
  uC = []
  SUBMP = 0
  for l in range(N):
    if STR[l] == '0':
      nU.append(L[l])
    elif STR[l] == '1':
      uA.append(L[l])
    elif STR[l] == '2':
      uB.append(L[l])
    else:
      uC.append(L[l])
    if len(uA) != 0 and len(uB) != 0 and len(uC) != 0:
      SUBMP = (len(uA)+len(uB)+len(uC)-3)*10+abs(sum(uA)-A)+abs(sum(uB)-B)+abs(sum(uC)-C)
      if SUBMP <= MP:
        MP = SUBMP
print(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 _ 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:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc119/editorial.pdf
・公式解の再帰
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits
from datetime import date

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,A,B,C=MAP()
L=[INT() for i in range(N)]
ABC=[A,B,C]

def rec(i, a, b, c):
    if i==N:
        # a,b,cどれか1つでも0なら1本も竹を使ってないので無効
        if min(a, b, c)==0:
            return INF
        # 合体させてきたabcを伸縮させてそれぞれABCにする
        a=abs(A-a)
        b=abs(B-b)
        c=abs(C-c)
        # それぞれ1本目には合体コストが要らないので各-10で-30
        return a+b+c-30
    res=INF
    # i本目の竹は使わない
    res=min(res, rec(i+1, a, b, c))
    # i本目の竹をa(Aにする予定の集まり)に合体させる(b,cも同じ)
    res=min(res, rec(i+1, a+L[i], b, c)+10)
    res=min(res, rec(i+1, a, b+L[i], c)+10)
    res=min(res, rec(i+1, a, b, c+L[i])+10)
    return res

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

Submission status: Accepted

Solution code:
INF = 1000000007


def dfs(cur, a, b, c):
    if cur == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30\
            if 0 < min(a, b, c) else INF

    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
    ret4 = dfs(cur + 1, a, b, c)

    return min(ret1, ret2, ret3, ret4)


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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar  2 11:07:19 2019

@author: Yamazaki Kenichi
"""

N,A,B,C = map(int,input().split())
l = [int(input()) for i in range(N)]
ABC = [0,A,B,C]
def basen(x,n):
    if x//n >0:
        return basen(x//n,n)+str(x%n)
    return str(x%n)

x = []
ans = 10**5
for i in range(4**N):
    k = basen(i,4).zfill(N)
    if any(k.count(c)<1 for c in '123'):
        continue
    abc = ABC[:]
    for j in range(N):
        abc[int(k[j])] -= l[j]
    ans = min(ans,
              (N-k.count('0')-3)*10
              +abs(abc[1])+abs(abc[2])+abs(abc[3]))
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 ans(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 = ans(cur + 1,a,b,c) 
    ret1 = ans(cur + 1,a + l[cur],b,c) + 10
    ret2 = ans(cur + 1,a,b + l[cur],c) + 10
    ret3 = ans(cur + 1,a,b,c + l[cur]) + 10

    return min(ret0,ret1,ret2,ret3)

print(ans(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 = pow(10, 9)

    #cur: 棒の番号 0~N-1

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().strip().split())

L = []
for i in range(N):
  L.append(int(input()))

INF = 10**9
  
def dfs(depth, a, b, c): # current length for A, B, C
  if depth == N:
    if min(a, b, c) > 0:
      return abs(A-a) + abs(B-b) + abs(C-c) - 30
      # -30 is for the first merger (it's unnecessary cost)
    else:
      return INF # a,b,c must be > 0
  else:
    # use L[depth] for A (with merger)
    case_a = dfs(depth+1, a+L[depth], b, c) + 10
    # use L[depth] for B (with merger)
    case_b = dfs(depth+1, a, b+L[depth], c) + 10
    # use L[depth] for C (with merger)
    case_c = dfs(depth+1, a, b, c+L[depth]) + 10
    # not using L[depth] 
    case_x = dfs(depth+1, a, b, c) 

    return min(case_a, case_b, case_c, case_x)
  
print(dfs(0,0,0,0))

Submission status: Accepted

Solution code:
def solve(V, take, A, B, C):
    make = [0, 0, 0] #A, B, C
    cnt = [0, 0, 0] #cntA, cntB, cntC
    cost = 0
    for i in range(N):
        if V[i] == 0:
            continue
        elif V[i] == 1:
            make[0] += take[i]
            if cnt[0] != 0:
                cost += 10
            cnt[0] += 1
        elif V[i] == 2:
            make[1] += take[i]
            if cnt[1] != 0:
                cost += 10
            cnt[1] += 1
        else:
            make[2] += take[i]
            if cnt[2] != 0:
                cost += 10
            cnt[2] += 1
    
    #何もないところからは作れないので、そのときは十分大な数を返す
    if 0 in make:
        return 100000
    cost += (abs(make[0]-A) + abs(make[1]-B) + abs(make[2]-C))
    return cost


        


temp = list(map(int, input().split()))
N = temp[0]
A = temp[1]
B = temp[2]
C = temp[3]
take = []
min = 100000
for i in range(N):
    take.append(int(input()))
zenbu = 4**N
for i in range(zenbu):
    bit = i
    vec = []
    for j in range(N):
        vec.append(bit % 4)
        bit //= 4
    cost = solve(vec, take, A, B, C)
    if cost < min:
        min = cost
print(str(min))

Submission status: Accepted

Solution code:
N, A, B, C = list(map(int, input().split(' ')))
bam_list = []

for i in range(N):
  bam_list.append(int(input()))

INF = 10000000

def enumerate(bam_list, a, b, c):
  if len(bam_list) == 0:
    return abs(A - a) + abs(B - b) + abs(C - c) - 30 if min(a, b, c) > 0 else  INF
  cur = bam_list[0]
  patA = enumerate(bam_list[1:], a + cur , b, c) + 10
  patB = enumerate(bam_list[1:], a, b+cur, c) + 10
  patC = enumerate(bam_list[1:], a, b, c+cur) + 10
  patD = enumerate(bam_list[1:], a, b, c)
  return min(patA, patB, patC, patD)

print(enumerate(bam_list, 0, 0, 0))

Submission status: Accepted

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

ans = 10**10
for l in itertools.product([0, 1, 2, 3], repeat = n):
    if 1 in l and 2 in l and 3 in l:
        count = [0] * 3
        total = [0] * 3
        for i, li in enumerate(l):
            if li != 0:
                count[li-1] += 1
                total[li-1] += ln[i]
        cost = 0
        cost += abs(a - total[0]) + 10 * (count[0] - 1)
        cost += abs(b - total[1]) + 10 * (count[1] - 1)
        cost += abs(c - total[2]) + 10 * (count[2] - 1)
        if ans > cost:
            ans = cost
print(ans)

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))

N,A,B,C=rl()
l=[ri() for _ in range(N)]
ans = 10**18
import itertools
for seq in itertools.product(range(4),repeat=N):
    a,b,c=0,0,0
    rst = 0
    for i in range(N):
        if seq[i]==1:
            a+=l[i]
            rst+=10
        elif seq[i]==2:
            b+=l[i]
            rst+=10
        elif seq[i]==3:
            c+=l[i]
            rst+=10
    if a*b*c != 0:
        rst += abs(A-a)+abs(B-b)+abs(C-c)-30
        if ans > rst:
            ans = rst

print(ans)

Submission status: Accepted

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

def dfs(depth,aa,bb,cc):
        if depth==n:
                #最初の1本の合体コストは無しなので30減らしておく
                ret=abs(a-aa)+abs(b-bb)+abs(c-cc)-30
                if min(aa,bb,cc)>0:
                        return ret
                else:
                        return 10**9+7
        ause=dfs(depth+1,aa+l[depth],bb,cc)+10
        buse=dfs(depth+1,aa,bb+l[depth],cc)+10
        cuse=dfs(depth+1,aa,bb,cc+l[depth])+10
        nonuse=dfs(depth+1,aa,bb,cc)
        return min(ause,buse,cuse,nonuse)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits
from datetime import date

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,A,B,C=MAP()
L=[INT() for i in range(N)]
ABC=[A,B,C]

ABCs=[[] for i in range(3)]
for i, x in enumerate(ABC):
    # どの材料を使って作るとMPがいくらかかるかを全組み合わせ試す
    for j in range(1<<N):
        if j==0:
            ABCs[i].append((INF, j))
            continue
        sm=cnt=0
        for k in range(N):
            if j>>k&1:
                sm+=L[k]
                cnt+=1
        mp=(cnt-1)*10
        mp+=abs(x-sm)
        ABCs[i].append((mp, j))
    ABCs[i].sort()

mn=INF
# 3つだけなので、どれ優先するか順番全部試す
for perm in permutations([0,1,2]):
    msk=sm=0
    for i in perm:
        for j in range(len(ABCs[i])):
            mp,k=ABCs[i][j]
            # ビットに重複がなければ、その組み合わせは使える
            if msk|k==msk^k:
                sm+=mp
                msk+=k
                break
    mn=min(mn, sm)
print(mn)

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))

N,A,B,C=rl()
l=[0]*N
for i in range(N):
    l[i] = ri()
ans = float('inf')
for n in range(4**N):
    a,b,c=0,0,0
    ans_ = 0
    for i in range(N):
        sn = format(n>>(2*i),'0{}b'.format(N))[-2:]
        if sn=='01':
            a+=l[i]
            ans_ += 10
        elif sn=='10':
            b+=l[i]
            ans_ += 10
        elif sn=='11':
            c+=l[i]
            ans_ += 10
    if a!=0 and b!=0 and c!=0:
        ans_ += abs(A-a)+abs(B-b)+abs(C-c) -30
        if ans > ans_:
            ans = ans_

print(ans)

Submission status: Accepted

Solution code:
def ttt (x,y,z,i,m,p,q,r):
  if i==n and (p==0 or q==0 or r==0):
    return 10000000
  if i==n:
    m+=abs(x-a)+abs(y-b)+abs(z-c)
    return m
  else:
    return min(ttt(x,y,z,i+1,m,p,q,r), ttt(x+l[i],y,z,i+1,m+10,p+1,q,r), 
               ttt(x,y+l[i],z,i+1,m+10,p,q+1,r), ttt(x,y,z+l[i],i+1,m+10,p,q,r+1))
n,a,b,c=map(int, input().split())
l=[int(input()) for i in range(n)]
print(ttt(0,0,0,0,0,0,0,0)-30)

Submission status: Accepted

Solution code:
def dfs(index, A, B, C, X ):
    global n, ans, a, b, c
    # print(A, B, C, X)
    mp = 0
    if A and B and C:
        mp += (max(len(A) - 1, 0) + max(len(B) - 1, 0) + max(len(C) - 1, 0) ) * 10
        mp += abs(sum(A) - a) +abs(sum(B) - b) +abs(sum(C) - c) 
        ans = min(ans, mp)
    if index == n:
        return
    dfs(index+1, A + [l[index]], B, C, X)
    dfs(index+1, A, B + [l[index]], C, X)
    dfs(index+1, A, B, C + [l[index]], X)
    dfs(index+1, A, B, C, X + [l[index]])

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

Submission status: Accepted

Solution code:
def dfs(i, d):
    if i == N:
        if any(v == [] and k != 'X' for k, v in d.items()):
            return
        join_mp = (len(d['A']) - 1) * 10 + (len(d['B']) - 1) * 10 + (len(d['C']) - 1) * 10
        sinshoku_mp = abs(A - sum(d['A'])) + abs(B - sum(d['B'])) + abs(C - sum(d['C']))
        mp = join_mp + sinshoku_mp
        cand.append(mp)
        return
    d['A'].append(l[i])
    dfs(i+1, d)
    del d['A'][-1]
    d['B'].append(l[i])
    dfs(i+1, d)
    del d['B'][-1]
    d['C'].append(l[i])
    dfs(i+1, d)
    del d['C'][-1]
    d['X'].append(l[i])
    dfs(i+1, d)
    del d['X'][-1]

if __name__ == '__main__':
    cand = []
    N, A, B, C = map(int, input().split())
    l = []
    for _ in range(N):
        l.append(int(input()))

    a = {'A': [], 'B': [], 'C': [], 'X': []}
    dfs(0, a)
    print(min(cand))

Submission status: Accepted

Solution code:
# 最大8本の竹からA,B,Cの3組に分ける→できない→未解決問題
# 3組に分けるやり方は再帰を用いる
from itertools import combinations


def solver(array, a_set, b_set, c_set):
    if not a_set or not b_set or not c_set:
        return float("inf")
    res_a = sum(array[x] for x in a_set)
    res_b = sum(array[x] for x in b_set)
    res_c = sum(array[x] for x in c_set)

    join_cost = sum([10 * (len(x)-1) for x in [a_set, b_set, c_set] if len(x) > 1])
    res = abs(res_a - a) + abs(res_b - b) + abs(res_c - c) + join_cost
    return res


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

a_comb, b_comb, c_comb = [], [], []
a_index, b_index, c_index = [False for x in range(n)], [False for x in range(n)], [False for x in range(n)]

index_array = [x for x in range(1, n + 1)]
for j in range(0, n + 1):
    a_comb += [set(x) for x in combinations(index_array, j)]
    b_comb += [set(x) for x in combinations(index_array, j)]
    c_comb += [set(x) for x in combinations(index_array, j)]

res = float("inf")
tmp = 0
for a_set in a_comb:
    for b_set in b_comb:
        if a_set & b_set:
            continue
        for c_set in c_comb:
            if a_set & c_set or b_set & c_set:
                continue
            tmp += 1
            res = min(res, solver(array, a_set, b_set, c_set))

print(res)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
li = list(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+li[cur], b, c) + 10
    ret2 = dfs(cur+1, a, b+li[cur], c) + 10
    ret3 = dfs(cur+1, a, b, c+li[cur]) + 10
    return min(ret0, ret1, ret2, ret3)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import itertools
INF = 1e10

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

ans = INF
for prod in itertools.product('NABC', repeat=N):
    if not ('A' in prod and 'B' in prod and 'C' in prod):
        continue

    D = {'A': [], 'B': [], 'C': [], 'N': []}
    for i in range(N):
        D[prod[i]].append(L[i])

    tmp = (len(D['A']) - 1) * 10 + abs(sum(D['A']) - A)
    tmp += (len(D['B']) - 1) * 10 + abs(sum(D['B']) - B)
    tmp += (len(D['C']) - 1) * 10 + abs(sum(D['C']) - C)
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
N, A, B, C = map(int, input().split())
l = list(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=[0]*n
ch=0
ans=0

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

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

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

Submission status: Accepted

Solution code:
from itertools import product
a = [0, 0, 0]
N, a[0], a[1], a[2] = list(map(int,input().split()))
l = []
for i in range(N):
  l.append(int(input()))
mm = float("inf")
for p in product(range(4), repeat=N):
  c = [0]*4
  s = [0]*4
  for i in range(N):
    c[p[i]] += 1
    s[p[i]] += l[i]
  if min(c[:3])==0:
    continue
  m = 0
  for j in range(3):
    m += max(0, c[j]-1)*10
    m += abs(a[j]-s[j])
  mm = min(mm, m)
print(mm)

Submission status: Accepted

Solution code:
import itertools

n,a,b,c=(input().split())
n,a,b,c=int(n),int(a),int(b),int(c)
l=[int(input()) for i in range(n)]
#print(n,a,b,c,l)

ansans=float('inf')
ans=float('inf')

mylist=list(itertools.product(range(4),repeat=n))
#print(len(mylist))
#mylist=[1,2,2,2,3]
for j in range(len(mylist)):
    x,y,z=0,0,0
    for i in range(n):
        if mylist[j][i]==1:
            x+=l[i]
        elif mylist[j][i]==2:
            y+=l[i]
        elif mylist[j][i]==3:
            z+=l[i]
        
    if mylist[j].count(1)>0 and mylist[j].count(2)>0 and mylist[j].count(3) > 0:
        ans=0
        ans+=abs(a-x)+abs(b-y)+abs(c-z)
        compo=0
        for i in range(1,4):
            compo+=mylist[j].count(i)-1
        ans+=10*compo

    if ans < ansans:
        ansans = ans

print(ansans)

Submission status: Accepted

Solution code:
# _*_ coding:utf-8 _*_
#  Atcoder_Beginners_Contest119-C
#  TODO https://atcoder.jp/contests/abc119/tasks/abc119_c

# Copy Editrial　Comment

N,A,B,C = map(int,input().strip().split(' '))
l =[]
for _ in range(0,N,+1):
	banbooLength = int(input().strip())
	l.append(banbooLength)
INF = 10 ** 9

def solveAlgorithm(cursol,aBanboo,bBanboo,cBanboo):
	if cursol==N :
		nowMin = min(aBanboo,bBanboo,cBanboo)
		if nowMin > 0 :
			# 1本目の竹を設定するのにも10コストかかるのでその分減らす
			addAndminusMagic = (abs(aBanboo-A)-10)+(abs(bBanboo-B)-10)+(abs(cBanboo-C)-10)
			return addAndminusMagic
		else:
			return INF
	# cursol+1 Banboo No Select  (No Magic Cost)
	return0 = solveAlgorithm(cursol+1,aBanboo,bBanboo,cBanboo)
	# cursol+1 Banboo A Select and leash magic
	return1 = solveAlgorithm(cursol+1,aBanboo+l[cursol],bBanboo,cBanboo)+10
	# cursol+1 Banboo B Select and leash magic
	return2 = solveAlgorithm(cursol+1,aBanboo,bBanboo+l[cursol],cBanboo)+10
	# cursol+1 Banboo C Select and leash magic
	return3 = solveAlgorithm(cursol+1,aBanboo,bBanboo,cBanboo+l[cursol])+10
	minReturn = min(return0,return1,return2,return3)
	return minReturn

solution = solveAlgorithm(0,0,0,0)
print("{}".format(solution))

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
# l1
# l2
# ...

tmp = input().split()
(N, A, B, C) = (int(tmp[i]) for i in range(4))
L = []
for i in range(N):
    l = int(input())
    L.append(l)
# N = 5
# A = 100
# B = 90
# C = 80
# L = [98, 40, 30, 21, 80]

def recur_function(a, b, c, n):
    if n == N:
        return abs(a - A) + abs(b - B) + abs(c - C) if min(a, b, c) > 0 else 10**9
    ret0 = recur_function(a + L[n], b, c, n + 1) + 10 if a > 0 else recur_function(a + L[n], b, c, n + 1)
    ret1 = recur_function(a, b + L[n], c, n + 1) + 10 if b > 0 else recur_function(a, b + L[n], c, n + 1)
    ret2 = recur_function(a, b, c + L[n], n + 1) + 10 if c > 0 else recur_function(a, b, c + L[n], n + 1)
    ret3 = recur_function(a, b, c, n + 1)
    return min(ret0, ret1, ret2, ret3)

print(recur_function(0, 0, 0, 0))