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

Вот подробное решение задачи и как действовать, чтобы понять, как максимизировать суммы при такой акции и «обмануть» программу кассы. Суть задачи (для понимания): - Каждые четыре товара дают бесплатно самый дешевый из этих четырех, если сортировка не нужна. - Но касса не учитывает расположение на ленте и сортирует цены внутри каждого блока так, чтобы стоимость покупки была максимально возможной. Это значит: чтобы максимизировать сумму к оплате, программа сделает бесплатным как можно более дешевый товар в каждом блоке из четырех. - Покупатель может располагать товары на ленте в любом порядке, но программа будет перерасчитывать так, чтобы скидка была минимальной. Чтобы все же получить максимальную возможную скидку, нужно правильно располагать товары на ленте перед кассой. Какой же порядок даст покупателю максимальную скидку при агрессивной сортировке кассы? 1) Обозначения и базовый вывод - Пусть всего N товаров, цены: p1, p2, ..., pN. - Число бесплатных товаров равно floor(N/4). Пусть f = floor(N/4). - Если товары на кассе разбиты на группы по четыре и в каждой группе бесплатным становится самый дешевый товар, то сумма скидки равна сумме минимальных цен по каждой группе. 2) Как группировать, чтобы максимизировать сумму скидки - Чтобы сумма минимальных элементов в группах была максимальной, нужно как можно выше поднимать минимальные значения каждой группы. Это достигается, если сначала отсортировать все цены по убыванию, а затем разбивать последовательность на группы по четыре подряд. - Иными словами: возьмем цены в порядке убывания q1 ≥ q2 ≥ ... ≥ qN и сделаем группы: - Группа 1: (q1, q2, q3, q4) — минимальная в этой группе будет q4 - Группа 2: (q5, q6, q7, q8) — минимальная q8 - Группа 3: (q9, q10, q11, q12) — минимальная q12 - и так далее. Почему так: если в какой-либо паре групп мы поменяем элементы местами так, чтобы в одной группе стало меньшее минимальное значение, а в другой — большее, сумма минимальных возрастет или останется такой же. Поэтому оптимум достигается, когда группы формируются из подряд идущих элементов после сортировки по возрастанию (или по убыванию, в любом случае — группа формируется из ближайших по величине элементов). 3) Формула для суммы к оплате - Пусть цены упорядочены по убыванию: q1 ≥ q2 ≥ ... ≥ qN. - Бесплатные товары будут: q4, q8, q12, ..., q_{4f}. - Сумма скидки D = q4 + q8 + q12 + ... + q_{4f}. - Общая сумма всех покупаемых товаров S = q1 + q2 + ... + qN (или суммарная сумма исходных p1..pN). - Стоимость покупки к оплате: P = S − D. 4) Простой пример Допустим, цены: 10, 8, 7, 6, 5, 4, 2, 1 (N=8, f=2). - Упорядочим по убыванию (у нас они уже упорядочены): 10, 8, 7, 6, 5, 4, 2, 1. - Группы: (10,8,7,6) → бесплатный 6; (5,4,2,1) → бесплатный 1. - Сумма скидки D = 6 + 1 = 7. - Сумма всех цен S = 10+8+7+6+5+4+2+1 = 43. - Стоимость к оплате P = 43 − 7 = 36. 5) Что будет важнее помнить - Количество бесплатных товаров равно floor(N/4). - Чтобы максимизировать скидку под удар кассы, покупатель должен располагать большие цены вместе в группах по четыре. Тогда минимальные в каждой группе (то, что становится бесплатным по правилу кассы) будут как можно крупнее, и сумма скидки будет максимальной. 6) Хочется учесть остаток товаров - Если N не делится на 4, то последние r = N mod 4 товаров не образуют полную группу и скидки на них не применяются. В формуле это учитывается через f = floor(N/4): бесплатных товаров ровно f штук. Итоговый ответ для задачи - Максимальную возможную скидку при заданной ситуации получаем, если товары на ленте перед кассой расположены в порядке убывания цены и разбиты на последовательные группы по четыре. - Бесплатные в каждой группе — это четвертый, восьмой, двенадцатый и т. д. по отсортированному по убыванию списку цен. - Общую стоимость покупки можно выразить так: P = S − sum_{i=1}^{f} q_{4i}, где q1 ≥ q2 ≥ ... ≥ qN —Prices отсортированы по возрастанию/убыванию (один из вариантов), S — сумма всех цен, f = floor(N/4). Если хочешь, могу привести ещё пример с твоими конкретными числами или помочь посчитать для набора цен, который у тебя есть.