|
Коммерческий калькулятор
(Время: 1 сек. Память: 16 Мб Сложность: 52%)
Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции.
На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым, оказывается нарушен классический принцип «от перестановки мест слагаемых сумма не меняется»  ).
Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в $1.05), потом результат — с 12 ($1.65), и затем — с 13 ($2.3), то всего мы заплатим $5, если же сначала отдельно сложить 10 и 11 ($1.05), потом — 12 и 13 ($1.25) и, наконец, сложить между собой два полученных числа ($2.3), то в итоге мы заплатим лишь $4.6.
Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.
Входные данные
Во входном файле INPUT.TXT записано число N (2 ≤ N ≤ 100000). Далее идет N натуральных чисел, которые нужно сложить, каждое из них не превышает 10000.
Выходные данные
В выходной файл OUTPUT.TXT выведите, сколько денег нам потребуется на нахождение суммы этих N чисел. Результат должен быть выведен с двумя знаками после десятичной точки без лидирующих нулей.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
10 11 12 13 | 4.60 |
| 2 | 2
1 1 | 0.10 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
