Кратко о задаче
- Метод покупки: каждые 4 товара образуют группу; в группе один товар – бесплатно. В исходной задумке покупатель хотел, чтобы бесплатным становился самый дорогой товар в группе.
- В реальности кассовая программа может переставлять товары в чеке так, чтобы сумма покупки была максимально большой. Значит, она может выбрать, какие именно товары окажутся свободными (4‑й, 8‑й и т.д.) в порядке обработки.
Два платежа, которые нужно вывести
- Минимальная сумма, которую планировал заплатить покупатель, если бесплатным был 4-й товар в каждой группе из 4 (то есть максимально выгоднаяDiscount–максимизирующая стратегия покупателя).
- Реальная сумма, которую он заплатил после того, как касса переставила цены в чеке так, чтобы стоимость покупки была максимальной (то есть выбрали бесплатные товары так, чтобы скидка была минимальной).
Как получить эти два числа
Пусть дано M цен товара: p1, p2, ..., pM. Пусть k = floor(M / 4) — число полноценных групп из 4 предметов.
Общая сумма: total = sum(p_i).
Чтобы минимизировать платёж (покупатель вытянул максимум скидок), в каждой группе 4 предмета свободным становится самый дорогой в группе. Чтобы получить максимально возможную суммарную скидку, можно сделать так, чтобы k самых дорогих предметов стали бесплатными. Тогда скидка = сумма k наибольших цен. Платеж по плану покупателя:
minimal_payment = total - sum_of_k_largest
Чтобы касса заплатила как можно больше, она может выбрать такие 4‑й позиции (свободные места в чекe) минимальные по цене. То есть бесплатными станут k самых маленьких цен. Тогда платёж кассы:
actual_payment = total - sum_of_k_smallest
Итого:
- minimal_payment = total - (сумма k наибольших цен)
- actual_payment = total - (сумма k наименьших цен)
Пример (ваш вход)
Вход:
4
80
30
50
40
- М = 4, k = 1
- total = 80 + 30 + 50 + 40 = 200
- сумма 1 наибольшей цены = 80
- сумма 1 наименьшей цены = 30
Тогда:
- минимальная сумма, которую планировал заплатить: 200 - 80 = 120
- реальная сумма, которую заплатил (когда касса сделала максимально возможную цену): 200 - 30 = 170
Замечание по приведённому в условии примера: в тексте примера написано «если каждый третий товар бесплатно» и приводятся значения 120 и 160. Это противоречит формулировке про «каждый четвёртый товар свободен» и подпишенным расчетам. При стандартном прочтении задачи (free‑item на позиции 4, 8, 12, …) для данного набора чисел правильные ответы: 120 и 170. Если же рассматривать вариант «каждый третий бесплатный», нужно соответствующим образом менять k и логику.
Алгоритм и сложность
- Считать все цены и посчитать total.
- Найти k наибольших элементов и их сумму.
- Найти k наименьших элементов и их сумму.
- minimal_payment = total - sum_k_largest
- actual_payment = total - sum_k_smallest
- Время работы: сортировка O(n log n) обеспечивает удобный способ достать суммы k наибольших и k наименьших (n = M, до 10 000). Память O(n).
Пояснение к реализации (Python-подобный псевдокод)
- Ввод: считываем M и список prices.
- k = M // 4
- total = sum(prices)
- Отсортируем prices по убыванию и возьмём сумма первых k элементов: sum_largest_k
- Отсортируем prices по возрастанию и возьмём сумма первых k элементов: sum_smallest_k
- minimal_payment = total - sum_largest_k
- actual_payment = total - sum_smallest_k
- Выводим: print(minimal_payment, actual_payment)
Пример кода (Python, кратко)
def solve(prices):
M = len(prices)
k = M // 4
total = sum(prices)
prices_desc = sorted(prices, reverse=True)
sum_largest_k = sum(prices_desc[:k])
prices_asc = sorted(prices)
sum_smallest_k = sum(prices_asc[:k])
minimal_payment = total - sum_largest_k
actual_payment = total - sum_smallest_k
return minimal_payment, actual_payment
Пример использования:
prices = [80, 30, 50, 40]
print(*solve(prices)) # вывод: 120 170
Если вам нужно, могу привести решение на другом языке (C++, Java) или разобрать другой пример пошагово.
