Кратчайшее кодовое слово

Ловушка, на которой сыплются чаще всего

По каналу связи передаются сообщения записанные определенным алфавитом (например, русским). Известны кодовые слова некоторых букв. 
Вопрос звучит невинно: «укажите кратчайшее кодовое слово для буквы Д». Ты находишь свободную точку повыше, пишешь ответ — и он неверный.

Потому что ты не оставил место для других букв русского алфавита. А им тоже нужно дать код! 

Два одинаковых вопроса с разными ответами

Сообщение передаётся на русском языке, с использованием всех букв. Некоторым буквам назначили коды 00 (А), 01(Б), 10(В). Какой кратчайший код назначить букве Г, чтобы передать сообщение АБВГ?

Свободна точка 11.

Если бы для передачи использовались только буквы А, Б, В, Г, то подвешать нам нужно было только одну — забираем 11 и радуемся. Ответ 11.

А если в алфавите еще остались буквы — занять 11 нельзя. Оно съест всю ветку, и другим буквам достанется пустота. Приходится спуститься на уровень: точка 11 раздваивается на 110 и 111, и обеим буквам хватает. Ответ уже 110.

Мораль простая: сначала посчитай, скольким ещё сидеть, и только потом занимай. На дерево подвешиваем все буквы из используемого алфавита, а не только те, что используются в указанном сообщении.

Вторая оговорка: «наименьшее по значению»

Часто в условии добавляют: если подходящих слов несколько, взять то, у которого меньше числовое значение. Это значит, что среди слов одной длины 110 идёт раньше, чем 111, а 0100 — раньше, чем 0101. Сначала сравниваем длину, и только при равной длине — значение.

Проверь себя