В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара,…
В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из четырех товаров самый дорогой он поместил на четвертое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной. Тогда покупатель разместил товары по-другому. Входные данные В первой строке входного файла находится число М — количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000). В следующих М строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10 000, каждое — в отдельной строке) Цены товаров указаны в произвольном порядке. Выходные данные Запишите в ответе два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 4-й товар в любой покупке, состоящей из 4 предметов. А затем запишите цену, которую он заплатил. Покупатель делит товары на группы наиболее выгодным для себя способом.
Кратко по задаче:
- Есть M товарoв с ценами p1,...,pM.
- В акции каждый четвертый товар бесплатен (один свободный товар на каждую группу из 4).
- Изначально покупатель группировал товары так, чтобы снижение цены было максимально большим, разместив в каждой группе 4-й элемент как самый дорогой. Это позволяет скидке суммировать по крупным значениям.
- Программа кассы сортирует цены в чеке так, чтобы итог был максимально большим для покупателя, то есть выбирает бесплатные товары минимально возможной суммой.
Ниже приводится решение и обоснование.
Задача требует вычислить две суммы:
- минимальная сумма, которую планировал заплатить изначально, если бесплатным должен быть 4-й товар в каждой группе из 4, и покупатель мог выбрать группы так, чтобы сумма скидок была максимальна.
- сумма, которую заплатил после того, как кассовая программа сортировала цены так, чтобы получить максимальную стоимость покупки (то есть минимизировала сумму цен бесплатных товаров).
Решение (пошагово)
- Пусть M — количество товаров, цены — массив prices, сумма всех цен — total.
- k = floor(M / 4) — количество бесплатных товаров (по одной на каждую группу из 4).
- Первая сумма (изначально планировал максимальную скидку):
- Чтобы сумма скидок была максимальной, он выбирает k наибольших цен как бесплатные (располагает их в 4-ые позиции групп).
- Скидка первая сумма = сумма k наибольших цен.
- Ответ1 = total - (сумма k наибольших цен).
- Вторая сумма (после сортировки кассой так, чтобы стоимость была максимально возможной):
- Касса сортирует все цены на чеке по возрастанию (чтобы бесплатные товары были как можно дешевле).
- В таком порядке свободны товары на позициях 4, 8, 12, ... (то есть индексы 3, 7, 11 в нулевой индексации).
- Скидка вторая сумма = сумма элементов на позициях 4, 8, 12, ... после сортировки по возрастанию.
- Ответ2 = total - (сумма цен на позициях 4, 8, 12, ... в отсортированном по возрастанию массиве).
Алгоритм в коде (концептуально, без привязки к языку):
- Прочитать M и массив prices.
- total = сумма prices.
- k = M // 4.
- СуммаTopK = сумма k наибольших элементов price.
- Можно просто отсортировать prices убыванию и взять первых k, или использовать кучу для топ-k.
- Ответ1 = total - SumTopK.
- Сортируем prices по возрастанию.
- СуммаFreeByCashier = сумма элементов на позициях 3, 7, 11, ... (0-based).
- Ответ2 = total - SumFreeByCashier.
- Вывести Ответ1 и Ответ2.
Сложность
- Время: O(M log M) из-за двух сортировок (можно оптимизировать до O(M log k) для получения топ-k).
- Память: O(M).
Пояснение корректности
- Первая сумма: можно выбрать k групп так, чтобы их 4-ые (свободные) элементы были ровно k наибольших цен. Это максимально увеличивает общую скидку, поэтому покупатель заплатит минимально возможную сумму при такой схеме.
- Вторая сумма: касса может упорядочить чек так, чтобы сумма скидки была минимальна. Это достигается тем, что из доступных групп 4-ых элементов выбираются минимальные значения как бесплатные. При сортировке по возрастанию бесплатные элементы оказываются на позициях 4, 8, 12 и т. д., что дает минимальную возможную суммарную скидку и максимальную стоимость покупки для покупателя в условиях данной кассовой схемы.
Пример (для иллюстрации)
- Пусть M = 7, цены: 4, 1, 3, 2, 10, 8, 6.
- total = 34, k = 1.
- Первая сумма: топ-1 наибольшая цена = 10; Ответ1 = 34 - 10 = 24.
- Вторая сумма: сортируем по возрастанию: 1, 2, 3, 4, 6, 8, 10..free = элемент на позиции 4 (значение 4). SumFreeByCashier = 4. Ответ2 = 34 - 4 = 30.
- Итого: Ответ1 = 24, Ответ2 = 30.
Рекомендованный код (Python) для быстрой проверки
- Этот фрагмент читает вход, выполняет вычисления и выводит два числа.
def solve(prices): m = len(prices) total = sum(prices) k = m // 4
# Первая сумма: топ-k самых дорогих как бесплатные
topk = sorted(prices, reverse=True)[:k]
sum_topk = sum(topk)
answer1 = total - sum_topk
# Вторая сумма: касса сортирует по возрастанию
asc = sorted(prices)
freebies = sum(asc[i] for i in range(3, m, 4)) # 4-й, 8-й, 12-й... позиции
answer2 = total - freebies
return answer1, answer2
- В файле входа: сначала M, затем M строк с ценами.
- Вывод: две целые числа через пробел: answer1 answer2.
Если захотите, могу привести готовый пример на вашем языке или прогнать тестовый пример из условия.
