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

Кратко по задаче: - Есть M товарoв с ценами p1,...,pM. - В акции каждый четвертый товар бесплатен (один свободный товар на каждую группу из 4). - Изначально покупатель группировал товары так, чтобы снижение цены было максимально большим, разместив в каждой группе 4-й элемент как самый дорогой. Это позволяет скидке суммировать по крупным значениям. - Программа кассы сортирует цены в чеке так, чтобы итог был максимально большим для покупателя, то есть выбирает бесплатные товары минимально возможной суммой. Ниже приводится решение и обоснование. Задача требует вычислить две суммы: 1) минимальная сумма, которую планировал заплатить изначально, если бесплатным должен быть 4-й товар в каждой группе из 4, и покупатель мог выбрать группы так, чтобы сумма скидок была максимальна. 2) сумма, которую заплатил после того, как кассовая программа сортировала цены так, чтобы получить максимальную стоимость покупки (то есть минимизировала сумму цен бесплатных товаров). Решение (пошагово) - Пусть M — количество товаров, цены — массив prices, сумма всех цен — total. - k = floor(M / 4) — количество бесплатных товаров (по одной на каждую группу из 4). 1) Первая сумма (изначально планировал максимальную скидку): - Чтобы сумма скидок была максимальной, он выбирает k наибольших цен как бесплатные (располагает их в 4-ые позиции групп). - Скидка первая сумма = сумма k наибольших цен. - Ответ1 = total - (сумма k наибольших цен). 2) Вторая сумма (после сортировки кассой так, чтобы стоимость была максимально возможной): - Касса сортирует все цены на чеке по возрастанию (чтобы бесплатные товары были как можно дешевле). - В таком порядке свободны товары на позициях 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. Если захотите, могу привести готовый пример на вашем языке или прогнать тестовый пример из условия.