@HedgeHog1234

Возникает ошибка, но не знаю какая?

Задача:
Максимальное время работы на одном тесте: 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)


Протокол, показывает, что есть ошибка во время выполнения программы, на одном из нескольких тестах, но не знаю что это за тест и вообще. Помогите, пожалуйста. Заранее спасибо!
  • Вопрос задан
  • 221 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Посмотрите на ограничения в задаче. Введите вашей программе максимальный тест: 15 монеток и сумму примерно в 1000000000. Ваша программа попробует съесть дюжину гигабайт памяти и упадет.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Vindicar
@Vindicar
RTFM!
Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства.

Я не вижу, как ты учитываешь этот факт. Если ты прочитал со входа номиналы монет "5 10 50 100", то тебе нужно использовать для разложения список монет [5, 5, 10, 10, 50, 50, 100, 100].
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы