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

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

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

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

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

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

Запишите в ответе разность между суммой, которую заплатил, и суммой, которую планировал заплатить покупатель.

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

4
80
30
50
40

При таких исходных данных, если каждый третий товар бесплатно, предполагаемая и действительная суммы равны 120 и 170. В ответе нужно указать 50 (170 - 120)