В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара,…
В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из четырех товаров самый дорогой он поместил на четвертое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной Тогда покупатель разместил товары по-другому. Входные данные В первой строке входного файла находится число М - количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000). В следующих М строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10 000, каждое - в отдельной строке) Цены товаров указаны в произвольном порядке Выходные данные Запишите в ответе два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 4-й товар в любой покупке, состоящей из 4 предметов. А затем запишите цену, которую он заплатил. Покупатель делит товары на группы наиболее выгодным для себя способом Типовой пример организации во входном файле 4 80 30 50 40 При таких исходных данных, если каждый третий товар бесплатно, предполагаемая и действительная суммы равны 120 и 160.
Задача решается двумя числами: минимальная сумма, которую покупатель планировал заплатить, и фактическая сумма, которую он заплатил после того, как касса попыталась максимизировать стоимость покупки.
Пояснение идеи (для понимания, без привязки к конкретному языку программирования)
- Правило акции: каждые четыре товара образуют группу, в которой 4-й товар бесплатен.
- Чтобы минимизировать заплаченное суммарно, покупатель мог в каждой группе сделать самым дорогим товаром бесплатным (то есть 4-й по группе — самый дорогой). Тогда в группе он платит за три меньших товара. Чтобы максимизировать общую экономию, группы формируются из самых дорогих товаров вместе (выстраиваем товары по возрастанию скидки: в первой группе — самые крупные три цены и максимальная сумма скидки за счёт бесплатного самого большого в группе).
- Однако касса сортирует цены на чеке так, чтобы стоимость покупки оказалась максимально возможной. Это означает, что она делает бесплатным как можно более дешевый товар в каждой группе (то есть 4-й по группе оказывается самым дешевым внутри группы). Соответственно экономия меньше и сумма к оплате выше.
Алгоритм решения
- Вводим M и список цен prices[0..M-1].
- Вычисляем общую сумму total = сумма всех цен.
- Сортируем prices по убыванию (desc).
- Минимальная заплаченная сумма (план покупателя):
- суммаMax = сумма элементов prices[0], prices[4], prices[8], ... до конца массива (то есть максимум каждой группы по отсортированному по убыванию списку).
- minPayment = total - суммаMax.
- Фактическая заплаченная сумма (после сортировки кассы на максимальную стоимость):
- discountCashier = сумма элементов prices[3], prices[7], prices[11], ... до конца массива (то есть 4-й элемент каждой группы по отсортированному по убыванию списку).
- actualPayment = total - discountCashier.
- Выводим две величины: minPayment и actualPayment разделённые пробелом.
Схематичный пример (для проверки)
- Ввод: 4 товара с ценами 80, 30, 50, 40
- total = 200
- Сортировка по убыванию: 80, 50, 40, 30
- Группа1 (вся четвёрка):
- сумма максимумов групп: 80
- minPayment = 200 - 80 = 120
- Для кассы (максимизация стоимости): 4-й товар в группе — самый дешевый: discountCashier = 30
- actualPayment = 200 - 30 = 170
- Вывод: 120 170
Сложность
- Основная операция — сортировка: O(M log M), где M ≤ 10000. Остальные шаги линейны.
Готовые формулы на основе отсортированного по убыванию списка prices:
- total = сумма всех цен
- minPayment = total - sum(price[i], где i = 0, 4, 8, ...)
- actualPayment = total - sum(price[i], где i = 3, 7, 11, ...)
Если хотите, могу привести готовый пример кода на любом языке (Python, C++, Java и т. д.).
