В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара,…
В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из четырех товаров самый дорогой он поместил на четвертое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной. Тогда покупатель разместил товары по-другому. Входные данные В первой строке входного файла находится число М — количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000). В следующих М строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10 000, каждое — в отдельной строке) Цены товаров указаны в произвольном порядке. Выходные данные Запишите в ответе два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 4-й товар в любой покупке, состоящей из 4 предметов. А затем запишите цену, которую он заплатил.
Задача описывает два сценария расчета суммы покупки при акции “каждый 4-й товар бесплатно”.
Ключевые идеи:
Пусть есть M товаров с ценами p1, p2, ..., pM. Пути распределения по группам по 4 штуки влияют на размер скидки.
В первом сценарии покупатель размещал товары так, чтобы в каждой группе из 4 самым дорогим считался бесплатным. Чтобы минимизировать заплаченную цену, он смог сделать скидку максимально возможной: сумма скидок равна сумме максимумов по каждой группе. Максимальная общая скидка достигается, если в каждую из floor(M/4) групп попадают по одному из крупнейших элементов списка. Так что:
- минимальная заплаченная цена в этом сценарии = total_sum всех цен - сумма топ-k элементов, где k = floor(M/4).
Во втором сценарии касса сортирует цены так, чтобы итоговая стоимость была максимально возможной. При такой сортировке в каждый 4-й элемент (после сортировки) оказывается бесплатным тот элемент, который стоит меньше в своей группе; в реальности это эквивалентно сортировке цен по убыванию и вычитанию сумм элементов на позициях 4, 8, 12, ... (то есть каждые 4-й элемент в отсортированном по убыванию списке исчезает из оплаты).
- заплаченная цена во втором случае = total_sum всех цен - сумма цен на позициях 4, 8, 12, ... после сортировки по убыванию.
Пошаговый алгоритм:
- Вчитать M и M цен.
- Вычислить total = сумма всех цен.
- k = M // 4.
- Отсортировать цены по убыванию в массиве desc.
- Скидка по первоначальному замыслу: discount1 = сумма первых k элементов desc. price_min = total - discount1.
- Скидка по программе кассы: discount2 = сумма элементов с индексов 3, 7, 11, ... в desc (то есть каждый 4-й элемент, начиная с 4-го). price_paid = total - discount2.
- Вывести два целых числа: price_min и price_paid.
Сложность:
- Основной расход времени — сортировка: O(M log M). Память — O(M).
Пример:
- Вход: M=8, цены: 10 9 8 7 6 5 4 3
- total = 52, k = 2
- desc = [10,9,8,7,6,5,4,3]
- discount1 = 10 + 9 = 19 → price_min = 52 - 19 = 33
- discount2 = 7 + 3 = 10 → price_paid = 52 - 10 = 42
- Вывод: 33 42
Решение можно реализовать на любом языке программирования. Ниже приведён простой пример на Python:
import sys
def main():
data = sys.stdin.read().strip().split()
if not data:
return
M = int(data[0])
prices = list(map(int, data[1:1+M]))
total = sum(prices)
desc = sorted(prices, reverse=True)
k = M // 4
discount1 = sum(desc[:k])
price_min = total - discount1
discount2 = sum(desc[i] for i in range(3, M, 4))
price_paid = total - discount2
print(price_min, price_paid)
if __name__ == "__main__":
main()
Если нужно, могу адаптировать объяснение под конкретный предмет или класс — скажи, и приведу более формальный (или более простой) вариант решения.
