Задача:
Максимальное время работы на одном тесте: 1 секунда
В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
Входные данные
На вход программы сначала поступает число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).
Выходные данные
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.
Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
Примеры
входные данные
100 6
11 20 30 40 11 99
выходные данные
3
40 30 30
Мой код:
def bankomat(sum, coins, maxCC):
full = 0
for i in range(0, len(coins)):
full = full + coins[i] * maxCC
if full < sum:
return -1
dp = [{'count': full + 1, 'coins': {}} for _ in range(sum + 1)]
coins.sort()
dp[0]['count'] = 0
for i in range(1, sum + 1):
item = dp[i]
optCoin = 0
for j in range(len(coins)):
coin = coins[j]
if coin > i:
break
prev = dp[i - coin]
if item['count'] > prev['count'] + 1 and (prev['coins'].get(coin, 0) < maxCC):
item['count'] = prev['count'] + 1
optCoin = coin
if optCoin:
prev = dp[i - optCoin]
item['coins'] = {**prev['coins'], optCoin: prev['coins'].get(optCoin, 0) + 1}
if dp[sum]['count'] > full:
return 0
arr = []
for coin in dp[sum]['coins']:
c = dp[sum]['coins'][coin]
for i in range(c):
arr.append(int(coin))
return arr
n, m = map(int, input().split())
s = list(map(int,input().split()))
u = bankomat(n, s, 2)
if u == 0:
print(0)
elif u == -1:
print(-1)
else:
print(len(u))
print(*u)
Протокол, показывает, что есть ошибка во время выполнения программы, на одном из нескольких тестах, но не знаю что это за тест и вообще. Помогите, пожалуйста. Заранее спасибо!
Простой
