В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара,…
В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из четырех товаров самый дорогой он поместил на четвертое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной Тогда покупатель разместил товары по-другому. Входные данные В первой строке входного файла находится число М - количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000). В следующих М строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10 000, каждое - в отдельной строке) Цены товаров указаны в произвольном порядке Выходные данные Запишите в ответе два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 4-й товар в любой покупке, состоящей из 4 предметов. А затем запишите цену, которую он заплатил. Покупатель делит товары на группы наиболее выгодным для себя способом Типовой пример организации во входном файле 4 80 30 50 40 При таких исходных данных, если каждый третий товар бесплатно, предполагаемая и действительная суммы равны 120 и 160.
Ниже подробное решение задачи с пошаговым объяснением.
Что нужно посчитать
- Пусть M — количество товаров, цены p1, p2, ..., pM.
- Каждая группа из 4 товаров даёт один бесплатный товар (4-й по порядку в группе). Пусть количество таких групп равно K = floor(M/4) = M // 4.
- План покупателя (как он изначально хотел минимизировать сумму оплаты)
- Он распределял товары по группам так, чтобы в каждой группе бесплатным был самый дорогой товар.
- Чтобы минимизировать общую заплатку, нужно выбрать в каждый из K бесплатных товаров максимально возможную цену, то есть суммировать максимумы K групп. А саму сумму оплаты получить как сумма всех цен минус сумма выбранных бесплатных максимумов.
- Эффективная формула: планируемая цена = сумма всех цен − сумма K наибольших цен.
- Реальная цена оплаты (как посчитает касса, если она сортирует цены так, чтобы стоимость покупки была максимально возможной)
- Программа корзины не учитывает реальное размещение на ленте и делает так, чтобы бесплатные были самыми дешевыми в своих группах (это максимизирует заплаченную сумму).
- Чтобы получить максимальную стоимость, касса сделает бесплатными именно K самых дешевых товаров (если можно как-то собрать группы так, чтобы эти товары оказались 4-ми в своих группах).
- Эффективная формула: реальная цена = сумма всех цен − сумма K самых дешевых цен.
Итого:
- Найдите K = M // 4.
- План: плановая цена = сумма всех p − сумма K наибольших p.
- Реальная: реальная цена = сумма всех p − сумма K наименьших p.
Сложность
- Сортировка нужна для выбора K наибольших и K наименьших элементов.
- В худшем случае O(M log M) время и O(1) дополнительной памяти, если сортировать в одну копию либо держать две суммы, можно оптимизировать до O(M log M) с одной сортировкой.
Пошаговый алгоритм
- Вводим M и массив цен prices[0..M-1].
- Вычисляем total = сумма всех цен.
- К = M // 4.
- Сортируем prices по возрастанию.
- Сумма наименьших K элементов: minK = sum(prices[0..K-1]).
- Сумма наибольших K элементов: maxK = sum(prices[M-K..M-1]). (Если K = 0, эти суммы равны 0.)
- Планируемая цена = total − maxK.
- Реальная цена = total − minK.
- Выводим: планируемая цена и реальная цена, через пробел.
Пример Ввод: 4 80 30 50 40
- M = 4, K = 1, prices = [80, 30, 50, 40], total = 200.
- После сортировки: [30, 40, 50, 80].
- minK = 30, maxK = 80.
- Планируемая цена = 200 − 80 = 120.
- Реальная цена = 200 − 30 = 170. Вывод: 120 170
Комментарий по примерам в задаче В примере в тексте есть несоответствие между описанием и числовыми примерами (упоминается «каждый третий» вместо «каждый четвертый» и итог 120/160 не совпадает с расчётами под четвертый). Правильная трактовка именно как в этом решении: каждый четвертый товар бесплатный, K = floor(M/4); сначала минимальная планируемая сумма, затем реальная сумма по описанной логике.
Если хотите, могу привести короткий код-реализацию на Python или другом языке.
