Московская городская олимпиада школьников по информатике,
2005/06 учебный год
при поддержке компании
Задача K. Коммерческий калькулятор
| Имя входного файла: | k.in |
| Имя выходного файла: | k.out |
| Максимальное время работы на одном тесте: | 3 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
Фирма 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 чисел.
Формат входных данных
Во входном файле записано число N (2≤N≤100000). Далее идет N натуральных чисел, которые нужно сложить, каждое из них не превышает 10000.
Формат выходных данных
В выходной файл выведите, сколько денег нам потребуется на нахождение суммы этих N чисел. Результат должен быть выведен с двумя знаками после десятичной точки.
Примеры
| k.in | k.out |
4 10 11 12 13 |
4.60 |
2 1 1 |
0.10 |