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

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

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

В первой строке входного файла находится число $N$ — количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10000). В следующих $N$ строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10000, каждое — в отдельной строке).

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

Запишите в ответе два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 9-й товар в любой покупке, состоящей из 9 предметов. Затем запишите цену, которую он заплатил. Покупатель делит товары на группы наиболее выгодным для себя способом.

Типовой пример организации данных во входном файле

4

80

50

30

40

При таких исходных данных, если каждый третий товар бесплатно, предполагаемая и действительная суммы равны 120 и 160.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/17687_26.txt