Задание EGEINF504F2E: Однозначное кодирование и условие Фано

Известные коды: Белый → 0; Зелёный → 11111; Фиолетовый → 11110; Красный → 1110; Чёрный → 10. Начальные нули являются частью кодового слова и не отбрасываются.

Условие Фано запрещает два случая: новый код является началом уже известного или известный код является началом нового. Изобразим возможные записи мысленно как двоичное дерево: ребро 0 ведёт влево, ребро 1 вправо. Известный код занимает вершину вместе со всеми её продолжениями; его предки также не могут стать кодами других букв.

После исключения занятых ветвей остаются свободные начала: 110. Это самые короткие корни полностью свободных ветвей. Их можно получить обходом дерева: если текущая строка уже является известным кодом, её ветвь закрыта; если она не совпадает с началом ни одного известного кода, вся ветвь свободна; иначе проверяем два продолжения, добавляя 0 и 1. Такой обход охватывает все допустимые новые коды.

Неизвестные коды нужны для Синий. Ищем кратчайший код символа Синий; среди равных длин выбираем наименьшее двоичное значение. Для одной длины числовой порядок совпадает с алфавитным порядком битовых строк.

Проверяем длины по возрастанию. В каждой строке перечислены все коды данной длины, совместимые с известными кодами; после каждого отмечена возможность завершить весь алфавит:
Длина 1: совместимых кодов нет.
Длина 2: совместимых кодов нет.
Длина 3: 110 — подходит.

Первый допустимый уровень имеет длину 3. Все более короткие варианты исключены. На этом уровне с учётом требуемого числового порядка выбираем 110. Пример полного дополнения: Синий → 110.

Проверка: сравним каждую пару кодов в полученном полном наборе. Ни короткое слово не совпадает с началом длинного, ни два слова одинаковой длины не совпадают друг с другом. Все символы получили разные коды, а выбранная запись проходит также проверку минимальной длины и указанного порядка. В ответ переносим битовую строку полностью, включая её начальные нули.

Ответ: 110.