ЕГЭ: информатика: теория

Простыми словами

У вас есть карта района без подписей расстояний и таблица расстояний, где улицы названы номерами П1, П2… Сначала нужно понять, какой номер — какая точка на карте, и только потом считать маршрут.

Один объект описан дважды: схемой (граф) и таблицей (весовая матрица). Нумерация в них никак не связана — первая работа задания 1 наложить одно на другое.

Пример: схема и таблица

Вопрос: найдите длину кратчайшего пути из А в Е.

Сопоставление по степеням

1. Степени в таблице: П1 — 3, П2 — 1, П3 — 3, П4 — 2, П5 — 3, П6 — 2. На схеме: А, В, Д — 3; Б, Г — 2; Е — 1.
2. Начинаем с уникальной степени: единственная вершина степени 1 — Е = П2. Её сосед Д = П5.
3. Соседи Д на схеме — В, Г, Е; у П5 — П1, П4, П2. Степень 2 среди них только у П4 → Г = П4, тогда В = П1.
4. Оставшиеся: А (степень 3) = П3, Б (степень 2) = П6. Проверка: А–Б есть — клетка П3–П6 заполнена ✓

Кратчайший путь по таблице

Длины берём только из таблицы. Идём от А и для каждого пункта храним наименьшее известное расстояние, обновляя его, если нашёлся обход короче.

Простыми словами

Дан «пазл»: логическая функция $F$ и несколько строк её таблицы истинности, но подписи столбцов x, y, z стёрты. Нужно вернуть каждую подпись на место — так, чтобы все строки фрагмента согласовались с формулой.

Решение всегда одно: построить полную таблицу функции, отобрать строки с нужным значением $F$ и приложить к ним фрагмент.

Логические операции

Разбор задания

$F=(x\to y)\wedge \neg z$. Фрагмент, все строки с $F=1$:

1. Когда $F=1$? Нужно $\neg z=1$, то есть $z=0$, и $x\to y=1$. Подходящие $(x,y)$: $(0,0)$, $(0,1)$, $(1,1)$ — нет только $(1,0)$.
2. Во всех строках $z=0$. Столбец из одних нулей — только первый. Значит, первый — $z$.
3. Второй и третий — $x$ и $y$. Во второй строке они равны $1$ и $0$. Если бы второй был $x$, получилось бы $x=1,y=0$ — запрещённая пара. Значит, второй — $y$, третий — $x$.
4. Проверяем все строки: $(x,y)=(1,1),(0,1),(0,0)$ — все допустимы ✓. Ответ: zyx.

Приёмы и ловушки

print('x y z')
for x in range(2):
    for y in range(2):
        for z in range(2):
            F = (x <= y) and (not z)
            if F:
                print(x, y, z)

Простыми словами

Телефонные номера экстренных служб устроены так, что ни один не является началом другого: набрали 112 — сразу звонок, ждать продолжения не нужно. В кодировании это называется условием Фано, и задание 4 целиком на нём построено.

Обычно даны двоичные коды нескольких букв, и нужно подобрать кратчайший код для ещё одной буквы так, чтобы сообщения по-прежнему расшифровывались однозначно.

Условие Фано

Каждого из условий достаточно для однозначного декодирования. Если в задаче не сказано иначе, проверяют прямое условие.

Двоичное дерево кодов

Коды удобно представить ветвями дерева: 0 — влево, 1 — вправо. Занятое слово закрывает всё своё поддерево и весь путь к нему. Свободное слово — узел, который не лежит на пути к занятому и не находится под занятым.

Разбор: кратчайший код для новой буквы

А — 01, Б — 000, В — 11, Г — 100. Найдите кратчайший код для Д (если их несколько — с наименьшим числовым значением).

1. Длина 1: «0» — начало 01 и 000; «1» — начало 11 и 100. Не годятся.
2. Длина 2: 00 — начало 000; 01 и 11 заняты; 10 — начало 100. Не годятся.
3. Длина 3: 000 занят; 001 — не начало ни одного кода, и ни один код (0, 00) не является его началом. Годится.
4. Ответ: 001. (Подошло бы и 101, но $001<101$.)

Простыми словами

Рецепт надо выполнять дословно: «добавить соль после варки» — значит после, а не до. Задание 5 — такой же «рецепт» для чисел: алгоритм описан словами, и его нужно выполнить буквально, без догадок о «смысле».

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

Типичный алгоритм

Разбор: наименьшее N, при котором R больше 77

1. Оценка: $R\approx 4N$, значит, $N$ около $77:4\approx 19$. Начнём проверку немного раньше.
2. $N=18=10010_2$: единиц 2 → дописываем 0 → $100100$, единиц 2 → 0 → $1001000_2=72$. Мало.
3. $N=19=10011_2$: → $100111$ → $1001110_2=78>77$ ✓
4. Ответ: $N=19$. (Если бы спрашивали «наименьшее $R$, большее 77» — ответ 78.)

Надёжный способ — перебор

Не ищите закономерность наугад: прогоните алгоритм на числах подряд, начиная с наименьшего. Нужное значение обычно находится в первых десятках проверок; на компьютере это несколько строк.

for n in range(1, 1000):
    s = bin(n)[2:]                 # двоичная запись без '0b'
    for _ in range(2):
        s += str(s.count('1') % 2) # дописать остаток суммы цифр
    r = int(s, 2)                  # обратно в десятичную
    if r > 77:
        print(n, r)
        break

Простыми словами

Программу не обязательно понимать «целиком». Достаточно стать компьютером: выполнять строку за строкой и записывать, чему равна каждая переменная. Такой способ называется трассировкой.

Таблица трассировки из двух-трёх столбцов решает почти любое задание этого номера: в строке — один проход цикла, в столбцах — значения переменных после него.

Операции, которые встречаются чаще всего

Разбор: цикл while

n = 345
c = 0
while n > 0:
    c += n % 6
    n //= 6
print(c)

Программа выведет 10. Проверка через смысл: $345=1333_6$, сумма цифр $1+3+3+3=10$ ✓

Разбор: цикл for

s = 0
for i in range(1, 5):
    s = s * 2 + i
print(s)

1. $i=1$: $s=0\cdot 2+1=1$.
2. $i=2$: $s=1\cdot 2+2=4$.
3. $i=3$: $s=4\cdot 2+3=11$.
4. $i=4$: $s=11\cdot 2+4=26$. Значения 5 нет — range(1, 5) его не включает. Ответ: 26.

Простыми словами

Картинка на экране — мозаика из точек-пикселей, у каждой свой цвет. Звук в компьютере — длинный ряд замеров громкости. И в том, и в другом случае объём — это «сколько штук × сколько бит на штуку».

В задании 7 считают размер файла с рисунком или звукозаписью без сжатия.

Изображение

где $W$ и $H$ — ширина и высота в пикселях, $k$ — глубина цвета: сколько бит отводится на цвет одного пикселя.

Глубина $k$ бит даёт $2^k$ цветов. Наоборот, для $N$ цветов нужно наименьшее $k$, при котором $2^k\ge N$: для 100 цветов $k=7$ ($2^7=128$), для 256 цветов $k=8$.

Звук

где $f$ — частота дискретизации (замеров в секунду, Гц; 16 кГц = 16 000 Гц), $i$ — разрядность (бит на один замер), $c$ — число каналов (моно — 1, стерео — 2, квадро — 4), $t$ — время в секундах.

Единицы и ловушки

Простыми словами

Кодовый замок с 3 колёсиками по 10 цифр открывается одной из $10\cdot 10\cdot 10=1000$ комбинаций. Задание 8 о том же: сколько разных «слов» можно составить из данных букв, если на них наложены условия.

«Слово» здесь — любая последовательность букв, не обязательно осмысленная. Порядок букв важен: РСТ и ТСР — разные слова.

Ячейки: сколько вариантов на каждое место

Тот же ответ даёт вычитание: все слова минус начинающиеся с Т — $3^5-3^4=243-81=162$.

Типовые надстройки

Запрет соседства

«Нет двух К подряд» считают по шагам. Пусть $a_k$ — число допустимых слов длины $k$, оканчивающихся на К, $b_k$ — на любую другую из $n-1$ букв.

from itertools import product
cnt = 0
for w in product('КЛМНП', repeat=6):
    if 'КК' not in ''.join(w):
        cnt += 1
print(cnt)   # 13056

Простыми словами

Почтовый адрес «г. Москва, ул. Ленина, д. 5, кв. 12» делится на две части: дом (общий для всех жильцов) и квартира. IP-адрес устроен так же: начало — адрес сети («дом»), конец — номер узла («квартира»). Где проходит граница, показывает маска.

Главные формулы

Номер узла — то, что «отрезала» маска: $\text{IP}\&\neg \text{маска}$.

Из всех $K$ адресов сети два служебные: адрес самой сети (все биты узла — нули) и широковещательный (все биты узла — единицы). Узлам их не выдают.

Других значений у байта маски, кроме этих и 0, не бывает.

Разбор: адрес сети

IP 192.168.157.40, маска 255.255.240.0.

1. Байты, где маска 255, переходят в адрес сети без изменений: 192.168. Где маска 0 — обнуляются: последний байт 0.
2. В двоичный вид переводим только «смешанный» байт — третий: $157=10011101_2$, $240=11110000_2$.
3. Поразрядное «И» даёт $10010000_2=144$. Адрес сети: 192.168.144.0.

Разбор: сколько адресов

Обратные задачи: маска по условию

Простыми словами

Чемодан берут целиком, даже если вещей на полчемодана. Так и с памятью: под каждую запись отводится целое число байт, и неполный байт всё равно занимается полностью. Именно здесь в задании 11 чаще всего и ошибаются.

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

Бит на символ

Для 26 букв — 5 бит, для 30 — 5, для 33 — 6, для 64 — 6, для 26 букв и 10 цифр ($N=36$) — 6 бит.

Порядок вычислений

1. Бит на символ: наименьшее $i$, при котором $2^i\ge N$.
2. Бит на запись: число символов × $i$.
3. Байт на запись: делим на 8 и округляем вверх.
4. Всего: байт на запись × число записей.

Обратные задачи

Простыми словами

Функция «Найти и заменить» в текстовом редакторе, но с одним отличием: Редактор меняет только первое найденное вхождение, а потом снова ищет с начала строки. Из-за этого цепочки «переезжают» по строке, и результат часто неочевиден.

Как читать программу

НАЧАЛО
ПОКА нашлось (111)
    заменить (111, 2)
    заменить (222, 1)
КОНЕЦ ПОКА
КОНЕЦ

Тело цикла выполняется, пока условие истинно. Внутри обе команды выполняются по очереди на каждом проходе, даже если вторая ничего не находит.

Разбор: строка из 100 единиц

Ручная трассировка ста символов долгая. Есть два надёжных пути.

s = '1' * 100
while '111' in s:
    s = s.replace('111', '2', 1)   # 1 — только первое вхождение
    s = s.replace('222', '1', 1)
print(s)   # 21

Рабочий метод и ловушки

Простыми словами

Исполнитель умеет две вещи — прибавить и умножить. Сколько разных программ переведут число A в число B? Перебирать программы долго; гораздо быстрее идти по числам от A к B и для каждого записывать, сколькими способами до него можно добраться.

Это тот же приём, что и подсчёт путей в графе: числа — вершины, команды — стрелки.

Главная формула

где $R(v)$ — число программ из A в $v$, $d$ — шаг команды «прибавь», $m$ — множитель команды «умножь». Второе слагаемое берётся, только если $v$ делится на $m$ нацело и частное не меньше A. База: $R(A)=1$; для чисел меньше A — $0$.

Почему так: последняя команда программы — либо «прибавь» (тогда до неё было $v-d$), либо «умножь» (тогда было $v/m$). Эти случаи не пересекаются, поэтому их количества складываются.

Разбор: из 2 в 12

Команды: 1) прибавь 1, 2) умножь на 2. Сколько программ переводят 2 в 12?

1. $R(2)=1$, $R(3)=R(2)=1$ (3 нечётное — только +1).
2. $R(4)=R(3)+R(2)=2$; $R(5)=2$; $R(6)=R(5)+R(3)=3$; $R(7)=3$.
3. $R(8)=R(7)+R(4)=5$; $R(9)=5$; $R(10)=R(9)+R(5)=7$; $R(11)=7$.
4. $R(12)=R(11)+R(6)=7+3=10$. Ответ: 10.

Обязательные и запрещённые числа

def f(a, b):
    if a > b: return 0
    if a == b: return 1
    return f(a + 1, b) + f(a * 2, b)

print(f(2, 12))             # 10
print(f(2, 6) * f(6, 12))   # через 6: 6

Простыми словами

В десятичной системе $10^5=100000$ — единица и пять нулей, а $10^5-1=99999$ — пять девяток. В любой системе с основанием $b$ происходит то же самое. На этом наблюдении строится всё задание 14: огромные числа вроде $8^{15}$ не надо вычислять — достаточно понять, как выглядит их запись.

где $b$ — основание, $a_i$ — цифры от $0$ до $b-1$. Перевод из десятичной: делить на $b$, выписывая остатки, и читать их снизу вверх.

Три главных факта

Разбор заданий

x = 8**15 + 4**8 - 26
print(hex(x)[2:].count('0'))   # 7
# для другой системы — делим в цикле:
n, b, zeros = x, 3, 0
while n > 0:
    zeros += (n % b == 0)
    n //= b
print(zeros)

Ловушки

Простыми словами

Правило «если идёт дождь, я беру зонт» нарушается только в одном случае: дождь идёт, а зонта нет. Задание 15 — подобрать такой параметр $A$, чтобы формула ни при одном $x$ не оказалась нарушенной.

Задачи с отрезками

$P=[6;17]$, $Q=[28;41]$. Наибольшая длина отрезка $A$, при которой $((x\in A)\to (x\in P))\vee (x\in Q)$ тождественно истинна?

1. Формула ложна, когда $x\in A$, $x\notin P$ и $x\notin Q$.
2. Чтобы такого $x$ не было, всё, что попало в $A$, должно лежать в $P$ или в $Q$: $A\subseteq P\cup Q$.
3. $P$ и $Q$ не пересекаются, а $A$ — один отрезок, поэтому он целиком внутри $P$ (длина $17-6=11$) или внутри $Q$ (длина $41-28=13$). Ответ: 13.

Задачи с делимостью (ДЕЛ)

ДЕЛ$(n,m)$ — «$n$ делится на $m$ без остатка». Наименьшее $A$, при котором ДЕЛ$(x,A)\to ($ДЕЛ$(x,30)\vee$ ДЕЛ$(x,14))$ тождественно истинна?

1. Ложна, когда $x$ кратно $A$, но не кратно ни 30, ни 14.
2. Возьмём $x=A$: тогда $A$ само обязано делиться на 30 или на 14.
3. Наименьшее такое $A$ — 14. Проверка: любое кратное 14 делится на 14 ✓

Поразрядная конъюнкция

$x\&A$ — поразрядное «И» двоичных записей. $x\&A\ne 0$ — «у $x$ есть хотя бы один общий единичный бит с $A$».

def F(x, A):
    return (not (x & 29 != 0)) or (x & 12 != 0) or (x & A != 0)

for A in range(1, 1000):
    if all(F(x, A) for x in range(1, 1024)):
        print(A)   # 17
        break

Простыми словами

Двое по очереди добавляют камни в кучу. Кто первым доведёт кучу до порога — победил. Задания 19–21 — одна игра и три вопроса про неё. В задании 19 нужно понять самое простое: из каких позиций можно выиграть одним ходом и из каких любой ход отдаёт победу сопернику.

Дальше разбираем пример: ходы +1 и ×2, игра кончается при $\ge 29$ камнях, $1\le S\le 28$.

Позиции разбираются от конца

Типовые вопросы задания 19

Программа и ловушки

N = 29
def moves(s): return [s + 1, s * 2]

W1 = [s for s in range(1, N) if any(m >= N for m in moves(s))]
L1 = [s for s in range(1, N) if s not in W1
      and all(m in W1 for m in moves(s))]
print(W1, L1)   # 15..28, [14]

Простыми словами

Стратегия — это не один удачный ход, а готовый ответ на любой ход соперника. Как в крестиках-ноликах: знаешь, что делать, как бы ни сыграл другой. Задание 20 спрашивает, при каких $S$ у Пети есть такая стратегия, приводящая к победе вторым ходом.

Игра та же, что в задании 19. Пример: ходы +1 и ×2, порог $29$, $1\le S\le 28$. Уже известно: W1 — $S$ от 15 до 28 (победа одним ходом), L1 — $S=14$ (любой ход отдаёт победу).

Слои позиций

Слово «каждый» — ключевое: достаточно одного спасительного ответа соперника, и стратегия разрушена.

Разбор: два наименьших S

Найдите два наименьших значения $S$, при которых у Пети есть стратегия выиграть вторым ходом, но нет стратегии выиграть первым.

1. Ищем ходы в L1 = {14}: $S+1=14\Rightarrow S=13$; $2S=14\Rightarrow S=7$.
2. Проверяем, что это не W1: из 7 и 13 одним ходом до 29 не дойти ✓
3. Проверяем стратегию для $S=13$: Петя — 14; Ваня — 15 или 28; Петя удваивает: $30$ или $56$, оба $\ge 29$ ✓
4. Ответ: 7 13 (в порядке возрастания, через пробел).

Программа и ловушки

N = 29
def moves(s): return [s + 1, s * 2]
W1 = {s for s in range(1, N) if any(m >= N for m in moves(s))}
L1 = {s for s in range(1, N) if s not in W1 and all(m in W1 for m in moves(s))}
W2 = [s for s in range(1, N) if s not in W1 and any(m in L1 for m in moves(s))]
print(W2)   # [7, 13]

Простыми словами

Задание 21 — самое длинное из игровой тройки. Нужно рассмотреть все ходы Пети и для каждого — лучший ответ Вани, на две пары ходов вперёд. Ветвей немного (обычно 4–8), и ошибаются не от сложности, а от пропущенной ветки.

Пример тот же: ходы +1 и ×2, порог 29. Из заданий 19–20: W1 — $S$ от 15 до 28, L1 — 14, W2 — 7 и 13.

Что значит формулировка

«У Вани есть стратегия, позволяющая выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая позволит ему гарантированно выиграть первым ходом». Это два условия одновременно:

Дерево игры для S = 12

1. Петя: 12 → 24. Ваня удваивает: 48 ≥ 29 — победа первым ходом.
2. Петя: 12 → 13. Ваня не может выиграть сразу ($26<29$), поэтому ходит +1 → 14 (L1).
3. Из 14 Петя может сделать 15 или 28 — обе позиции W1, Ваня выигрывает вторым ходом.
4. Условие 1 выполнено (выигрыш при любом ходе), условие 2 тоже (после 13 сразу не выиграть). Ответ: 12.

Таблица разбора и программа

Удобная схема — таблица из четырёх столбцов: позиция, ход Пети, ответ Вани, итог. Кандидатов проверяйте снизу вверх; если подходящих несколько, а спрашивают наименьшее — берите первое.

N = 29
def moves(s): return [s + 1, s * 2]
def win(s, k):          # игрок, который ходит из s, выигрывает не позднее k-го хода
    if k == 0: return False
    return any(m >= N or lose(m, k - 1) for m in moves(s))
def lose(s, k):         # каждый ход из s ведёт в позицию, выигрышную для соперника за k
    return all(m < N and win(m, k) for m in moves(s))

print([s for s in range(1, N) if lose(s, 2) and not lose(s, 1)])   # [12]

Простыми словами

Схема дорог с односторонним движением. Сколько разных маршрутов из А в И? Какой из них самый короткий? Обе задачи решаются одним движением по схеме слева направо: для каждого пункта записываем число — сумму (для числа путей) или минимум (для длины пути).

Количество путей

где $N_X$ — число путей из начальной вершины в $X$. В начальную вершину — один «пустой» путь: $N_{А}=1$. Считать нужно по порядку, чтобы к моменту обработки вершины все её предшественники были уже посчитаны.

1. $N_{Б}=N_{В}=N_{Г}=1$ (в них ведёт только А).
2. $N_{Д}=N_{Б}+N_{В}=2$; $N_{Е}=N_{В}+N_{Г}+N_{Д}=1+1+2=4$.
3. $N_{Ж}=N_{Д}+N_{Е}=6$; $N_{З}=N_{Е}=4$; $N_{И}=6+4=10$.

Через вершину и в обход

Кратчайший путь

То же движение по вершинам, но вместо суммы — минимум: