В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из четырех товаров самый дорогой он поместил на четвертое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной. Тогда покупатель разместил товары по-другому. Входные данные В первой строке входного файла находится число М — количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000). В следующих М строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10 000, каждое — в отдельной строке) Цены товаров указаны в произвольном порядке. Выходные данные Запишите в ответе два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 4-й товар в любой покупке, состоящей из 4 предметов. А затем запишите цену, которую он заплатил.

Задача описывает два сценария расчета суммы покупки при акции “каждый 4-й товар бесплатно”. Ключевые идеи: - Пусть есть M товаров с ценами p1, p2, ..., pM. Пути распределения по группам по 4 штуки влияют на размер скидки. - В первом сценарии покупатель размещал товары так, чтобы в каждой группе из 4 самым дорогим считался бесплатным. Чтобы минимизировать заплаченную цену, он смог сделать скидку максимально возможной: сумма скидок равна сумме максимумов по каждой группе. Максимальная общая скидка достигается, если в каждую из floor(M/4) групп попадают по одному из крупнейших элементов списка. Так что: - минимальная заплаченная цена в этом сценарии = total_sum всех цен - сумма топ-k элементов, где k = floor(M/4). - Во втором сценарии касса сортирует цены так, чтобы итоговая стоимость была максимально возможной. При такой сортировке в каждый 4-й элемент (после сортировки) оказывается бесплатным тот элемент, который стоит меньше в своей группе; в реальности это эквивалентно сортировке цен по убыванию и вычитанию сумм элементов на позициях 4, 8, 12, ... (то есть каждые 4-й элемент в отсортированном по убыванию списке исчезает из оплаты). - заплаченная цена во втором случае = total_sum всех цен - сумма цен на позициях 4, 8, 12, ... после сортировки по убыванию. Пошаговый алгоритм: 1) Вчитать M и M цен. 2) Вычислить total = сумма всех цен. 3) k = M // 4. 4) Отсортировать цены по убыванию в массиве desc. 5) Скидка по первоначальному замыслу: discount1 = сумма первых k элементов desc. price_min = total - discount1. 6) Скидка по программе кассы: discount2 = сумма элементов с индексов 3, 7, 11, ... в desc (то есть каждый 4-й элемент, начиная с 4-го). price_paid = total - discount2. 7) Вывести два целых числа: price_min и price_paid. Сложность: - Основной расход времени — сортировка: O(M log M). Память — O(M). Пример: - Вход: M=8, цены: 10 9 8 7 6 5 4 3 - total = 52, k = 2 - desc = [10,9,8,7,6,5,4,3] - discount1 = 10 + 9 = 19 → price_min = 52 - 19 = 33 - discount2 = 7 + 3 = 10 → price_paid = 52 - 10 = 42 - Вывод: 33 42 Решение можно реализовать на любом языке программирования. Ниже приведён простой пример на Python: ```python import sys def main(): data = sys.stdin.read().strip().split() if not data: return M = int(data[0]) prices = list(map(int, data[1:1+M])) total = sum(prices) desc = sorted(prices, reverse=True) k = M // 4 discount1 = sum(desc[:k]) price_min = total - discount1 discount2 = sum(desc[i] for i in range(3, M, 4)) price_paid = total - discount2 print(price_min, price_paid) if __name__ == "__main__": main() ``` Если нужно, могу адаптировать объяснение под конкретный предмет или класс — скажи, и приведу более формальный (или более простой) вариант решения.