В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из четырех товаров самый дорогой он поместил на четвертое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной Тогда покупатель разместил товары по-другому. Входные данные В первой строке входного файла находится число М - количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 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. 1) План покупателя (как он изначально хотел минимизировать сумму оплаты) - Он распределял товары по группам так, чтобы в каждой группе бесплатным был самый дорогой товар. - Чтобы минимизировать общую заплатку, нужно выбрать в каждый из K бесплатных товаров максимально возможную цену, то есть суммировать максимумы K групп. А саму сумму оплаты получить как сумма всех цен минус сумма выбранных бесплатных максимумов. - Эффективная формула: планируемая цена = сумма всех цен − сумма K наибольших цен. 2) Реальная цена оплаты (как посчитает касса, если она сортирует цены так, чтобы стоимость покупки была максимально возможной) - Программа корзины не учитывает реальное размещение на ленте и делает так, чтобы бесплатные были самыми дешевыми в своих группах (это максимизирует заплаченную сумму). - Чтобы получить максимальную стоимость, касса сделает бесплатными именно K самых дешевых товаров (если можно как-то собрать группы так, чтобы эти товары оказались 4-ми в своих группах). - Эффективная формула: реальная цена = сумма всех цен − сумма K самых дешевых цен. Итого: - Найдите K = M // 4. - План: плановая цена = сумма всех p − сумма K наибольших p. - Реальная: реальная цена = сумма всех p − сумма K наименьших p. Сложность - Сортировка нужна для выбора K наибольших и K наименьших элементов. - В худшем случае O(M log M) время и O(1) дополнительной памяти, если сортировать в одну копию либо держать две суммы, можно оптимизировать до O(M log M) с одной сортировкой. Пошаговый алгоритм 1. Вводим M и массив цен prices[0..M-1]. 2. Вычисляем total = сумма всех цен. 3. К = M // 4. 4. Сортируем prices по возрастанию. 5. Сумма наименьших K элементов: minK = sum(prices[0..K-1]). 6. Сумма наибольших K элементов: maxK = sum(prices[M-K..M-1]). (Если K = 0, эти суммы равны 0.) 7. Планируемая цена = total − maxK. 8. Реальная цена = total − minK. 9. Выводим: планируемая цена и реальная цена, через пробел. Пример Ввод: 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 или другом языке.