Задание № 2 0 Уровень ЕГЭ В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из четырех товаров самый дорогой он поместил на четвертое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной. Тогда покупатель разместил товары по-другому. Входные данные В первой строке входного файла находится число М — количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000). В следующих М строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10 000, каждое — в отдельной строке) Цены товаров указаны в произвольном порядке. Выходные данные Запишите в ответе два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 4-й товар в любой покупке, состоящей из 4 предметов. А затем запишите цену, которую он заплатил. Покупатель делит товары на группы наиболее выгодным для себя способом. Типовой пример организации во входном файле 4 80 30 50 40 При таких исходных данных, если каждый третий товар бесплатно, предполагаемая и действительная суммы равны 120 и 160.

Ниже подробное решение задачи с объяснениями и пошаговым выводом двух сумм. Цель и идеи - Пусть дано M цен: a1, a2, …, aM. Пусть g = floor(M/4) — число полноценных групп по 4 предмета. - В изначальном плане покупатель хотел получить как можно большую дисконтировку: в каждой группе 4-й предмет был бесплатен и должен был быть максимально дорогим внутри своей группы. Чтобы максимально увеличить сумму бесплатных цен, можно выбрать g групп и сделать их максимумами самыми большими ценами. Таким образом минимальная сумма покупки, которую планировал заплатить изначально, равна общему сумме всех цен минус сумма крупнейших g цен. - После кассового подсчета покупатель не учёл расположение и кассир переставил цены так, чтобы сумма покупки была максимально возможной. Чтобы максимизировать общую стоимость, кассир должен сделать бесплатными как можно более дешёвые товары, то есть выбрать g самых маленьких цен как бесплатные. Следовательно, реально заплаченная сумма равна общему сумме всех цен минус сумма самых маленьких g цен. Алгоритм - Ввод: M, далее M цен. - g = M // 4 - S = сумма всех цен - Отсортируем цены по возрастанию: b1 <= b2 <= … <= bM - Сумма самых маленьких g цен: sum_min_g = sum(b1 … bg) - Сумма самых больших g цен: sum_max_g = sum(bM-g+1 … bM) (если g > 0) - Минимальная заплаченная сумма изначально: min_paid = S - sum_max_g - Фактическая заплаченная сумма после сортировки кассира: actual_paid = S - sum_min_g - Вывод: min_paid и actual_paid Пример Для входа: M = 4 prices: 80, 30, 50, 40 S = 200 g = 1 b = [30, 40, 50, 80] sum_min_g = 30 sum_max_g = 80 min_paid = 200 - 80 = 120 actual_paid = 200 - 30 = 170 Итого: 120 170 Замечания - Если M < 4, тогда g = 0, и обе суммы равны S (нет полноценных групп). - Алгоритм работает за O(M log M) из-за сортировки, что при M ≤ 10000 вполне быстро. Псевдокод / простой код на Python (для копирования) - Введите список цен prices - M = len(prices) - g = M // 4 - S = sum(prices) - prices_sorted = sorted(prices) # по возрастанию - sum_min_g = sum(prices_sorted[:g]) - sum_max_g = sum(prices_sorted[-g:]) if g > 0 else 0 - min_paid = S - sum_max_g - actual_paid = S - sum_min_g - вывести: min_paid, actual_paid Код-подсказка (пожалуйста, используйте в вашей среде без изменений форматирования) def solve(prices): M = len(prices) g = M // 4 S = sum(prices) prices_sorted = sorted(prices) sum_min_g = sum(prices_sorted[:g]) sum_max_g = sum(prices_sorted[-g:]) if g > 0 else 0 min_paid = S - sum_max_g actual_paid = S - sum_min_g return min_paid, actual_paid Если хотите, могу привести решение под конкретный входной файл или подготовить готовый код на другом языке.