ЕГЭ 2025 Информатика: кодирование сообщения (задача 4)

Задача 4 (Яндекс)

В новогоднюю ночь Максим решил украсить дом гирляндой из красных и зелёных лампочек, закодировав с их помощью праздничное послание, используя систему шифрования, удовлетворяющую условию Фано (никакое кодовое слово не является началом другого). Он уже придумал кодовые слова для некоторых букв: Н — КК, Ы — КЗ, А — ЗКК, О — ЗКЗ. Помогите Максиму определить минимальное количество лампочек для кодирования сообщения «Новый год».

Заменим К на 0 и З на 1:

Н: 00
Ы: 01
А: 100
О: 101

Сообщение «Новый год» содержит буквы Н, О, В, Ы, Й, Г, О, Д. Построим бинарное дерево, начиная с 1 (так как уже есть 00 и 01). Каждая ветвь разветвляется на 0 и 1. Добавим кодовые слова длиной 4 для В, Й, Г, Д и остальные буквы алфавита.

Подсчитаем длину кодового слова для каждой буквы в сообщении «Новый год»:

Н: 2
О: 3
В: 4 (предполагается)
Ы: 2
Й: 4 (предполагается)
Г: 4 (предполагается)
О: 3
Д: 4 (предполагается)

Общее количество лампочек: 2 + 3 + 4 + 2 + 4 + 4 + 3 + 4 = 26. Ответ: 26.

Задача 8

Определите количество натуральных чисел, удовлетворяющих условиям:

Восьмеричная запись числа содержит ровно четыре цифры.
Сумма любых двух соседних цифр восьмеричной записи нечётна.
Двоичная запись числа не содержит двух идущих подряд единиц.

Решение с использованием модуля itertools:

from itertools import product

k = 0
for w in product('01234567', repeat=4):
    s = ''.join(w)
    if s[0] != '0' and all((int(s[i]) + int(s[i+1])) % 2 != 0 for i in range(len(s)-1)) and '11' not in bin(int(s, 8))[2:]:
        k += 1
print(k) # Ответ: 136

Задача (Яндекс, 5 декабря)

Максим составляет таблицу сигналов для новогодних гирлянд из пяти лампочек красного (К), зелёного (З), белого (Б) и синего (С) цветов. Зелёная лампочка может быть не более двух раз, красные и белые не должны стоять рядом. Сколько разных сигнальных последовательностей возможно?

from itertools import product

k = 0
for w in product('КЗБС', repeat=5):
    l = ''.join(w)
    if l.count('З') <= 2 and 'КБ' not in l and 'БК' not in l:
        k += 1
print(k) # Ответ: 536

Задача 13 (Яндекс)

IP-адрес 137.219.220.63 принадлежит сети. Какое максимальное количество единиц может быть в её маске?

import ipaddress

for m in range(32, -1, -1):
    net = ipaddress.ip_network(f'137.219.220.63/{m}', False)
    if str(ipaddress.ip_address('137.219.220.63')) != str(net.broadcast_address):
        print(m)
        break # Ответ: 25

Задача 13 (Яндекс)

В сети с IP-адресом 185.178.54.144 и маской 255.255.255.0, сколько IP-адресов имеют в двоичной записи правого байта сочетание трёх подряд идущих нулей и четырёх подряд идущих единиц?

import ipaddress

net = ipaddress.ip_network('185.178.54.144/24')
k = 0
for ip in net.hosts():
    ip4 = bin(int(str(ip).split('.')[-1]))[2:].zfill(8)
    if '000' in ip4 and '1111' in ip4:
        k += 1
print(k)

Задача (Файл с последовательностью чисел)

Файл содержит последовательность чисел от 0 до 10000. Определите количество пар чётных чисел (идущих подряд) с наибольшим общим делителем > 20 и наибольшую разность между числами в таких парах.

import math

s = []
with open('17.txt') as f:
    for line in f:
        s.append(int(line))

res = []
for i in range(len(s) - 1):
    if s[i] % 2 == 0 and s[i+1] % 2 == 0 and math.gcd(s[i], s[i+1]) > 20:
        res.append(abs(s[i] - s[i+1]))

print(len(res), max(res) if res else 0) # Ответ: 126 8592