Коды и условие Фано

Когда использовать: Нужно найти код одной буквы или проверить, какие коды ещё допустимы.

1. Нарисуйте дерево и разведите известные коды по ветвям 0 и 1.
2. Отметьте кодовые слова как листья.
3. Запретите все продолжения этих слов.
4. Выпишите свободные вершины по возрастанию длины.
5. Отбросьте кандидатов, которые не подходят под дополнительные условия.
6. Выберите самый короткий код и проверьте, что он не ломает коды остальных букв.

По мотивам задач № 16677 и № 10917.

Когда использовать: Даны известные коды, нужно найти минимальную длину заданного слова.

1. Выпишите известные коды и их длины.
2. Посчитайте частоты букв в слове.
3. Найдите все свободные коды, которые можно использовать.
4. Отсортируйте их по длине.
5. Назначьте короткие коды частым буквам, длинные — редким и отсутствующим в слове.
6. Проверьте, что для всех букв алфавита хватает кодов.
7. Сложите частоты, умноженные на длины кодов.

По мотивам задачи № 10917 (база Kompege).

Когда использовать: Дан набор кодов, нужно понять, можно ли его использовать и какие слова конфликтуют.

1. Выпишите все коды.
2. Для каждой пары проверьте, не является ли одно слово началом другого.
3. Если да — код не префиксный, однозначность не гарантирована.
4. Проверьте обратное условие, если оно указано в задаче.
5. При добавлении нового кода проверьте его со всеми старыми.
6. Помните: занятое слово запрещает все свои продолжения.

По мотивам задачи № 16677.

Когда использовать: В задаче явно указано обратное условие Фано или код нужно читать с конца.

1. Выпишите известные коды.
2. Переверните каждое кодовое слово.
3. Постройте дерево для перевёрнутых слов.
4. Найдите свободные ветви и подберите код.
5. Переверните выбранный код обратно.
6. Проверьте, что ни один код не является окончанием другого.

По мотивам задачи № 25756.

Когда использовать: Сказано «не более N знаков», «чётное число единиц», «наибольшее числовое значение» и т. п.

1. Постройте дерево и найдите свободные вершины.
2. Отбросьте вершины глубже разрешённой длины.
3. Если нужно несколько кодов, посчитайте листья в поддереве: 2^(L−d).
4. Примените дополнительное условие к каждому кандидату.
5. Для числового значения сравните int(code, 2).
6. Проверьте, что выбранный код не лишает остальные буквы кодов.

По мотивам задачи № 12678 (база Kompege).

Когда использовать: Много свободных ветвей или несколько ограничений — вручную легко запутаться.

1. Запишите известные коды в словарь.
2. Напишите проверку: новый код не является началом и не имеет начала среди известных.
3. Переберите слова нужной длины через product("01", repeat=L).
4. Отфильтруйте кандидатов по дополнительным условиям.
5. Для каждого кандидата посчитайте длину слова.
6. Выведите минимум и сам код.

from itertools import product

codes = {"П": "00", "О": "1000", "З": "1010", "Ц": "01", "Я": "110"}
word = "ПОЗИЦИЯ"

def ok(code):
    return all(not c.startswith(code) and not code.startswith(c) for c in codes.values())

best = None
for L in range(1, 7):
    for p in product("01", repeat=L):
        code = "".join(p)
        if not ok(code) or code.count("1") % 2:
            continue
        total = sum(len(codes.get(ch, code)) for ch in word)
        if best is None or total < best[0]:
            best = (total, code)

print(best)  # (23, '1001')

Шаблон по мотивам решений задач № 14299, 22485 и 25756.

Когда использовать: В условии сказано, что код должен исправлять одну ошибку, или даны кодовые слова и нужно подобрать ещё одно.

1. Выпишите известные кодовые слова.
2. Для каждой пары посчитайте число позиций, в которых они различаются.
3. Чтобы исправлять одну ошибку, расстояние должно быть не меньше 3.
4. Переберите кандидатов нужной длины.
5. Оставьте те, что отличаются от каждого известного слова не менее чем в 3 позициях.
6. Если кандидатов несколько, выберите с минимальным числовым значением.

По мотивам задачи № 17084 (база Kompege).