Question

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

**Входные данные.**Первая строка входного файла содержит число *N* — количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000).Каждая из последующих *N* строк содержит цены товаров, которые выбирал покупатель (все числа натуральные, не превышающие 10 000, каждое в отдельной строке).Цены товаров указаны в произвольном порядке.**Выходные данные.**В ответе запишите два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 3-⁠й товар в любой покупке, состоящей из 3 предметов. А затем запишите цену, которую он заплатил.Покупатель делит товары на группы наиболее выгодным для себя способом.**Типовой пример входных данных:**480305040При таких исходных данных, если каждый третий товар бесплатно, предполагаемая и действительная суммы равны 120 и 160.

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

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

Изначально покупатель планировал разместить товары так, чтобы в каждой группе самый дорогой товар стоял на третьем месте (и был бесплатным). Однако касса автоматически сортирует цены в каждом чеке по убыванию, делая бесплатным самый дорогой товар из трёх.

Затем покупатель переместил товары оптимальным образом, чтобы минимизировать сумму к оплате при автоматической сортировке.

**Входные данные:**
- Первая строка: число $N$ — количество товаров (не превышает 10 000).
- Следующие $N$ строк: цены товаров (натуральные числа, не превышающие 10 000).

**Выходные данные:**
Два целых числа:
1. Минимальная сумма, которую покупатель планировал заплатить при исходном расположении (каждый третий товар бесплатен).
2. Сумма, которую он заплатил после оптимального переразмещения товаров.

**Пример:**
```
4
80
30
50
40
```

При исходном плане: группы (80, 30, 50) и (40) → платит 80 + 30 + 40 = 150.
При оптимальном переразмещении: группы (80, 40, 30) и (50) → касса сортирует, платит (80 + 40) + 50 = 170.

---

### РЕШЕНИЕ

Идея решения: отсортировать цены по убыванию; для первого ответа исключить каждый третий товар (самый дорогой в каждой группе), для второго — исключить товары на позициях, кратных 3 (после оптимального переразмещения касса делает бесплатным самый дорогой в каждой группе).

**Шаг 1.** Прочитаем файл и отсортируем цены в порядке убывания.

**Шаг 2.** Для первого ответа: если товары разделены на группы по три и в каждой группе бесплатен третий (самый дорогой), то платим за товары, начиная с позиции $\lfloor N / 3 \rfloor$ (пропускаем первые $\lfloor N / 3 \rfloor$ самых дорогих).

**Шаг 3.** Для второго ответа: при оптимальном переразмещении касса всё равно сортирует и делает бесплатным каждый третий по стоимости товар. Платим за товары на позициях, не кратных 3 (индексы 0, 1, 3, 4, 6, 7, …).

```python
f = open("26_6759.txt")
prices = list(map(int, f.readlines()))
prices = prices[1:]
prices.sort(reverse=True)

# Первый ответ: пропускаем первые len(prices)//3 товаров
ans1 = sum(prices[len(prices) // 3:])

# Второй ответ: платим за товары, не на позициях, кратных 3
ans2 = sum(prices) - sum(prices[2::3])

print(ans1, ans2)
```

**Пояснение:**
- `prices[len(prices) // 3:]` — сумма всех товаров, кроме самых дорогих $\lfloor N / 3 \rfloor$ штук (они бесплатны при исходном плане).
- `prices[2::3]` — товары на позициях 2, 5, 8, … (каждый третий, начиная со второго индекса). Вычитаем их из общей суммы.

**Сложность:** $O(n \log n)$ (сортировка).

---

### ОТВЕТ

Задание №26ПрограммированиеЕГЭ по информатике