10967. Комерційний калькулятор


Відправити розв'язок

Бали: 100
Time limit: 2.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

Фірма 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 ≤ 10^5\)).

У другому рядку задано \(N\) натуральних чисел, кожне з яких не перевищує 10000.

Формат вихідних даних

Визначте, скільки грошей нам знадобиться знаходження суми цих \(N\) чисел. Результат має бути виведений із двома знаками після десяткової точки.

Приклад вхідних даних

4
10 11 12 13

Приклад вихідних даних

4.60

Приклад вхідних даних

2
1 1

Приклад вихідних даних

0.10

Коментарі

Ще немає коментарів.