Задача №113479. Коды, сохраняющие порядок
Двоичный код "— это код, где каждому символу сопоставляется последовательность из единиц и нулей. Код называется префиксным, если ни одно кодовое слово не является префиксом другого. Код называется сохраняющим порядок, если лексикографический порядок кодовых слов совпадает с алфавитным порядком символов.
Рассмотрим текст над алфавитом, содержащим n символов, в котором a 1 раз встречается первый символ, a 2 раз встречается второй символ, ... , a n раз встречается n -й символ. Длина текста после кодирования его префиксным кодом, где первому символу сопоставлена строка длины l 1 , второму — строка длины l 2 , и т. д., будет равна a 1 · l 1 + a 2 · l 2 + ... + a n · l n .
Требуется найти сохраняющий порядок префиксный код, минимизирующий длину закодированного текста.
Первая строка содержит число n "— число символов в алфавите (2 ≤ n ≤ 2000) . Следующая строка содержит n целых чисел "— сколько раз каждый символ встречается в тексте: a 1 , a 2 , ..., a n . Числа положительные и не превосходят 10 9 .
Выведите n двоичных последовательностей "— искомый код.
5 1 8 2 3 1
00 01 10 110 111