Имя входного файла: huffman.in
Имя выходного файла: huffman.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Заданы числа p_1,p_2,...,p_n. Предположив, что имеется текст, содержащий p_1 символов c_1, p_2 символов c_2 и т. д., постройте код Хаффмана и найдите суммарное число битов, необходимое для кодирования такого текста.
Первая строка воходного файла содержит число n (2 ≤ n ≤ 1000). Вторая строка содержит n целых чисел p_1, p_2,..., p_n (1 ≤ p_i ≤ 10^9).
Выведите одно число - число битов, необходимое для кодирования текста с заданным во входном файле количеством вхождений каждого символа.
huffman.in
10
1 2 3 4 5 6 7 8 9 10
huffman.out
173
Имя входного файла: bwt.in
Имя выходного файла: bwt.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Реализуйте преобразование Бароуза-Уиллера.
Рассмотрим строку s, состоящую из строчных латинских букв.
Отсортируем в лексиграфическом порядке все ее циклические сдвиги. Выпишем последние буквы получившихся строк в порядке сортировки.
Входной файл содержит строку, содержащую не более 1000 строчных букв латинского алфавита.
Выведите результат преобразования Барроуза-Уиллера.
bwt.in
abacaba
bwt.out
bcabaaa
Имя входного файла: mtf.in
Имя выходного файла: mtf.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Реализуйте преобразование MTF.
Рассмотрим строку из строчных латинских букв.
Исходно бувы от 'a' до 'z' организованы в список в алфавитном порядке. По очереди рассматриваются слова из латинских букв. Для каждой буквы кодируемой строки выполняется следующее:
-
Выводится ее номер в списке (нумерация с 1)
-
Она перемещается на первую позицию в списке.
Входной файл содержит строку, содержащую не более 1000 строчных букв латинского алфавита.
Пусть длина строки во входном файле равна n. Выведите n чисел от 1 до 26, которые будет выведены при преобразовании Move To Front.
mtf.in
abacaba
mtf.out
1 2 2 3 2 3 2
Имя входного файла: lzw.in
Имя выходного файла: lzw.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Реализуйте кодирование в алгоритме LZW.
Рассмотрим строку s, состоящую из строчных латинских букв.
Исходном имеется словарь, содержазщий символы от 'a' до 'z' с кодами от 0 до 25, соответственно. Алгоритм поддерживает текущий буфер t, исходно инициализированный пустой строкой. Последовательно рассматриваются символы строки s. Пусть очередной символ строки равен c.
Если строка t есть в словаре, то t присваивается tc и обработка символа завершается.
Иначе выводится код t и строка tc помещается в словарь с минимальным свободным кодом. После этого t присваивается значение c и обработка символа завершается.
После этого просмотра всех символов код оставшегося t выводится.
Входной файл содержит строку, содержащую не более 1000 строчных букв латинского алфавита.
Выведите коды, которые выводятся по мере выполнения алгоритма.
lzw.in
abacaba
lzw.out
0 1 0 2 26 0