Перейти к содержимому
ЕГЭ 2027 · 24 разделов

Формулы и теория для ЕГЭ по информатике

2026/2027 учебный год. Опорные формулы и правила по заданиям КЕГЭ: справочных материалов на экзамене не выдают. Разбор с решением на Python — на страницах заданий.

Графы и таблица расстояний

В задании 1 сопоставляют вершины графа с номерами пунктов в таблице: нумерация в таблице не связана с буквами на схеме.

Свойства

  • Степень вершины — число рёбер из неё; в таблице — число заполненных клеток строки
  • Сумма степеней всех вершин равна удвоенному числу рёбер
  • Таблица неориентированного графа симметрична относительно главной диагонали
  • Сопоставление начинают с вершин единственной степени, остальные различают по соседям

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

В задании 2 восстанавливают столбцы таблицы истинности, в 15 ищут параметр, при котором выражение истинно при любом x. В КИМ конъюнкцию пишут /\ или &, дизъюнкцию — \/ или |.

Операции

ЗаписьОперацияИстинно, когдаPython
¬Aотрицание, НЕA = 0not a
A ∧ Bконъюнкция, ИA = 1 и B = 1a and b
A ∨ Bдизъюнкция, ИЛИхотя бы одно равно 1a or b
A → Bимпликациякроме A = 1, B = 0a <= b
A ≡ BтождествоA и B совпадаютa == b

Приоритет и таблица истинности

  • Порядок: ¬, затем ∧, ∨, →, ≡; ¬A ∧ B ∨ C ∧ D = ((¬A) ∧ B) ∨ (C ∧ D)
  • У выражения от n переменных 2n строк таблицы истинности

Законы

  • A → B = ¬A ∨ B
  • A ≡ B = (A ∧ B) ∨ (¬A ∧ ¬B)
  • Законы де Моргана: ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B
  • Двойное отрицание: ¬¬A = A
  • Поглощение: A ∨ A ∧ B = A, A ∧ (A ∨ B) = A
  • Распределительный закон: A ∧ (B ∨ C) = A ∧ B ∨ A ∧ C
  • A ∨ ¬A = 1, A ∧ ¬A = 0

Предикаты задания 15 на Python

В условииPython
ДЕЛ(x, A)x % A == 0
x ∈ [a; b]a <= x <= b
x & A (поразрядная конъюнкция)x & A
истинно при любом xall(f(x) for x in range(1, 1000))

Базы данных и электронные таблицы

В задании 3 база из нескольких таблиц лежит в файле: нужные поля подтягивают по ключу и считают итог по условиям.

Связи таблиц

  • Ключ (ID) однозначно определяет строку таблицы-справочника
  • Связь «один ко многим»: ключ справочника повторяется в главной таблице, например ID магазина в каждой операции

Функции таблиц

ФункцияЧто делает
=ВПР(ключ; диапазон; номер_столбца; 0)подставляет поле из справочника по ключу; 0 — точное совпадение
=СУММЕСЛИМН(сумма; диапазон1; условие1; …)сумма по строкам, где выполнены все условия
=СЧЁТЕСЛИМН(диапазон1; условие1; …)число таких строк
=ЕСЛИ(условие; да; нет)значение по условию, например знак операции

Кодирование и условие Фано

В задании 4 подбирают недостающие кодовые слова так, чтобы код остался однозначно декодируемым, а сообщение — самым коротким.

Определения

  • Условие Фано: никакое кодовое слово не является началом другого — такой код расшифровывается однозначно
  • Обратное условие Фано: никакое кодовое слово не является концом другого — тоже однозначная расшифровка
  • Равномерный код для N букв: у всех слов длина ⌈log2N⌉ бит

Как подбирать слова

  • Кодовые слова — листья двоичного дерева: у занятого слова продолжений нет
  • Свободное слово — вершина дерева, у которой нет занятых предков и потомков
  • Для кода Фано с длинами l1, …, ln: 2−l1 + … + 2−ln ≤ 1; сумма равна 1 — свободных слов не осталось
  • Сообщение короче, когда частым буквам достаются короткие слова

Системы счисления

Задание 5 работает с двоичной записью числа, задание 14 — с записью в системе с основанием до 36 и делимостью.

Запись числа

  • Развёрнутая форма: (an…a1a0)q = an · qn + … + a1 · q + a0
  • Цифры системы с основанием q — от 0 до q − 1; после 9 идут буквы: A = 10, B = 11, …
  • Из десятичной — делить на q и записывать остатки снизу вверх
  • Двоичная ↔ восьмеричная — по три бита, ↔ шестнадцатеричная — по четыре

Полезные факты

  • qn в системе с основанием q — единица и n нулей; 2n − 1 = 11…12 (n единиц)
  • Чётность числа — последняя двоичная цифра; дописать 0 справа — умножить на 2
  • Число делится на q − 1, когда сумма его цифр в системе с основанием q делится на q − 1

Python

ВыражениеЧто даёт
bin(n)[2:]двоичная запись числа n строкой
oct(n)[2:], hex(n)[2:]восьмеричная и шестнадцатеричная запись
int(s, q)число из строки s в системе с основанием q от 2 до 36
bin(n).count('1')число единиц в двоичной записи
n % q, n // qпоследняя цифра в системе q и число без неё

Числа от 0 до 15

102816
0000000
1000111
2001022
3001133
4010044
5010155
6011066
7011177
81000108
91001119
10101012A
11101113B
12110014C
13110115D
14111016E
15111117F

Черепаха и точки с целыми координатами

В задании 6 Черепаха рисует фигуры, и нужно сосчитать точки с целыми координатами внутри фигуры, их пересечения или объединения. Внимательно читайте, считаются ли точки на границе.

Как читать алгоритм

  • В начале голова смотрит вверх, вдоль оси y; после «Направо 90» Черепаха идёт вправо, вдоль оси x
  • Повтори k [Вперёд a Направо 90 Вперёд b Направо 90] при k ≥ 2 — один и тот же прямоугольник a × b: обход замыкается за два повтора
  • Правильный n-угольник: Повтори n [Вперёд a Направо 360n]
  • Замкнутый обход поворачивает Черепаху в сумме на 360°
  • При поднятом хвосте Черепаха только меняет положение: новая фигура начинается из сдвинутой точки

Точки с целыми координатами

  • Прямоугольник a × b со сторонами вдоль осей и вершинами в целых точках: строго внутри (a − 1)(b − 1) точек, вместе с границей (a + 1)(b + 1)
  • Пересечение прямоугольников [x1; x2] × [y1; y2] и [x3; x4] × [y3; y4] — прямоугольник [max(x1, x3); min(x2, x4)] × [max(y1, y3); min(y2, y4)]
  • Объединение: точки первой фигуры + точки второй − точки пересечения
  • Формула Пика для многоугольника с вершинами в целых точках: S = В + Г2 − 1, где В — точки внутри, Г — на границе

Черепаха на Python (модуль turtle)

PythonКоманда
left(90)голова вверх, как у Черепахи КИМ (в turtle она сначала смотрит вправо)
forward(n), back(n)Вперёд n, Назад n
right(m), left(m)Направо m, Налево m
up(), down()Поднять хвост, Опустить хвост
for _ in range(k): …Повтори k […]
tracer(0), update()рисовать сразу, без анимации

Единицы измерения информации

Ответ в заданиях 7 и 11 просят в байтах, Кбайт или Мбайт. В ЕГЭ приставки двоичные: Кбайт — это 1024 байта, а не 1000.

Единицы

ЕдиницаСколькоСтепень двойки
1 байт8 бит23 бит
1 Кбайт1024 байта210 байт = 213 бит
1 Мбайт1024 Кбайт220 байт = 223 бит
1 Гбайт1024 Мбайт230 байт
1 Кбит1024 бита210 бит

Степени двойки

  • 201
  • 212
  • 224
  • 238
  • 2416
  • 2532
  • 2664
  • 27128
  • 28256
  • 29512
  • 2101 024
  • 2112 048
  • 2124 096
  • 2138 192
  • 21416 384
  • 21532 768
  • 21665 536
  • 2201 048 576
  • 2301 073 741 824

Как переводить

  • Из бит в байты — разделить на 8; из байт в Кбайт — на 1024 = 210
  • Удобно считать степенями: 32 000 Гц · 16 бит = 28 · 125 · 24 бит
  • «Наименьшее число Кбайт» — округление вверх, «не более N Кбайт» — сравнение с N · 210 байт

Объём изображения и звука

В задании 7 считают объём растрового рисунка или звукового файла, иногда — время передачи по каналу.

Изображение

  • I = W · H · i, где W × H — размер в пикселях, i — глубина цвета в битах
  • Число цветов в палитре: N = 2i, глубина цвета: i = ⌈log2N⌉

Звук

  • I = f · i · k · t, где f — частота дискретизации (Гц), i — глубина кодирования (бит), k — число каналов, t — время (с)
  • Моно — k = 1, стерео — k = 2, квадро — k = 4

Передача и сжатие

  • Объём, переданный по каналу: I = v · t, где v — скорость в бит/с
  • Файл сжат на p %: новый объём I · (1 − p100)

Комбинаторика: слова и номера

В задании 8 считают слова из заданных букв или ищут номер слова в алфавитном списке.

Формулы

  • Слова длины k из N букв, буквы повторяются: Nk
  • Перестановки n разных букв: n! = 1 · 2 · … · n
  • Слова длины k из n букв без повторов: n · (n − 1) · … · (n − k + 1)
  • Перестановки с повторами: n!n1! · n2! · … · nm!
  • Алфавитный список слов из N букв — это числа в N-ичной системе: буквы по алфавиту — цифры 0, …, N − 1, номер слова = значение + 1

Python

ВыражениеЧто даёт
product('АКЦ', repeat=k)все слова длины k; буквы в строке — по алфавиту, тогда и слова по алфавиту
permutations('АКЦ')все перестановки букв
enumerate(…, 1)номер слова в списке с единицы

Электронные таблицы: функции и условия по строке

В задании 9 в файле тысячи строк чисел: считают строки, где одновременно выполнены два условия — о повторах, о среднем, о сумме или порядке чисел.

Функции

ФункцияЧто делает
=СЧЁТЕСЛИ(A1:E1; A1)сколько раз число из A1 встречается в строке
=МАКС(A1:E1), =МИН(A1:E1)наибольшее и наименьшее число строки
=НАИБОЛЬШИЙ(A1:E1; k)k-е по величине число; =НАИМЕНЬШИЙ — k-е с начала
=СУММ(A1:E1), =СРЗНАЧ(A1:E1)сумма и среднее арифметическое
=ОСТАТ(A1; 2)остаток от деления, например проверка чётности
=И(усл1; усл2), =ИЛИ(усл1; усл2)оба условия, хотя бы одно
=ЕСЛИ(И(…); 1; 0)1 у подходящей строки; сумма столбца — ответ

Ссылки при копировании формулы

  • A1 — относительная ссылка: при копировании меняются и столбец, и строка
  • $A$1 — абсолютная: не меняется; $A1 — закреплён столбец, A$1 — строка

Те же условия на Python (r — список чисел строки)

PythonУсловие
len(set(r)) == len(r)все числа строки различны
c = [r.count(x) for x in r]сколько раз встречается каждое число строки
c.count(2) == 2 and c.count(1) == len(r) - 2ровно одно число повторяется дважды, остальные — по разу
sorted(r)числа по возрастанию: s[-1] — наибольшее, s[0] — наименьшее
sum(r) / len(r)среднее арифметическое
r = list(map(int, line.split(',')))строка CSV-копии файла — список чисел

IP-адрес и маска подсети

В задании 10 по адресу узла и маске находят адрес сети, число адресов в ней или подходящую маску. Адрес сети — поразрядная конъюнкция адреса и маски.

Определения

  • IP-адрес — 32 бита, записывают четырьмя октетами от 0 до 255: 192.168.159.86
  • Маска — сначала k единиц, затем 32 − k нулей; короткая запись — /k
  • Адрес сети = IP-адрес ∧ маска поразрядно; октет маски 255 оставляет октет адреса, 0 — обнуляет
  • Широковещательный адрес: в части узла все единицы
  • Адресов в сети: 232 − k; узлам — 232 − k − 2 (без адреса сети и широковещательного)
  • Два узла в одной сети, когда у них совпадает адрес сети

Октет маски по числу единиц

  • 0 единиц0
  • 1128
  • 2192
  • 3224
  • 4240
  • 5248
  • 6252
  • 7254
  • 8255

Python (модуль ipaddress)

ВыражениеЧто даёт
net = ip_network(ip + '/' + mask, strict=False)сеть узла: ip = '192.168.159.86', mask = '255.255.252.0'
net.network_address, net.broadcast_addressадрес сети и широковещательный
net.num_addresses, net.prefixlenчисло адресов и число единиц маски k
ip_address(ip) in netлежит ли адрес в сети
a & mпоразрядная конъюнкция октетов (или целых 32-битных адресов)

Формула Хартли и объём сообщения

Задание 11: символы кодируют одинаковым и наименьшим числом бит, а каждый объект — пароль, номер — хранят целым числом байт.

Формулы

  • N = 2i: i бит различают N вариантов
  • Наименьшее число бит на символ алфавита из N символов: i = ⌈log2N⌉
  • Объём сообщения из K символов: I = K · i бит
  • Объект хранится целым числом байт: ⌈K · i8⌉ байт
  • Наибольшая мощность алфавита при i битах на символ: N = 2i

Обратная задача: известен объём

  • На один объект — не больше ⌊VM⌋ байт, где V — объём в байтах, M — число объектов
  • Бит на символ — не больше ⌊8 · байт на объектK⌋; округляем вниз, иначе объект не поместится

Исполнители: машина Тьюринга и Редактор

В задании 12 исполняют программу для исполнителя с фиксированным набором команд — машины Тьюринга (МТ) над лентой или Редактора над строкой — и ищут результат или исходные данные.

Машина Тьюринга

  • Программа — таблица: строки — состояния q0, q1, …, столбцы — символы на ленте
  • Команда «0, L, q3»: записать 0, сдвинуться влево и перейти в q3; R — вправо, S — стоп после команды
  • Сначала запись, потом сдвиг; пустая клетка таблицы — такая пара «символ — состояние» не встречается
  • Прибавить 1 к двоичному числу: идём справа, единицы меняем на нули до первого нуля, его — на 1
  • Ответ просят в десятичной системе: прочитайте ленту и переведите число

Редактор

  • заменить(v, w) — первое слева вхождение v меняется на w; если v нет, строка не меняется
  • нашлось(v) — истинно, если v есть в строке
  • ПОКА нашлось(v) … КОНЕЦ ПОКА — повторять, пока условие истинно

Python

PythonКоманда
s = s.replace(v, w, 1)заменить(v, w) — третий аргумент 1: только первое вхождение
v in sнашлось(v)
while '11' in s: …ПОКА нашлось(11)
tape = dict(enumerate(s))лента МТ: номер клетки → символ, пустые — tape.get(i, 'λ')

Число программ исполнителя

В задании 13 исполнитель с двумя-тремя командами переводит одно число в другое: считают программы, иногда с обязательным или запретным числом на траектории.

Динамика по числам

  • K(x) — число программ, переводящих исходное число a в x; K(a) = 1
  • K(x) — сумма K(y) по всем y, из которых x получается одной командой
  • Траектория обязана пройти через c: K(a → c) · K(c → b)
  • Траектория не должна содержать c: считаем K(c) = 0
  • Если команды только увеличивают число, считаем K по возрастанию от a до b

Python: рекурсия «от начала к концу»

СтрокаСмысл
def f(x, y):число программ из x в y
if x > y: return 0проскочили — программы нет (команды только увеличивают)
if x == y: return 1пришли — одна программа
return f(x + 1, y) + f(x * 2, y)сумма по командам; обязательное c — f(a, c) * f(c, b)

Рекуррентные функции

В задании 16 функция F(n) задана через свои значения при меньших n. Значения бывают огромными: выражение сначала упрощают, а считают программой с запоминанием.

Упрощение

  • F(n) = n · F(n − 1), F(1) = 1 — это n! = 1 · 2 · … · n
  • Тогда F(n)F(n − 1) = n, F(n)F(n − 2) = n · (n − 1): факториалы сокращают, а не вычисляют
  • F(n) = F(n − 1) + g(n): разность F(n) − F(n − 1) = g(n), F(n) − F(m) — сумма g(k) от m + 1 до n
  • Выписывают первые значения F и ищут закономерность — так проверяют упрощение

Python

ВыражениеЗачем
@lru_cache(None)запоминает уже посчитанные F(n) — из functools
sys.setrecursionlimit(10**6)глубокая рекурсия без RecursionError
for n in range(2, N + 1): F[n] = …счёт снизу вверх — без рекурсии вовсе
a // bцелочисленное деление: a / b у больших чисел даёт float и теряет точность

Обработка последовательности чисел

В задании 17 в файле около 10 000 целых чисел: считают пары или тройки соседних элементов с условием и находят наибольшую или наименьшую сумму.

Сколько пар и троек

  • Пар соседних элементов среди N чисел — N − 1, троек — N − 2
  • Всех пар (не обязательно соседних) — N · (N − 1)2
  • Последняя цифра отрицательного числа: |x| mod 10; в Python x % 10 для −13 даёт 7, а не 3
  • Двузначное число по модулю: 10 ≤ |x| ≤ 99

Python

ВыражениеЧто даёт
a = [int(x) for x in open('17.txt')]числа файла списком
for x, y in zip(a, a[1:]):все пары соседних; тройки — zip(a, a[1:], a[2:])
abs(x) % 10 == 3запись числа оканчивается на 3
max(a), min(x for x in a if x % 2)наибольшее и наименьшее с условием
cnt, best = 0, -10**9счётчик и максимум до цикла

Робот на клетчатом поле

В задании 18 Робот идёт по полю вправо и вниз и собирает монеты. Наибольшую и наименьшую сумму считают в электронной таблице одной формулой, протянутой на всё поле.

Динамика

  • S(i, j) — лучшая сумма, с которой Робот приходит в клетку (i, j); A(i, j) — монета в клетке
  • S(i, j) = A(i, j) + max(S(i − 1, j), S(i, j − 1)); для наименьшей суммы — min
  • Первая строка и первый столбец — накопленные суммы: прийти туда можно только одним путём
  • Стена между клетками — из этой соседки хода нет, берём только другую
  • Если конечных клеток несколько, ответ — наибольшее (наименьшее) S среди них

В таблице: поле в A1:T20, суммы — на втором поле

ЯчейкаФормула
V1=A1
W1 (первая строка)=V1+B1
V2 (первый столбец)=V1+A2
W2 и дальше=МАКС(W1;V2)+B2
W3, если над B3 стена=V3+B3 — сосед за стеной в формулу не входит

Теория игр: выигрышные позиции

Задания 19–21 — одна игра с кучами камней. Позиции делят на выигрышные и проигрышные, считая с конца — от позиций, где игра уже закончилась.

Определения

  • Позиция выигрышная, если из неё есть ход в проигрышную; проигрышная — если все ходы ведут в выигрышные
  • П1 — Петя выигрывает первым ходом: есть ход сразу в конец игры
  • В1 — Ваня выигрывает первым ходом при любом ходе Пети: после каждого хода Пети у Вани есть ход в конец игры
  • П2 — Петя выигрывает вторым ходом при любой игре Вани: есть ход в позицию В1, и сам Петя не выигрывает первым
  • В2 — Ваня выигрывает первым или вторым ходом: все ходы Пети ведут в П1 или П2, и хотя бы один — в П2

Что спрашивают

  • 19: «Ваня выиграл первым ходом» — у Пети есть хотя бы один неудачный ход, после которого Ваня выигрывает одним ходом
  • 20: стратегия Пети П2 — значения S по возрастанию
  • 21: у Вани стратегия В2, но не В1
  • Ход «удвоить» растёт быстрее: при поиске выигрыша сначала проверяют его

Python: рекурсия по числу ходов

СтрокаСмысл
def f(a, b, m):m — сколько ходов обоих игроков осталось; П1 — m = 1, В1 — 2, П2 — 3, В2 — 4
if a + b >= 133: return m % 2 == 0игра закончилась: последний ход сделал наш игрок
if m == 0: return Falseходы кончились, а игра — нет
h = [f(a + 4, b, m - 1), f(a * 2, b, m - 1), f(a, b + 4, m - 1), f(a, b * 2, m - 1)]все ходы из позиции
return any(h) if m % 2 else all(h)ходит наш игрок — хватит одного хода, соперник — проверяем все
f(17, s, 3) and not f(17, s, 1)20: П2, но не П1; для 21 — f(17, s, 4) and not f(17, s, 2)

Параллельные процессы

В задании 22 у процессов есть время выполнения и список процессов, результаты которых им нужны. Каждый процесс начинается как можно раньше.

Расписание

  • Независимый процесс (в таблице 0) начинается в момент 0
  • Начало процесса — наибольший конец среди процессов, от которых он зависит; конец = начало + время
  • Наименьшее время выполнения всех процессов — наибольший конец
  • Миллисекунды нумеруют с 1: процесс с началом s и временем d занимает мс с s + 1 по s + d
  • Процессов на t-й мс — число процессов с s < t ≤ s + d

Python

ВыражениеЧто даёт
deps = [int(x) for x in str(c).split(';')]список зависимостей из «3;25» или 7; 0 — нет зависимостей
end[p] = max(end[q] for q in deps) + t[p]конец процесса; считать в порядке, где зависимости уже готовы
sum(s < t <= s + d for s, d in runs)сколько процессов идёт на t-й мс

Пути в ориентированном графе

В задании 23 граф из файла ациклический: ищут кратчайший путь между вершинами или число путей. Обе задачи решает проход по вершинам в топологическом порядке.

Ациклический граф

  • Ациклический граф можно упорядочить так, что все рёбра ведут вперёд — это топологический порядок
  • Кратчайший путь: d(start) = 0, d(v) = min(d(u) + w(u, v)) по рёбрам u → v
  • Число путей: P(start) = 1, P(v) — сумма P(u) по рёбрам u → v
  • Путь через обязательную вершину c: путь start → c плюс путь c → finish
  • Длина пути — сумма весов его рёбер; «целая часть» — округление вниз

Любой граф с неотрицательными весами

  • Алгоритм Дейкстры: берём непосещённую вершину с наименьшим d и улучшаем d её соседей
  • Число вершин и рёбер в задании небольшое — до 200 строк файла

Python

ВыражениеЧто даёт
l, m, w = line.split()строка файла: из L в M ребро веса W; веса — float(w)
TopologicalSorter(pred)вершины в топологическом порядке — .static_order(); pred: вершина → её предшественники (graphlib)
d = defaultdict(lambda: float('inf'))расстояния, пока неизвестные
heappush(q, (d, v)), heappop(q)очередь Дейкстры (heapq)
int(d[100])целая часть длины пути

Обработка строки из файла

В задании 24 файл — одна строка в миллионы символов: ищут самую длинную подстроку с условием или считают такие подстроки. Нужен один проход по строке.

Приёмы

  • Один проход: длина текущей цепочки растёт, пока условие выполнено; нарушение — цепочка начинается заново
  • Начало новой цепочки — не всегда следующий символ: иногда часть старой цепочки остаётся началом новой
  • Два указателя: правая граница идёт вперёд, левая сдвигается, пока окно не станет допустимым
  • Без символа c: самая длинная подстрока — наибольшая часть строки, разрезанной по c

Python

ВыражениеЧто даёт
s = open('24.txt').readline()строка файла; .strip() убирает перевод строки в конце
max(map(len, s.split('X')))самая длинная подстрока без X
re.finditer(шаблон, s)все непересекающиеся совпадения регулярного выражения
max(len(m.group()) for m in …)длина самого длинного совпадения
s.count('AB')число непересекающихся вхождений

Делители, простые числа, маски чисел

В задании 25 перебирают числа и ищут те, у которых делители с условием, или числа по маске. Перебор должен укладываться в секунды — делители ищут до корня.

Делители

  • Если d делит n, то и nd делит n: делители ищут до √n, парами d и n // d
  • Простое число — ровно два делителя: 1 и само число
  • n = p1a1 · … · pkak: число делителей (a1 + 1) · … · (ak + 1)
  • Нечётное число делителей только у полных квадратов
  • Произведение двух простых n = p · q, p ≤ q: меньший множитель p ≤ √n

Маска числа

  • «?» — ровно одна цифра, «*» — любая последовательность цифр, в том числе пустая
  • Число по маске, кратное k, ищут перебором кратных: от наименьшего кратного шагом k

Python

ВыражениеЧто даёт
for d in range(2, isqrt(n) + 1):делители до корня (math.isqrt — точный целый корень)
if n % d == 0: divs |= {d, n // d}оба делителя пары
fnmatch(str(n), '3?12?14*5')подходит ли число под маску (модуль fnmatch)
'16' in str(p), str(p).count('16') == 1запись числа содержит 16 (ровно один раз)

Сортировка и жадный выбор

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

Приёмы

  • Наибольшее число объектов в объёме V: сортируем по возрастанию и берём, пока помещаются
  • Наибольший последний объект при том же числе: заменяем последний взятый на самый большой, который ещё помещается
  • Время «чч:мм:сс» в секундах: ч · 3600 + м · 60 + с; строки этого формата сравниваются и как текст
  • Накопление с очисткой: когда следующий объём не помещается, текущая сумма уходит в «копию», счёт начинается с нуля

Python

ВыражениеЧто даёт
n, k = map(int, f.readline().split())первая строка файла
a.sort(key=lambda r: r[1], reverse=True)сортировка по второму полю, по убыванию
total = defaultdict(int); total[c] += sсумма по ключу (collections)
max(total, key=total.get)ключ с наибольшей суммой
sum(sorted(copies)[-2:])сумма двух наибольших

Кластеры и центры

В задании 27 точки или частицы из файла делят на кластеры и находят центры. Центр — элемент кластера с наименьшей суммой расстояний до остальных.

Формулы

  • Расстояние на плоскости: √((x1 − x2)2 + (y1 − y2)2)
  • Кинетическая энергия: E = m2 · v2, где v2 = Vx2 + Vy2
  • Центр кластера: элемент c, у которого сумма |Ec − Ei| (или расстояний) по кластеру наименьшая
  • Кластеры по одному значению с порогом R: сортируем значения, новый кластер — там, где соседние различаются больше чем на R
  • Ответ «× 10 000, целая часть»: int(Q · 10 000)

Python

ВыражениеЧто даёт
float(x.replace(',', '.'))число с десятичной запятой из файла
dist(p, q)расстояние между точками (math.dist)
min(cl, key=lambda c: sum(dist(c, p) for p in cl))центр кластера
sum(x for x, y in centers) / len(centers)среднее координат центров

Частые вопросы

Выдают ли на ЕГЭ по информатике справочные материалы?

Нет. В начале КИМ есть только соглашения: как обозначают логические операции, в каком порядке их выполняют и что Кбайт и Мбайт — степени двойки. Формулы объёма, Хартли и законы логики нужно знать самому.

Кбайт — это 1000 или 1024 байта?

1024. В КИМ ЕГЭ Кбайт и Мбайт понимают «в традиционном для информатики смысле»: 1 Кбайт = 2¹⁰ байт, 1 Мбайт = 2²⁰ байт.

Где разбор заданий с решением?

На страницах заданий: там все типы задания, решение на Python, которое можно запустить в браузере, и тренажёр. Здесь — только формулы и правила, которые эти решения используют.