8 Шпаргалка по заданию 4

Шпаргалка по заданию 4

Условие Фано

Ни один код не является началом (префиксом) другого.
На дереве: все коды сидят в ЛИСТЬЯХ, ни один не стоит по пути к другому.

Дерево кода

влево  = 0     вправо = 1
код = путь от корня до листа
занятый лист закрывает всю ветку под собой

Порядок решения (типы 1 и 2)

1. Нарисовать дерево, отметить известные коды (занятые листья).
2. Найти свободные ветки (куда ещё можно поставить код).
3. Тип 1: посадить буквы в самые короткие ветки, дробя при нехватке; сложить длины.
   Тип 2: взять кратчайшую свободную ветку; при нескольких вариантах —
          нужное числовое значение (наименьшее или наибольшее).

Python (жадная упаковка для типа 1)

import heapq
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)
while len(free)<k:                    # k = сколько букв разместить
    d=heapq.heappop(free); heapq.heappush(free,d+1); heapq.heappush(free,d+1)
print(sum(len(x) for x in fixed)+sum(sorted(free)[:k]))

⚠️ Типичные ошибки

1. Забыл про условие Фано и повесил код на уже занятую ветку. Проверь: все коды — в листьях, ни один не стоит по пути к другому.

2. Посадил две буквы в одну ветку без деления. В ветку длины d помещается только одна буква; для двух её надо разделить на d + 1.

3. В типе 1 взял не самые короткие свободные ветки — сумма получилась больше минимальной. Всегда начинай с самых высоких веток.

4. В типе 2 нашёл кратчайший код, но не оставил место для второй неизвестной буквы. Если букв две — короткую ветку придётся разделить.

5. Перепутал, что просят: наименьшее или наибольшее числовое значение кода. Читай последнюю строку условия внимательно.

6. Потерял ведущий ноль в ответе. Код 011 — это именно 011, а не 11; нули значимы.

💡 Последнее напутствие

Задание 4 — почти гарантированный балл, если не решать его в уме. Нарисуй дерево, отметь занятые коды, найди свободные ветки — и ответ окажется прямо перед глазами. Всё задание держится на одной мысли: занятый код закрывает всю ветку под собой.

Определи тип задачи (сумма длин, выбор кода или кодирование слова), примени правило коротких веток — и балл твой. А если картина сложная, перепроверь себя коротким кодом на Python. Удачи на экзамене — Профиматика с тобой!

Шпаргалка по заданию 4 — Задание 4 ЕГЭ 2027 | Методички — Профиматика