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: Wrong Answer

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 9999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 9999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    #key = str((index, current_ch, sss, used, costs))
    key = str((index, current_ch, sss, used, (len(costs['a']), sum(costs['a'])), (len(costs['b']), sum(costs['b'])), (len(costs['c']), sum(costs['c']))))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        elif min_a < abs(sum(costs['a']) - a) * 0.2:
            return 9999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    # if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
    if index >= n:
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 9999999
        return memo[key]
    # skip
    temp = min(9999999, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 9999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 9999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 9999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    #key = str((index, current_ch, sss, used, costs))
    key = str((index, current_ch, sss, used, (len(costs['a']), sum(costs['a'])), (len(costs['b']), sum(costs['b'])), (len(costs['c']), sum(costs['c']))))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        elif min_a < abs(sum(costs['a']) - a) * 0.1:
            return 9999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    # if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
    if index >= n:
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 9999999
        return memo[key]
    # skip
    temp = min(9999999, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 9999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 9999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 9999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    key = str((index, current_ch, sss, used, costs))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        elif min_a < abs(sum(costs['a']) - a) * 0.5:
            return 9999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    # if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
    if index >= n:
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 9999999
        return memo[key]
    # skip
    temp = min(9999999, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 9999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 9999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 9999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    key = str((index, current_ch, sss, used, costs))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        else:
            return 9999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    # if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
    if index >= n:
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 9999999
        return memo[key]
    # skip
    temp = min(9999999, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 9999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 9999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 9999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    sumsum = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
    key = str((index, current_ch, sss, used, sumsum))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        elif min_a < abs(sum(costs['a']) - a) * 0.1:
            return 9999999

    if current_ch == 'd':
        memo[key] = sumsum
        return memo[key]
    # if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
    if index >= n:
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 9999999
        return memo[key]
    # skip
    temp = min(9999999, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 9999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 99999999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 99999999999
min_b = 99999999999
min_c = 99999999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    global min_b
    global min_c
    key = str((index, current_ch, sss, used, costs))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        else:
            return 99999999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 99999999999
        return memo[key]
    temp = 99999999999
    # skip
    temp = min(temp, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 99999999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 99999999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 99999999999
min_b = 99999999999
min_c = 99999999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    global min_b
    global min_c
    key = str((index, current_ch, sss, used, costs))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        elif min_a < abs(sum(costs['a']) - a) * 0.1:
            return 99999999999
    if costs['b'] and current_ch == 'c':
        if min_b >= abs(sum(costs['b']) - b):
            min_b = abs(sum(costs['b']) - b)
        # elif min_b < abs(sum(costs['b']) - b) * 0.1:
        #     return 99999999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 99999999999
        return memo[key]
    temp = 99999999999
    # skip
    temp = min(temp, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 99999999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 99999999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 99999999999
min_b = 99999999999
min_c = 99999999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    global min_b
    global min_c
    key = str((index, current_ch, sss, used, costs))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        elif min_a < abs(sum(costs['a']) - a) * 0.1:
            return 99999999999
    if costs['b'] and current_ch == 'c':
        if min_b >= abs(sum(costs['b']) - b):
            min_b = abs(sum(costs['b']) - b)
        # elif min_b < abs(sum(costs['b']) - b) * 0.1:
        #     return 99999999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 99999999999
        return memo[key]
    temp = 99999999999
    # skip
    temp = min(temp, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
      if hoge < 99999999999:
          print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

p=10**5
for i in range(len(PRD)):
    n,a,b,c=0,0,0,0
    for j in range(N):
        if PRD[i][j]==1:
            a+=l[j]
        elif PRD[i][j]==2:
            b+=l[j]
        elif PRD[i][j]==3:
            c+=l[j]
    if 0 in [a,b,c]:
        continue
    if p>abs(A-a)+abs(B-b)+abs(C-c):
        p=abs(A-a)+abs(B-b)+abs(C-c)
        L=PRD[i]

p+=(L.count(1)+L.count(2)+L.count(3)-3)*10
print(p)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from functools import lru_cache

@lru_cache(None)
def doit(a, b, c, idx):
    if idx == len(unused):
        return abs(a - needA) + abs(b - needB) + abs(c - needC)
    return min(
        doit(a, b, c, idx + 1),
        doit(a + unused[idx], b, c, idx + 1) + 10,
        doit(a, b + unused[idx], c, idx + 1) + 10,
        doit(a, b, c + unused[idx], idx + 1) + 10
    )

n, needA, needB, needC = map(int, input().split())
a = [int(input()) for _ in range(n)]
ret = float('inf')
for mask in range(1 << n):
    if bin(mask).count('1') != 3:
        continue
    abc = [a[i] for i in range(n) if (mask >> i) & 1]
    unused = [a[i] for i in range(n) if not (mask >> i) & 1]
    for p in permutations(abc):
        ret = min(ret, doit(p[0], p[1], p[2], 0))
print(ret)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1000000)

def permute(a, idx):
    if idx == len(a):
        permutations.append(a[::])
    for i in range(idx, len(a)):
        a[i], a[idx] = a[idx], a[i]
        permute(a, idx + 1)
        a[i], a[idx] = a[idx], a[i]

def doit(a, b, c, idx):
    if (a, b, c, idx) in memo:
        return memo[a, b, c, idx]
    if idx == len(unused):
        return abs(a - needA) + abs(b - needB) + abs(c - needC)
    memo[a, b, c, idx] = min(
        doit(a, b, c, idx + 1),
        doit(a + unused[idx], b, c, idx + 1) + 10,
        doit(a, b + unused[idx], c, idx + 1) + 10,
        doit(a, b, c + unused[idx], idx + 1) + 10
    )
    return memo[a, b, c, idx]

n, needA, needB, needC = map(int, input().split())
a = [int(input()) for _ in range(n)]
ret = float('inf')
memo = {}
for mask in range(1 << n):
    if bin(mask).count('1') != 3:
        continue
    abc = [a[i] for i in range(n) if (mask >> i) & 1]
    unused = [a[i] for i in range(n) if not (mask >> i) & 1]
    permutations = []
    permute(abc, 0)
    for p in permutations:
        ret = min(ret, doit(p[0], p[1], p[2], 0))
print(ret)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

    
def main():
    ans=10**10
    n,a,b,c=inpm()
    l=inplm(n)
    for an in range(1,n-1):
        for use_a in combinations(range(n),an):
            tank = []
            for j in range(n):
                if j not in use_a:
                    tank.append(j)
            for bn in range(1,n-an):
                for use_b in combinations(tank,bn):
                    tank1=[]
                    for j in tank:
                        if j not in use_b:
                            tank1.append(j)
                    for cn in range(1,n-an-bn):
                        for use_c in combinations(tank1,cn):
                            a_pre=0
                            b_pre=0
                            c_pre=0
                            for i in use_a:
                                a_pre+=l[i]
                            for i in use_b:
                                b_pre+=l[i]
                            for i in use_c:
                                c_pre+=l[i]
                            cnt=0
                            cnt+= (len(use_a)+len(use_b)+len(use_c)-3)*10 + abs(a_pre-a)+abs(c_pre-c)+abs(b_pre-b)
                            if ans>cnt:
                                ans=cnt
                            
    print(ans) 

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def TtoF(a):
  r = ''
  while a >= 1:
    r += str(a%4)
    a = a // 4
  return r
n,a,b,c = map(int,input().split())
l = [int(input()) for i in range(n)]
m = float('INF')
for i in range(1,4**n):
  cur = TtoF(i)
  cur = '0'*(n-len(cur)) + cur
  abc = [[] for i in range(3)]
  for j in range(n):
    if cur[j] != '3':
      abc[int(cur[j])].append(l[j])
  if [] in abc:
    continue
  else:
    m = min(m,10*(len(abc[0])-1)+abs(sum(abc[0])-a)+10*(len(abc[1])-1)+abs(sum(abc[1])-b)+10*(len(abc[2])-1)+abs(sum(abc[2])-c))
print(m)

Submission status: Wrong Answer

Solution code:
N, A, B, C = map(int, input().split())
li = [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
  else:
    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: Wrong Answer

Solution code:
n,a,b,c=map(int,input().split())
l=[]
for i in range(n):
    l.append(int(input()))
op=[[0],[1],[2]]
for i in range(n-1):
    tmp=[]
    for j in op:
        tmp.append(j+[0])
        tmp.append(j+[1])
        tmp.append(j+[2])
    op=tmp
ans=1000000000
for i in op:
    ta=0
    tb=0
    tc=0
    for j in range(len(i)):
        if i[j]==0:
            ta+=l[j]
        elif i[j]==1:
            tb+=l[j]
        else:
            tc+=l[j]
    mp=abs(a-ta)+abs(b-tb)+abs(c-tc)
    if ta==0 or tb==0 or tc==0:
        mp=1000000000
    ans=min(ans,mp)
print(ans)

Submission status: Wrong Answer

Solution code:
"""
できなかった

- 操作 = 四則演算 or 関数
- 交換法則などが成り立つかどうか確認する必要がある
- 再帰的(dfs)に実装する場合、何を初期値として終了条件とするかの理解が必要
  - 前提として全探索であること => 1の解に収束する必要がない
    全ての葉を訪れたときに最小・最大値・解への到達が判定できれば良い

- dfsの実装: いまどの高さにいるかを引数として渡す = 何を高さとして定義するか
  - 階層のインデックスは選択可能な配列のインデックス
  - 同階層のノードは選択肢
  - ノードが持つ値は、その選択をした時の合計の値
  - 終了条件A, B, Cを満たす

- 求める長さA, B, Cの竹 -> 選択肢

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


def dfs(index, a, b, c):
    if N == index:
        if 0 < min(a, b, c):
            return abs(a - A) + abs(b - B) + abs(c - C) - 30
        else:
            return 1 ** 9
    costs = []
    costs.append(dfs(index + 1, a, b, c))
    costs.append(dfs(index + 1, a + l[index], b, c))
    costs.append(dfs(index + 1, a, b + l[index], c))
    costs.append(dfs(index + 1, a, b, c + l[index]))
    return min(costs)


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