Задание № 2 0 Уровень ЕГЭ В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары…
Задание № 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
Если хотите, могу привести решение под конкретный входной файл или подготовить готовый код на другом языке.
