В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара,…

Понимаю задачу. Нам нужно для набора цен определить две суммы:

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.