Решение задачи #5. Python Яндекс CodeRun, Кафе

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Кафе.
Статус решения: "Решено".

Условие задачи:
Около Петиного университета недавно открылось новое кафе, в котором действует следующая система скидок: при каждой покупке более чем на 100 рублей покупатель получает купон, дающий право на один бесплатный обед (при покупке на сумму 100 рублей и меньше такой купон покупатель не получает).

Однажды Пете на глаза попался прейскурант на ближайшие N дней. Внимательно его изучив, он решил, что будет обедать в этом кафе все N дней, причем каждый день он будет покупать в кафе ровно один обед. Однако стипендия у Пети небольшая, и поэтому он хочет по максимуму использовать предоставляемую систему скидок так, чтобы его суммарные затраты были минимальны. Требуется найти минимально возможную суммарную стоимость обедов и номера дней, в которые Пете следует воспользоваться купонами.

Формат ввода:
В первой строке входного файла записано целое число N (0 ≤≤ N ≤≤ 100). В каждой из последующих N строк записано одно целое число, обозначающее стоимость обеда в рублях на соответствующий день. Стоимость — неотрицательное целое число, не превосходящее 300.

Формат вывода:
В первой строке выдайте минимальную возможную суммарную стоимость обедов. Во второй строке выдайте два числа K1K1​ и K2K2​ — количество купонов, которые останутся неиспользованными у Пети после этих N дней и количество использованных им купонов соответственно.

В последующих K2K2​ строках выдайте в возрастающем порядке номера дней, когда Пете следует воспользоваться купонами. Если существует несколько решений с минимальной суммарной стоимостью, то выдайте то из них, в котором значение K1K1​ максимально (на случай, если Петя когда-нибудь ещё решит заглянуть в это кафе). Если таких решений несколько, выведите любое из них.

Решение:

Python

def main():
    import sys

    # Чтение входных данных
    N = int(input())  # Количество дней
    costs = [int(input()) for _ in range(N)]  # Стоимость обедов для каждого дня

    # Максимальное количество купонов ограничено числом дней
    max_coupons = N + 1  # На случай, если все дни дают купоны

    # dp[i][c] - минимальная стоимость за первые i дней с c оставшимися купонами
    dp = [[float('inf')] * max_coupons for _ in range(N + 1)]
    prev = [[None] * max_coupons for _ in range(N + 1)]  # Для восстановления пути

    # Начальное состояние: на нулевой день затраты равны 0, купонов нет
    dp[0][0] = 0

    # Заполнение таблицы динамики
    for i in range(1, N + 1):
        cost = costs[i - 1]
        for c in range(max_coupons):
            if dp[i - 1][c] == float('inf'):
                continue  # Если предыдущее состояние недостижимо, пропускаем

            # Вариант 1: Платим за обед (получаем купон, если цена > 100)
            new_coupons = c + (1 if cost > 100 else 0)
            if new_coupons < max_coupons and dp[i][new_coupons] > dp[i - 1][c] + cost:
                dp[i][new_coupons] = dp[i - 1][c] + cost
                prev[i][new_coupons] = (i - 1, c, False)  # Не использовали купон

            # Вариант 2: Используем купон (если есть хотя бы один)
            if c > 0 and dp[i][c - 1] > dp[i - 1][c]:
                dp[i][c - 1] = dp[i - 1][c]
                prev[i][c - 1] = (i - 1, c, True)  # Использовали купон

    # Поиск оптимального результата
    min_cost = float('inf')
    best_c = -1
    for c in range(max_coupons):
        if dp[N][c] < min_cost or (dp[N][c] == min_cost and c > best_c):
            min_cost = dp[N][c]
            best_c = c

    # Восстановление пути (номеров дней, когда использовались купоны)
    used_days = []
    i, c = N, best_c
    while i > 0:
        prev_i, prev_c, used_coupon = prev[i][c]
        if used_coupon:
            used_days.append(i)
        i, c = prev_i, prev_c

    # Вывод результатов
    print(min_cost)  # Минимальная суммарная стоимость
    print(best_c, len(used_days))  # Количество оставшихся и использованных купонов
    for day in sorted(used_days):  # Вывод дней в порядке возрастания
        print(day)


if __name__ == '__main__':
    main()

Объяснение кода

1. Чтение входных данных
Мы считываем количество дней N и список стоимостей обедов costs для каждого дня.
N — это число дней, а costs — массив из N элементов, где каждый элемент представляет стоимость обеда на соответствующий день.

2. Инициализация динамического программирования
Создаём двумерный массив dp, где dp[i][c] хранит минимальную сумму за первые i дней с c оставшимися купонами.
Создаём массив prev для отслеживания предыдущих состояний, чтобы можно было восстановить путь (какие дни были выбраны для использования купонов).

3. Заполнение таблицы динамики
Для каждого дня i и каждого возможного количества купонов c мы рассматриваем два варианта:
Вариант 1 : Платим за обед. Если стоимость обеда больше 100 рублей, получаем новый купон.
Вариант 2 : Используем купон, если он доступен (т.е., если c > 0).
Для каждого варианта обновляем значения в таблице dp и сохраняем информацию о предыдущем состоянии в массиве prev.

4. Поиск оптимального результата
После заполнения таблицы dp мы ищем минимальную стоимость среди всех возможных состояний на последнем дне (N).
Если несколько решений имеют одну и ту же минимальную стоимость, выбираем то, которое максимизирует количество оставшихся купонов (best_c).

5. Восстановление пути
Используя массив prev, восстанавливаем список дней, когда использовались купоны.
Результат хранится в списке used_days, который затем сортируется по возрастанию.

6. Вывод результатов
Сначала выводим минимальную сумму (min_cost).
Затем выводим количество оставшихся купонов (best_c) и количество использованных купонов (len(used_days)).
Наконец, выводим номера дней, когда использовались купоны, в порядке возрастания.

Пример работы программы:
Ввод:
5
35
40
101
59
63

Вывод:
235
0 1
5

Объяснение:
Минимальная сумма: 235 рублей.
Осталось 0 купонов, использован 1 купон.
Купон был использован в пятый день (день с индексом 5).

Детали реализации:
Сложность алгоритма :
Временная сложность: O(N2), так как мы перебираем все возможные состояния для каждого дня.
Пространственная сложность: O(N2), так как используем две таблицы размером N×(N+1).

Ограничения :
Код работает корректно при N≤100 и стоимости обедов до 300 рублей.

Обработка граничных случаев:
Если N=0, программа выведет 0 0 (нет дней, нет купонов).
Если все обеды стоят менее 100 рублей, купоны не будут получены.

Источник: hdhai.com