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

Понимаю задачу. Нам нужно для набора цен определить две суммы: 1) минимальную цену, которую покупатель планировал заплатить, если из каждой группы из 4 товаров бесплатным считался 4-й товар (и он располагал товары так, чтобы это было выгодно для него); 2) цену, которую он фактически заплатит, если кассовая программа переставляет цены на чеке так, чтобы стоимость покупки была максимально возможной (то есть чтобы бесплатным становился минимальный в каждой группе из 4). Алгоритм (для случая "каждый четвертый товар бесплатно"): - Пусть M — число товаров, prices — их цены. - Общая сумма всех цен S = sum(prices). - Количество полных групп по 4: K = floor(M / 4). 1) Минимальная планируемая сумма (исходно, когда 4-й товар в каждой группе — самый дорогой): - Чтобы максимально использовать скидку, в каждой группе из 4 покупатель ставил на место 4-го максимальное значение группы, т.е. платил за три меньших товара. Сумма скидок по группам равна сумме максимумов этих групп. - Для максимизации суммарных максимумов целесообразно выбрать K самых больших цен как максимум в своих группах. - Поэтому минимальная заплатка: P_min = S - (сумма K самых больших цен). 2) Реальная заплата после сортировки кассы (максимизируемая программа): - Программа сортирует цены на чеке так, чтобы общая стоимость была максимальной. При этом бесплатным будет 4-й товар в каждой группе, т.е. в группах из 4 она сработает на минимальном элементе группы. - Чтобы минимизировать сумму бесплатных элементов (и тем самым максимизировать заплату), касса формирует группы так, что в каждой группе 4-й элемент — минимальный среди четырех, что достигается, например, сортировкой цен по убыванию и взятием каждых четырех подряд. - В таком случае сумма бесплатных элементов равна сумме элементов на позициях 4, 8, 12, ... в упорядоченном по убыванию списке цен. - Следовательно, P_actual = S - (сумма цен на позициях 4, 8, 12, ... в списке, отсортированном по убыванию). Итого: - Пусть prices отсортирован по убыванию: p1 >= p2 >= ... >= pM. - P_min = S - sum(p1, p2, ..., pK) (сумма первых K элементов). - P_actual = S - sum(p4, p8, p12, ...) (то есть сумма элементов с индексами 4, 8, 12, ... в 1-based нумерации). Сложность алгоритма: сортировка O(M log M), затем линейные суммирования. Пример с вашей парой чисел - Вход: 4 80 30 50 40 - М = 4, цены: [80, 30, 50, 40], S = 200, K = floor(4/4) = 1. - Сортируем по убыванию: [80, 50, 40, 30]. - P_min = S - сумма первых K цен = 200 - 80 = 120. - P_actual: берем 4-й элемент в списке (индексы 4,8,...): 30. P_actual = 200 - 30 = 170. Ответ по задаче: 120 170 Примечание по возможной путанице в примере - В тексте вы упомянули пример и числа 120 и 160, и в примере сказано «каждый третий» товар. Это, видимо, опечатка в описании примера: задача гласит о «каждом четвертом», а сам пример иногда приводит к другой формулировке. - Если взять именно принцип «каждый четвертый товар бесплатно», как выше, для примера с 80, 30, 50, 40 получится 120 и 170. - Если же в примере использовать принцип «каждый третий товар бесплатно» (для сравнения), расчеты будут другими (например, для тех же цен сумма и результаты изменятся). Поэтому ориентируйтесь на формулировку задачи: каждый четвертый товар бесплатно. Если хотите, могу привести ещё один пример или привести минимальный код на выбранном вами языке (Python/C++/Java) для автоматического вычисления P_min и P_actual.