Инвертирование Хаффмана
Статическое кодирование Хаффмана — это алгоритм, используемый в основном для сжатия текста. Для текста определенного размера, содержащего N различных символов, алгоритм выбирает N кодов, по одному для каждого символа. Сжатие текста осуществляется с помощью этих кодов. Для выбора кодов алгоритм строит двоичное корневое дерево с N листьями. Если N ≥ 2, дерево можно построить следующим образом:
Для каждого уникального символа в тексте создайте дерево, состоящее из одного узла, и присвойте ему вес, равный количеству вхождений этого символа в тексте.
Создайте множество s, содержащее вышеуказанные N деревьев.
Пока в s больше одного дерева:
(a) Выберите t_1 из s с минимальным весом и удалите его из s.
(b) Выберите t_2 из s с минимальным весом и удалите его из s.
(c) Постройте новое дерево t, используя t_1 как левое поддерево и t_2 как правое поддерево, и присвойте t вес, равный сумме весов t_1 и t_2.
(d) Включите t в s.
Верните единственное оставшееся дерево в s.
Для текста "abracadabra" дерево, полученное в результате этой процедуры, может выглядеть как на левой стороне следующего рисунка, где каждый внутренний узел помечен весом поддерева, укорененного в этом узле. Обратите внимание, что дерево также может выглядеть как на правой стороне рисунка, среди прочих вариантов, поскольку на шагах 3(a) и 3(b) множество s может содержать несколько деревьев с минимальным весом.
Для каждого уникального символа в тексте его код определяется путем в конечном дереве от корня до листа, соответствующего символу. Длина кода равна количеству ребер на этом пути (что совпадает с количеством внутренних узлов на пути). Если предположить, что дерево слева было построено алгоритмом, код для "r" имеет длину 3, а код для "d" — длину 4.
Ваша задача — по заданным длинам N кодов, выбранных алгоритмом, определить минимальный размер (общее количество символов), который может иметь текст, чтобы сгенерированные коды имели эти N длины.
Входные данные
Первая строка содержит целое число N (2 ≤ N ≤ 50), представляющее количество различных символов в тексте. Вторая строка содержит N целых чисел L_i, указывающих длины кодов, выбранных алгоритмом Хаффмана для различных символов (1 ≤ L_i ≤ 50 для i = 1, 2, ..., N). Вы можете быть уверены, что существует по крайней мере одно дерево, построенное, как описано, которое производит коды с заданными длинами.
Выходные данные
Выведите строку с целым числом, представляющим минимальный размер (общее количество символов), который может иметь текст, чтобы сгенерированные коды имели заданные длины.