6 Способ через Python — для самопроверки

Способ через Python — для самопроверки

Дерево рисуется за минуту, но на сложной задаче удобно перепроверить себя кодом. Идея: находим свободные ветки, а потом «дробим» самые короткие из них, пока не разместим все буквы, — как настоящий жадный алгоритм.

import heapq

fixed = ['00', '01', '11']   # известные коды
n = 5                        # всего букв

def free_branches(occ):
    occ = set(occ)
    free, stack = [], ['']
    while stack:
        c = stack.pop()
        if c in occ:                       # код занят — ветка закрыта
            continue
        if any(o.startswith(c) and o != c for o in occ):
            stack += [c + '0', c + '1']    # ниже есть занятые — идём глубже
        else:
            free.append(c)                 # свободная ветка целиком
    return free

free = [len(b) for b in free_branches(fixed)]   # длины свободных веток
heapq.heapify(free)
k = n - len(fixed)                # сколько букв ещё разместить
while len(free) < k:              # не хватает мест — делим короткую ветку
    d = heapq.heappop(free)
    heapq.heappush(free, d + 1)
    heapq.heappush(free, d + 1)

new_lengths = sorted(free)[:k]                        # длины новых кодов
answer = sum(len(x) for x in fixed) + sum(new_lengths)
print(answer)     # 12

Как это работает: free_branches обходит дерево и возвращает свободные ветки. Каждую свободную ветку кладём в кучу как её длину. Пока мест меньше, чем букв, берём самую короткую ветку и делим её на две (длина растёт на 1). Когда мест хватило — берём k самых коротких и складываем длины. Результат совпал с ручным: 12.

💡 Когда включать Python

На экзамене задание 4 почти всегда быстрее решить деревом на черновике. Python держи для задач со сложной картиной занятых веток или когда хочется на 100 % убедиться в ответе. Для второго типа (выбор кода) и вовсе достаточно глаз: нашёл кратчайшую свободную ветку — вот и ответ.