Задача 7 из 21

Каждый девятый бесплатно

Время 2 с · память 256 МБ

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

Сначала покупатель рассчитывал, что бесплатным будет самый дорогой товар каждой группы: его он собирался класть на девятое место. Товары он делит на группы так, чтобы заплатить как можно меньше.

Однако программа кассового аппарата не учитывает расположение товаров и в каждой группе делает бесплатным самый дешёвый товар. Узнав об этом, покупатель разделил товары на группы по-другому — так, чтобы и в этом случае заплатить как можно меньше.

Определите минимальную сумму, которую покупатель планировал заплатить изначально, и сумму, которую он заплатил на самом деле.

Входные данные

В первой строке находится число NN — количество товаров (натуральное число, не превышающее 10 00010\,000). В каждой из следующих NN строк находится цена одного товара — натуральное число, не превышающее 10 00010\,000.

Цены идут в произвольном порядке и могут повторяться.

Выходные данные

Выведите два целых числа: сначала минимальную сумму, которую покупатель планировал заплатить изначально, затем сумму, которую он заплатил на самом деле.

Примеры

Ввод 1
10
80
30
50
40
10
10
10
10
10
5
Вывод 1
175 245
Ввод 2
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Вывод 2
136 160

Примечание

В первом примере общая цена равна 255. Изначально можно было получить бесплатно товар за 80, то есть заплатить 175. На деле выгодно объединить девять самых дорогих товаров: касса сделает бесплатным товар за 10, а оставшийся товар за 5 оплачивается полностью. Сумма равна 245.

Во втором примере общая цена равна 171. Планируемая скидка равна 18+17=3518+17=35, фактическая при оптимальном делении — 10+1=1110+1=11.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче