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 % убедиться в ответе. Для второго типа (выбор кода) и вовсе достаточно глаз: нашёл кратчайшую свободную ветку — вот и ответ. |