eolymp
bolt
Try our new interface for solving problems
Məsələlər

Коммерческий калькулятор

Коммерческий калькулятор

Фирма QISAC выпустила новую версию калькулятора. Этот калькулятор берёт с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна \textbf{5\%} от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму \textbf{N} натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдётся вычисление суммы чисел (тем самым, оказывается нарушен классический принцип \textit{от перестановки мест слагаемых сумма не меняется} :) ). Например, пусть нам нужно сложить числа \textbf{10}, \textbf{11}, \textbf{12} и \textbf{13}. Тогда если мы сначала сложим \textbf{10} и \textbf{11} (это обойдётся нам в \textbf{$1.05}), потом результат - с \textbf{12} (\textbf{$1.65}), и затем - с \textbf{13} (\textbf{$2.3}), то всего мы заплатим \textbf{$5}, если же сначала отдельно сложить \textbf{10} и \textbf{11} (\textbf{$1.05}), потом \textbf{12} и \textbf{13} (\textbf{$1.25}) и, наконец, сложить между собой два полученных числа (\textbf{$2.3}), то в итоге мы заплатим лишь \textbf{$4.6}. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных \textbf{N }чисел. \InputFile Во входном файле записано число \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{100000}). Далее идёт \textbf{N} натуральных чисел, которые нужно сложить, каждое из них не превышает \textbf{10000}. \OutputFile В выходной файл выведите, сколько денег нам потребуется на нахождение суммы этих \textbf{N} чисел с точностью не менее \textbf{10^\{-6\}}.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4
10 11 12 13
Çıxış verilənləri #1
4.600000