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: Time Limit Exceeded

Solution code:
import itertools 
from collections import defaultdict
d=defaultdict(int)
def take_solve(take):
    key=str(take)
    if key in d.keys():
        return d[key]
    result=float("inf")
    for x,y,z in itertools.permutations(take):
        result=min(result,abs(x-a)+abs(y-b)+abs(z-c))
    d[key]=result
    return result

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

def ans(takes):
    takes=sorted(takes)
    key=str(takes)
    if key in d.keys():
        return d[key]
    m=len(takes)
    result=float("inf")
    if m==3:
        result=min(result,take_solve(takes)+10*(n-m))
    else:
        for i,j in itertools.combinations(list(range(m)),2):
            next_take=[takes[x] for x in range(m) if not x in (i,j)]
            next_take.append(takes[i]+takes[j])
            result=min(result,ans(next_take))
        for i,j,k in itertools.combinations(list(range(m)),3):
            result=min(result,take_solve((takes[i],takes[j],takes[k]))+10*(n-m))
    d[key]=result
    return result
print(ans(l))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, a, b, c = map(int, input().split())
    arr = [int(input()) for i in range(n)]

    min_cost = float("inf")
    for i in range(1, 2 ** n):
        bin_i = "{:08b}".format(i)[::-1]
        arr_i = [arr[x] for x in range(n) if bin_i[x] == "1"]
        cost_i = (len(arr_i) - 1) * 10
        sum_i = sum(arr_i)
    
        for j in range(1, 2 ** n):
            bin_j = "{:08b}".format(j)[::-1]
    
            if any([x == "1" and y == "1" for x, y in zip(bin_i, bin_j)]):
                continue
    
            arr_j = [arr[x] for x in range(n) if bin_j[x] == "1"]
            cost_j = (len(arr_j) - 1) * 10
            sum_j = sum(arr_j)
    
            for k in range(1, 2 ** n):
                bin_k = "{:08b}".format(k)[::-1]
    
                if any([x == "1" and y == "1" for x, y in zip(bin_i, bin_k)]):
                    continue
    
                if any([x == "1" and y == "1" for x, y in zip(bin_j, bin_k)]):
                    continue
    
                arr_k = [arr[x] for x in range(n) if bin_k[x] == "1"]
    
                cost_k = (len(arr_k) - 1) * 10
                sum_k = sum(arr_k)
    
                cost = abs(sum_i - a) + abs(sum_j - b) + abs(sum_k - c) + cost_i + cost_j + cost_k
    
                if min_cost > cost:
                    min_cost = cost
    
    print(min_cost)


main()

Submission status: Time Limit Exceeded

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

def dist(l, A, B, C):
    min_dist = 3000
    for i in range(len(l)):
        for j in range(len(l)):
            for k in range(len(l)):
                if i != j and j != k:
                    dist = abs(A - l[i]) + abs(B - l[j]) + abs(C - l[k])
                    if dist < min_dist:
                        min_dist = dist
    return min_dist

def dfs(l, depth):
    node_score = depth * 10 + dist(l, A, B, C)
    if len(l) == 3:
        return node_score
    for i in range(len(l)):
        for j in range(i+1, len(l)):
            child_l = l[:i] + l[i+1:j] + l[j+1:] + [l[i] + l[j]]
            child_score = dfs(child_l, depth + 1)
            if child_score < node_score:
                node_score = child_score
    return node_score

print(dfs(l, 0))

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C = [int(a) for a in input().split(" ")]
ls = [int(input()) for i in range(N)]
tab = [([float("inf")]*N, ref) for ref in (A, B, C)]
INF = float("inf")
from heapq import heappush, heappop, heapreplace
maxtarg = max(A, B, C)

# O(n)
def solve(ls):
    n = len(ls)
    qs = [[(-INF, -1)]*3 for i in range(3)]
    # 3*n times
    for ref, q in zip((A, B, C), qs):
        for i in range(n):
            val = -abs(ref-ls[i])
            if q[0][0] < val:
                heapreplace(q, (val, i))
    ans = INF
    # 9 times
    for a, i in qs[0]:
        for b, j in qs[1]:
            for c, k in qs[2]:
                if i!=j and j!=k and k!=i:
                    ans = min(ans, -(a+b+c))
    return ans

def dfs(ls):
    n = len(ls)
    if n < 3: return INF
    ans = solve(ls)
    for i in range(n-1):
        for j in range(i+1,n):
            tmp = ls[i]+ls[j]
            if min(maxtarg-ls[i], maxtarg-ls[j]) < 10:
                continue
            ls2 = ls[:i]+ls[i+1:]
            ls2[j-1] = tmp
            ans = min(ans, 10+dfs(ls2))
    return ans

print(dfs(ls))

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C = [int(a) for a in input().split(" ")]
ls = [int(input()) for i in range(N)]
tab = [([float("inf")]*N, ref) for ref in (A, B, C)]
INF = float("inf")
from heapq import heappush, heappop, heapreplace

def solve(ls):
    n = len(ls)
    ans = float("inf")
    qs = [[] for i in range(3)]
    for ref, q in zip((A, B, C), qs):
        for i in range(n):
            val = -abs(ref-ls[i])
            if len(q)<3:
                heappush(q, (val, i))
            elif q[0][0] < val:
                heapreplace(q, (val, i))
    ans = INF
    for a, i in qs[0]:
        for b, j in qs[1]:
            for c, k in qs[2]:
                if i!=j and j!=k and k!=i:
                    ans = min(ans, -(a+b+c))
    return ans

def dfs(ls):
    n = len(ls)
    if n < 3:
        return INF
    ans = solve(ls)
    for i in range(n-1):
        for j in range(i+1,n):
            ls2 = ls[:i]+ls[i+1:]
            ls2[j-1] = ls[i]+ls[j]
            ans = min(ans, 10+dfs(ls2))
    return ans

print(dfs(ls))

Submission status: Time Limit Exceeded

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

def solve(ls):
    n = len(ls)
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if i!=j and j!=k and i!=k:
                    tmp = abs(ls[i]-A)+abs(ls[j]-B)+abs(ls[k]-C)
                    ans = min(ans, tmp)
    return ans

def dfs(ls):
    n = len(ls)
    if n < 3:
        return float("inf")
    ans = solve(ls)
    for i in range(n-1):
        for j in range(i+1,n):
            ls2 = ls[:i]+ls[i+1:]
            ls2[j-1] = ls[i]+ls[j]
            ans = min(ans, 10+dfs(ls2))
    return ans

print(dfs(ls))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def search(arr,arr2,cost,flag):
  global mincost
  if cost>mincost:
    return 0
  if flag==0:
    if len(arr2)==0:
      ans.add(cost)
      if mincost>cost:
        mincost=cost
      return 0
    for i in range(len(arr)):
      search(arr[:i]+arr[i+1:],arr2[1:],cost+abs(arr2[0]-arr[i]),0)
  else:
    if len(arr)>=len(arr2)+1:
      for i in range(len(arr)):
        for j in range(i+1,len(arr)):
          search(arr[:i]+arr[i+1:j]+arr[j+1:]+[arr[i]+arr[j]],arr2,cost+10,0)
          search(arr[:i]+arr[i+1:j]+arr[j+1:]+[arr[i]+arr[j]],arr2,cost+10,1)

n,a,b,c=map(int,input().split())
arr=[int(input()) for _ in range(n)]
arr2=[a,b,c]
ans=set()
mincost=10**9

search(arr,arr2,0,0)
search(arr,arr2,0,1)

ans=sorted(list(ans))
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

l = []
for i in range(N):
    num = int(input())
    l.append(num)
l = np.array(l)

min_loss = 9999999999999999
for pat in itertools.product(["A", "B", "C", "D"], repeat=N):
    if pat.count("A") > 0 and pat.count("B") > 0 and pat.count("C") > 0:
        pat = np.array(pat)
        pat_A = l[pat == "A"]
        pat_B = l[pat == "B"]
        pat_C = l[pat == "C"]

        loss_A = abs(A-pat_A.sum())+10*(len(pat_A)-1)
        loss_B = abs(B-pat_B.sum())+10*(len(pat_B)-1)
        loss_C = abs(C-pat_C.sum())+10*(len(pat_C)-1)

        loss = loss_A+loss_B+loss_C
        min_loss = min(min_loss, loss)

print(min_loss)

Submission status: Time Limit Exceeded

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

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

import itertools
import sys

ans = sys.maxsize
executed = set()
for i in range(3, N+1):
    for bamboos_rearranged in itertools.permutations(bamboos, i):
        execute = ','.join(map(str,bamboos_rearranged))
        if execute in executed:
            continue
        else:
            executed.add(execute)
        #print(bamboos_rearranged)
        for j in range(1, len(bamboos_rearranged)):
            for k in range(j+1, len(bamboos_rearranged)):
                bamboos_abc = (bamboos_rearranged[:j], bamboos_rearranged[j:k], bamboos_rearranged[k:])
                cost = 0
                flag = True
                for n, b in enumerate(bamboos_abc):
                    cost += (len(b) - 1) * 10
                    cost += abs(ABC[n] - sum(b))
                    if cost >= ans:
                        flag = False
                        break
                if flag == True:
                    ans = min(ans, cost)
print(ans)

Submission status: Time Limit Exceeded

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

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

import itertools
import sys

ans = sys.maxsize
executed = set()
for i in range(3, N+1):
    for bamboos_rearranged in itertools.permutations(bamboos, i):
        #print(bamboos_rearranged)
        execute = ','.join(map(str,bamboos_rearranged))
        if execute in executed:
            continue
        else:
            executed.add(execute)
        for j in range(1, len(bamboos_rearranged)):
            for k in range(j+1, len(bamboos_rearranged)):
                bamboos_abc = (bamboos_rearranged[:j], bamboos_rearranged[j:k], bamboos_rearranged[k:])
                cost = 0
                for n, b in enumerate(bamboos_abc):
                    cost += (len(b) - 1) * 10
                    cost += abs(ABC[n] - sum(b))
                ans = min(ans, cost)
print(ans)

Submission status: Time Limit Exceeded

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

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

import itertools
import sys

ans = sys.maxsize

for i in range(3, N+1):
    for bamboos_rearranged in itertools.permutations(bamboos, i):
        #print(bamboos_rearranged)
        for j in range(1, len(bamboos_rearranged)):
            for k in range(j+1, len(bamboos_rearranged)):
                bamboos_abc = (bamboos_rearranged[:j], bamboos_rearranged[j:k], bamboos_rearranged[k:])
                cost = 0
                for n, b in enumerate(bamboos_abc):
                    cost += (len(b) - 1) * 10
                    cost += abs(ABC[n] - sum(b))
                ans = min(ans, cost)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import time

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

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

INF = 10 ** 8

stack = []
depth, a, b, c, mp = 0, 0, 0, 0, 0
stack.append([depth, a, b, c, mp])
flg = []

MP = INF

ct = 0
while stack:
    x = stack.pop(-1)
    if x[0] == N:
        a, b, c = x[1], x[2], x[3]
        mp = x[4] + abs(a-A) + abs(b-B) + abs(c-C) - 30
        if min(a, b, c) > 0 and mp < MP:
            MP = mp
    elif x[0] > N:
        pass
    else:
        tmp = tuple(x)
        for i in range(4):
            if i == 0:
                x[0] += 1
            else:
                x[0] += 1
                x[i] += l[x[0]-1]
                x[4] += 10
            if x not in flg:
                stack.append(x)
                flg.append(tuple(x))
            x = list(tmp)
print(MP)

Submission status: Time Limit Exceeded

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

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

stack = []
stack.append((0, (0, 0, 0), 0))
flg = []
mp = []

while stack:
    x = stack.pop(-1)
    if x[0] == N:
        a = x[1][0]
        b = x[1][1]
        c = x[1][2]
        if min(a, b, c) > 0:
            sum_mp = x[2] + abs(a-A)+abs(b-B)+abs(c-C)
            mp.append(sum_mp)
    else:
        depth = x[0]
        bamboo = x[1]
        MP = x[2]
        for i in range(4):
            bb = list(bamboo)
            if i < 3:
                if bb[i] != 0 and bb[i] < [A, B, C][i]:
                    mm = MP + 10
                    bb[i] += l[depth]
                    if (depth+1, bb, mm) not in flg:
                        stack.append((depth+1, bb, mm))
                        flg.append((depth+1, bb, mm))
                elif bb[i] == 0:
                    mm = MP
                    bb[i] += l[depth]
                    if (depth+1, bb, mm) not in flg:
                        stack.append((depth+1, bb, mm))
                        flg.append((depth+1, bb, mm))
            else:
                mm = MP
                if (depth+1, bb, mm) not in flg:
                    stack.append((depth+1, bb, mm))
                    flg.append((depth+1, bb, mm))

print(min(mp))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

nums = [[[], [], []],
        [[], [], []],
        [[], [], []]] 
    
for l in ls:
    tmpA = []
    for num in nums:
        for i in range(3):
            tmpB = copy.deepcopy(num)
            tmpB[i].append(l)
            tmpA.append(tmpB)
    nums.extend(tmpA)   

ans = 10**20

for num in nums:
    n = abs(A-sum(num[0])) + abs(B-sum(num[1])) + abs(C-sum(num[2])) + 10*(max(0, len(num[0])-1)) + 10*(max(0, len(num[1])-1)) + 10*(max(0, len(num[2])-1))
    
    ans = min(ans, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

import numpy as np

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

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

l = np.array(l)

###########

'''
Aの竹の材料にする、Bの竹の材料にする、Cの竹の材料にする、使わない
'''

min_cost = 1e10

for i in product(np.arange(4), repeat=N):
    i = np.array(i)

    if(np.sum(np.unique(i)) != 6):
        continue

    for_a = l[i == 1]
    for_b = l[i == 2]
    for_c = l[i == 3]

    A_diff = np.abs(np.sum(for_a) - A) + (len(for_a) - 1) * 10
    B_diff = np.abs(np.sum(for_b) - B) + (len(for_b) - 1) * 10
    C_diff = np.abs(np.sum(for_c) - C) + (len(for_c) - 1) * 10

    cost = A_diff + B_diff + C_diff

    if(cost < min_cost):
        min_cost = cost

print(min_cost)

Submission status: Time Limit Exceeded

Solution code:

import itertools
import math
import copy

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

pattern = [list(itertools.combinations(range(x), 3)) for x in range(3, N+1)]

def stretch_shortening(sticks, A, B, C):
    min_cost = 1e10
    
    for i1, i2, i3 in pattern[len(sticks) - 3]:
        cost = abs(sticks[i1] - A) + abs(sticks[i2] - B) + abs(sticks[i3] - C)
        if min_cost > cost:
            min_cost = cost
    return min_cost

def connect(sticks, A, B, C):
    
    min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        if sticks[i1] + sticks[i2] > sticks[-1] and sticks[-1] >= C:
            continue
        if sticks[i1] <= 10 or sticks[i2] <= 10:
            continue
        '''
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        copied_sticks = sorted(copied_sticks)
        '''
        i1_value = sticks[i1]
        i2_value = sticks[i2]
        total_i1_i2 = i1_value + i2_value
        flag = False
        for i, v in enumerate(sticks):
            if total_i1_i2 < v:
                insert_index = i
                sticks.insert(i, total_i1_i2)
                sticks.pop(i2)
                sticks.pop(i1)
                flag = True
                #print(0, sticks)
                break
        if flag == False:
            insert_index = -1
            sticks.insert(len(sticks), total_i1_i2)
            sticks.pop(i2)
            sticks.pop(i1)
            #print(1, sticks[-1], sticks)
        
                
        
        min_cost_connect = connect(sticks, A, B, C)
        sticks.insert(i1, i1_value)
        sticks.insert(i2, i2_value)
        sticks.pop(insert_index)
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost
'''
def connect(sticks, A, B, C, min_cost):
    
    new_min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    if len(sticks) <= 3:
        if min_cost > new_min_cost:
            return new_min_cost
        else:
            return min_cost
    
    if min_cost < new_min_cost:
        return min_cost
    else:
        min_cost = new_min_cost
    
    
    min_copied_sticks = None
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        if sticks[i1] + sticks[i2] > sticks[-1] and sticks[-1] > C:
            continue
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        copied_sticks = sorted(copied_sticks)
        #min_cost_connect = connect(copied_sticks, A, B, C, min_cost)
        min_cost_connect = stretch_shortening(copied_sticks, A, B, C) + (N - len(copied_sticks)) * 10
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
            min_copied_sticks = copied_sticks
    
    if min_copied_sticks is not None:
        min_cost_connect = connect(min_copied_sticks, A, B, C, min_cost)
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost
'''
sticks = []
for _ in range(N):
    sticks.append(int(input()))
sticks = sorted(sticks)

min_cost = connect(sticks, C, B, A) #, 1e10)
#min_cost = stretch_shortening(sticks, A, B, C)
#print(pattern)

print(min_cost)

Submission status: Time Limit Exceeded

Solution code:

import itertools
import math
import copy

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

pattern = [list(itertools.combinations(range(x), 3)) for x in range(3, N+1)]

def stretch_shortening(sticks, A, B, C):
    min_cost = 1e10
    
    for i1, i2, i3 in pattern[len(sticks) - 3]:
        cost = abs(sticks[i1] - A) + abs(sticks[i2] - B) + abs(sticks[i3] - C)
        if min_cost > cost:
            min_cost = cost
    return min_cost

def connect(sticks, A, B, C):
    
    min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        if sticks[i1] + sticks[i2] > sticks[-1] and sticks[-1] > C:
            continue
        if sticks[i1] <= 10 or sticks[i2] <= 10:
            continue
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        copied_sticks = sorted(copied_sticks)
        min_cost_connect = connect(copied_sticks, A, B, C)
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost
'''
def connect(sticks, A, B, C, min_cost):
    
    new_min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    if len(sticks) <= 3:
        if min_cost > new_min_cost:
            return new_min_cost
        else:
            return min_cost
    
    if min_cost < new_min_cost:
        return min_cost
    else:
        min_cost = new_min_cost
    
    
    min_copied_sticks = None
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        if sticks[i1] + sticks[i2] > sticks[-1] and sticks[-1] > C:
            continue
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        copied_sticks = sorted(copied_sticks)
        #min_cost_connect = connect(copied_sticks, A, B, C, min_cost)
        min_cost_connect = stretch_shortening(copied_sticks, A, B, C) + (N - len(copied_sticks)) * 10
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
            min_copied_sticks = copied_sticks
    
    if min_copied_sticks is not None:
        min_cost_connect = connect(min_copied_sticks, A, B, C, min_cost)
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost
'''
sticks = []
for _ in range(N):
    sticks.append(int(input()))
sticks = sorted(sticks)

min_cost = connect(sticks, C, B, A) #, 1e10)
#min_cost = stretch_shortening(sticks, A, B, C)
#print(pattern)

print(min_cost)

Submission status: Time Limit Exceeded

Solution code:

import itertools
import math
import copy

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

pattern = [list(itertools.combinations(range(x), 3)) for x in range(3, N+1)]

def stretch_shortening(sticks, A, B, C):
    #sticks = sorted(sticks)
    min_cost = 1e10
    
    for i1, i2, i3 in pattern[len(sticks) - 3]:
        cost = abs(sticks[i1] - A) + abs(sticks[i2] - B) + abs(sticks[i3] - C)
        if min_cost > cost:
            min_cost = cost
    return min_cost

def connect(sticks, A, B, C):
    
    min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        if sticks[i1] + sticks[i2] > sticks[-1] and sticks[-1] > C:
            continue
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        copied_sticks = sorted(copied_sticks)
        min_cost_connect = connect(copied_sticks, A, B, C)
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost

sticks = []
for _ in range(N):
    sticks.append(int(input()))
sticks = sorted(sticks)

min_cost = connect(sticks, C, B, A)
#min_cost = stretch_shortening(sticks, A, B, C)
#print(pattern)

print(min_cost)

Submission status: Time Limit Exceeded

Solution code:

import itertools
import math
import copy

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


pattern = [list(itertools.combinations(range(x), 3)) for x in range(3, N+1)]

def stretch_shortening(sticks, A, B, C):
    sticks = sorted(sticks)
    min_cost = 1e10
    
    for i1, i2, i3 in pattern[len(sticks) - 3]:
        cost = abs(sticks[i1] - A) + abs(sticks[i2] - B) + abs(sticks[i3] - C)
        if min_cost > cost:
            min_cost = cost
    return min_cost

def connect(sticks, A, B, C):
    
    min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        min_cost_connect = connect(copied_sticks, A, B, C)
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost

sticks = []
for _ in range(N):
    sticks.append(int(input()))

min_cost = connect(sticks, C, B, A)
#min_cost = stretch_shortening(sticks, A, B, C)
#print(pattern)

print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations, combinations


def solve(string):
    n, a, b, c, *l = map(int, string.split())
    ans = 3000
    for _l in permutations(l):
        for i, j, k in combinations(range(1, len(l) + 1), 3):
            tmp = 10 * (i - 1) + abs(a - sum(_l[:i]))
            if tmp > ans:
                continue
            tmp += 10 * (j - i - 1) + abs(b - sum(_l[i:j]))
            if tmp > ans:
                continue
            tmp += 10 * (k - j - 1) + abs(c - sum(_l[j:k]))
            if tmp < ans:
                ans = tmp
    return str(ans)


if __name__ == '__main__':
    n, a, b, c = map(int, input().split())
    print(solve('{} {} {} {}\n'.format(n, a, b, c) + '\n'.join([input() for _ in range(n)])))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations, combinations


def solve(string):
    n, a, b, c, *l = map(int, string.split())
    ans = 3000
    for _l in permutations(l):
        for i, j, k in combinations(range(1, len(l) + 1), 3):
            tmp = 10 * (i - 1) + abs(a - sum(_l[:i])) + 10 * (j - i - 1) + abs(
                b - sum(_l[i:j])) + 10 * (k - j - 1) + abs(c - sum(_l[j:k]))
            if tmp < ans:
                ans = tmp
    return str(ans)


if __name__ == '__main__':
    n, a, b, c = map(int, input().split())
    print(solve('{} {} {} {}\n'.format(n, a, b, c) + '\n'.join([input() for _ in range(n)])))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

import numpy as np

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

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

l = np.array(l)

###########

'''
Aの竹の材料にする、Bの竹の材料にする、Cの竹の材料にする、使わない
'''

min_cost = 1e10

for i in product(np.arange(4), repeat=N):
    i = np.array(i)

    if(np.sum(np.unique(i)) != 6):
        continue

    for_a = l[i == 1]
    for_b = l[i == 2]
    for_c = l[i == 3]

    A_diff = np.abs(np.sum(for_a) - A) + (len(for_a) - 1) * 10
    B_diff = np.abs(np.sum(for_b) - B) + (len(for_b) - 1) * 10
    C_diff = np.abs(np.sum(for_c) - C) + (len(for_c) - 1) * 10

    cost = A_diff + B_diff + C_diff

    if(cost < min_cost):
        min_cost = cost

print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
def rec(A, B, C, L, mp):
    N = len(L)
    ret = 1e18
    
    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
                
                ret = min(ret, mp + abs(A - L[i]) + abs(B - L[j]) + abs(C - L[k]))

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            
            newL = [l for k, l in enumerate(L) if k != i and k != j]
            newL.append(L[i] + L[j])
            ret = min(ret, rec(A, B, C, newL, mp + 10))
    
    return ret

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

print(rec(A, B, C, L, 0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(l, a, b, c):
    n = len(l)
    best = 10**10
    for mask in range(4**n):
        v = np.zeros(4, np.int)
        w = np.zeros(4, np.int)
        num = 0
        for i in range(n):
            j = mask % 4
            mask //= 4
            v[j] += 1
            w[j] += l[i]
        if (v[0] > 0) and (v[1] > 0) and (v[2] > 0):
            cur = 10 * (sum(v[:3]) - 3) + np.sum(np.abs(w[:3]-[a,b,c]))
            best = min(best, cur)
    return best
n, a, b, c = map(int, input().split())
l = [int(input()) for i in range(n)]
print(solve(l, a, b, c))

Submission status: Time Limit Exceeded

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

# 合成を使わないとき
def move(a, b, c ,l):
    ''' a, b, c = int, l = list'''

    x = []
    for i in range(len(l)):
        c_abs = abs(c - l[i])
        m = l[:]
        m.pop(i)
        for j in range(len(m)):
            b_abs = abs(b - m[j])
            p = m[:]
            p.pop(j)
            for k in range(len(p)):
                a_abs = abs(a - p[k])
                x.append(c_abs + b_abs + a_abs)
    return min(x)

# 合成を使う時
def merge(l):
    ''' return possible l list'''

    mp = 0
    if len(l) == 3:
        return l, mp
    a = []
    mp = 10
    for i in range(len(l) - 1):
        x = l[i]
        m = l[:]
        m.pop(i)
        for j in range(len(m)):
            if j < i:
                continue
            y = m[j]
            p = m[:]
            p.pop(j)
            p.append(x + y)
            a.append(p)
    return a, mp

def answer(n, a, b, c, l):
    y = move(a, b, c, l)
    mp = [y]

    if n == 3:
        return mp[0]
    l_new, mp_add = merge(l)
    for i in l_new:
        mp.append(move(a, b, c, i) + mp_add)
        # n = 4 のとき
        if n == 4:
            continue #return = min(mp)
        l_new1, mp_add1 = merge(i)
        for j in l_new1:
            mp.append(move(a, b, c, j) + mp_add + mp_add1)
            # n = 5のとき
            if n == 5:
                continue #return = min(mp)
            l_new2, mp_add2 = merge(j)
            for k in l_new2:
                mp.append(move(a, b, c, k) + mp_add + mp_add1 + mp_add2)
                # n == 6
                if n == 6:
                    continue #return min(mp)
                l_new3, mp_add3 = merge(k)
                for p in l_new3:
                    mp.append(move(a, b, c, p) + mp_add + mp_add1 + mp_add2 + mp_add3)
                    # n == 7
                    if n == 7:
                        continue #return min(mp)
                    l_new4, mp_add4 = merge(p)
                    for q in l_new4:
                        mp.append(move(a, b, c, q) + mp_add + mp_add1 + mp_add2 + mp_add3 + mp_add4)
                        # n == 8
                        if n == 8:
                            continue #return min(mp)
    else:
        return min(mp)

print(answer(n, a, b, c, l))