Задача оценки количества денег в копилке

Question

Условие

Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела. Как известно, количество денег в копилке можно определить, только разбив ее. Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.

Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.

Дано E — вес пустой копилки, F — вес копилки с монетами, N — количество достоинств монет, Cᵢ и Wᵢ — достоинство и вес каждого вида монет (1 ⩽ i ⩽ N). Требуется определить минимальную сумму, которая может содержаться в копилке.

Ограничения

Ограничение памяти: 64 Мб Входной файл: input.txt Выходной файл: output.txt

1 ⩽ E ⩽ F ⩽ 10000; 1 ⩽ N ⩽ 100
1 ⩽ Cᵢ ⩽ 10000; 1 ⩽ Wᵢ ⩽ 10000

Формат входного файла

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — Cᵢ Wᵢ. Все числа во входном файле — целые.

Формат выходного файла

В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то в выходной файл следует записать число -1.

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	10 110 2 1 1 30 50	60
2	10 110 2 1 1 50 30	100

Моё решение

Почему-то моя программа ничего не выдает, и я не понимаю, где ошибка.

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    K = int(input[ptr])
    ptr += 1
    K1 = int(input[ptr])
    ptr += 1
    N = int(input[ptr])
    ptr += 1

    coins = []
    for _ in range(N):
        Ci = int(input[ptr])
        ptr += 1
        Mi = int(input[ptr])
        ptr += 1
        coins.append((Mi, Ci)) 

    total_weight = K1 - K
    if total_weight < 0:
        print("No")
        return

    INF = float('inf')
    dp = [INF] * (total_weight + 1)
    dp[0] = 0  

    for weight in range(1, total_weight + 1):
        for Mi, Ci in coins:
            if Mi <= weight:
                if dp[weight - Mi] + Ci < dp[weight]:
                    dp[weight] = dp[weight - Mi] + Ci

    if dp[total_weight] != INF:
        print(dp[total_weight])
    else:
        print("No")

if __name__ == "__main__":
    main()

Answer 1

Если Вам действительно необходимо sys.stdin.read(), то надо завершить ввод.
Допустим, поступает несколько чисел разделённых пробелом.

(.venv) PS D:\BookMemoryOrenburgRegion>
2 3 4 5 6 7 8 9 10 11 12
^Z
No
(.venv) PS D:\BookMemoryOrenburgRegion>

^^^ Здесь ввели строку
>>> переходим на новую строку Enter
>>> команду завершения ввода — Ctrl+Z (Ctrl+D для Linux)
>>> подтверждаем завершение ввода ^^^ Enter

То же с построчным вводом:

Может, стоит просто использовать input()?

Answer 2

Ваша функция успешно проходит заданные тесты. Однако, вы, вероятно, не видите результат, потому что не передаёте данные на стандартный ввод, где функция main ожидает их, выполняя строку input = sys.stdin.read().split().

Предположим, что код сохранён в файле my_script.py, а тестовые данные — в input.txt. Тогда вы можете проверить результат выполнения main() на входных данных такой командой:

python my_script.py < input.txt

Альтернатива - подменить стандартный вход файлом данных в Python:

from contextlib import redirect_stdout
import sys

with open('input.txt') as file:
    sys.stdin = file
    with redirect_stdout(open('output.txt', 'w')):
        main()     # вывод перенаправлен в файл output.txt
    sys.stdin = sys.__stdin__

БЛОГ НА HUSL