Подразделы

Другие разделы

Дата и время

25/04/2024 06:33:39

Авторизация

2448. Декодирование Хаффмана

Декодирование Хаффмана

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Бинарный файл input.bin содержит текст, закодированный с помощью кода Хаффмана.

Первая часть файла содержит структуру дерева кодирования. Бит 1 указывает на лист дерева, далее следует 8 бит ASCII-кода, начиная со старшего. Бит 0 указывает на промежуточный лист дерева, далее следует описание левой ветки дерева, кодируемой битом 0, и правой ветки дерева, кодируемой битом 1.

Вторая часть файла содержит закодированный текст. Коды символов задаются в файле, начиная со старшего бита, и соответствуют пути от корня дерева до листа-символа. Символ с кодом 0 завершает ввод и не выводится.

Вывести раскодированный текст.

Бинарный файл input.bin для теста 1

0й байт  1й байт     2й байт  3й байт   4й байт 5й байт  6й байт   7й байт  8й байт
0 123456701 2 3 4 567012345 670123456 7 012345670 123456701 2 345670123 456701234
0 101100001 0 0 0 101100011 101100100 0 100001010 100000000 0 101100010 101110010
   a               c         d           \n        EOF         b         r

8й  9й байт    10й байт    11й байт   12й байт
5 670 123 4 5670 1 2345 6 701 234 5 6701 234567
0 110 111 0 1000 0 1001 0 110 111 0 1010 1011??
a b   r   a c    a d    a b   r   a \n   EOF

Скачать input.bin для теста 1

Пример вывода 1

abracadabra

Пример ввода 1

input.bin (13b)

Назад