Інвертування Гаффмана#6589
Статичне кодування Гаффмана — це алгоритм, що використовується переважно для стиснення тексту. Дано текст, що складається з різних символів, і алгоритм обирає кодів, по одному для кожного символу. Текст стискається за допомогою цих кодів. Для вибору кодів алгоритм будує двійкове кореневе дерево з листками. Для N \geq 2 дерево можна побудувати наступним чином:
Для кожного символу в тексті створіть дерево з одним вузлом і призначте йому вагу, що дорівнює кількості появ символу в тексті.
Створіть множину , що містить ці дерев.
Поки містить більше одного дерева:
(a) Оберіть t_1 з мінімальною вагою з і видаліть його.
(b) Оберіть t_2 з мінімальною вагою з і видаліть його.
(c) Створіть нове дерево з t_1 як лівим піддеревом і t_2 як правим піддеревом, і призначте суму ваг t_1 та t_2.
(d) Додайте у .
Поверніть єдине дерево, що залишилося в .
Для тексту "abracadabra", дерево, створене за цією процедурою, може виглядати як те, що зображено зліва на наступному малюнку, де кожен внутрішній вузол позначений вагою піддерева, що вкорінене в цьому вузлі. Зверніть увагу, що отримане дерево може також виглядати як те, що справа на малюнку, оскільки на кроках 3(a) та 3(b) множина може містити кілька дерев з мінімальною вагою.
Для кожного символу в тексті його код визначається шляхом у кінцевому дереві від кореня до листка, що відповідає символу. Довжина коду — це кількість ребер на цьому шляху (що дорівнює кількості внутрішніх вузлів на шляху). Припускаючи, що дерево зліва було побудоване алгоритмом, код для "r" має довжину , тоді як код для "d" має довжину .
Ваше завдання — за заданими довжинами кодів, обраних алгоритмом, знайти мінімальний розмір (загальну кількість символів), який може мати текст, щоб згенеровані коди мали ці довжини.
Перший рядок містить ціле число (2 \leq N \leq 50), що представляє кількість різних символів у тексті. Другий рядок містить цілих чисел L_i, що вказують довжини кодів, обраних алгоритмом Гаффмана для різних символів (1 \leq L_i \leq 50 для i = 1, 2, \ldots, N). Ви можете припустити, що існує принаймні одне дерево, побудоване, як описано, що продукує коди з даними довжинами.
Виведіть одне ціле число, що представляє мінімальний розмір (загальну кількість символів), який може мати текст, щоб згенеровані коди мали дані довжини.
Приклад 1