Задание 4 ЕГЭ по информатике 2027: условие Фано и кодирование

from itertools import combinations, product

# известные коды букв
known = {'Б': '1', 'Р': '01', 'Т': '0011'}
word = 'ННТТББИНН'   # слово, длину кодирования которого ищем
hidden = 'ИН'        # буквы, которым код ещё не назначен

# 1. Свободные слова: не совпадают с известными, не начинаются с них
#    и сами не являются началом известного слова.
candidates = []
for length in range(1, 7):
    for bits in product('01', repeat=length):
        w = ''.join(bits)
        if any(w.startswith(k) or k.startswith(w) for k in known.values()):
            continue
        candidates.append(w)

# 2. Частая буква должна получить короткий код.
freq = sorted((word.count(ch) for ch in hidden), reverse=True)

# 3. Перебираем пары свободных слов и берём самую дешёвую по длине слова.
best = None
for a, b in combinations(candidates, 2):
    if a.startswith(b) or b.startswith(a):
        continue                       # условие Фано нарушено
    cost = sum(f * l for f, l in zip(freq, sorted((len(a), len(b)))))
    best = cost if best is None else min(best, cost)

# 4. Прибавляем вклад букв с известными кодами.
fixed = sum(word.count(ch) * len(code) for ch, code in known.items())
print(best + fixed)

from itertools import product

known = {'Г': '011', 'З': '10', 'Р': '00'}
need = 3          # столько кодов нужно разместить: у букв В, С и Т
used = list(known.values())

# 1. Свободные слова — те, что не конфликтуют с известными кодами.
candidates = []
for length in range(1, 7):
    for bits in product('01', repeat=length):
        w = ''.join(bits)
        if any(w.startswith(k) or k.startswith(w) for k in used):
            continue
        candidates.append(w)
candidates.sort(key=len)


def kraft(words):
    """Сумма 1/2 в степени длины: у однозначного кода она не больше 1."""
    return sum(2 ** (-len(w)) for w in words)


# 2. Идём от коротких слов: слово подходит, если после него остаётся
#    место для кодов остальных букв (или буква всего одна).
for w in candidates:
    left = 1 - kraft(used) - kraft([w])
    if left > 0 or need == 1:
        print(len(w))
        break

from itertools import product

known = {'Б': '0000', 'Ж': '111', 'К': '110', 'Т': '01'}
need = 3          # столько кодов нужно разместить: Д, Р и Ю

# 1. Свободные слова: не заняты, не начинаются с известного кода
#    и сами не являются его началом.
candidates = []
for length in range(1, 7):
    for bits in product('01', repeat=length):
        w = ''.join(bits)
        if any(w.startswith(k) or k.startswith(w) for k in known.values()):
            continue
        candidates.append(w)
candidates.sort(key=len)          # короткие слова считаем первыми

# 2. Ищем тройку попарно совместимых слов с наименьшей суммой длин.
best = None
for i in range(len(candidates)):
    for j in range(i + 1, len(candidates)):
        for k in range(j + 1, len(candidates)):
            a, b, c = candidates[i], candidates[j], candidates[k]
            total = len(a) + len(b) + len(c)
            if best is not None and total >= best:
                break             # слова отсортированы, короче уже не будет
            if (a.startswith(b) or b.startswith(a) or a.startswith(c)
                    or c.startswith(a) or b.startswith(c) or c.startswith(b)):
                continue          # условие Фано нарушено
            best = total
print(best)