Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слову КАША соответствует код 011011010. Какое наименьшее количество двоичных знаков может содержать сообщение, кодирующее слово ОСОКА?
Начнем с расшифровку кодового слова с конца. Букве А не может соответствовать код 0, так как в начале слова есть 0, а в начале должна стоять буква К. 10 подходящий код, но стоит проверить дальше. 010 не может соответствовать А, так как в слове больше нет 010, а буквы А две в слове, 1010 не может по тем же причинам. Далее проверять нет смысла, так как с кодами длиннее мы не уместим вторую букву А. Значит, А — 10. Если перебрать варианты, получается, что 01 10 110 10 единственный подходящий порядок. Выходит, К — 01, А — 10, Ш — 110. Если перерисовать это в дерево, получим, что веточка 00 не занята, буква О встречается два раза, поэтому за 00 подвесим О. Остается разветвить 111 и за 1110 подвесить С. Минимальная длина выходит 12.