images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
26/12/2024 22:33:24

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

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

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

40646.png
Бинарный файл 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
loading