Разборы заданий ЕГЭ и ОГЭ по информатике
Для каждого номера: что от тебя хотят, разбор реальной задачи из ЕГЭ, код на Python, который её решает, типичные ошибки и лайфхаки. Код из любого разбора открывается в песочнице вместе с задачей из базы.
ЕГЭ по информатике: задания 1–27
Задание №1
Графы и таблицы: кто есть кто на карте
Одну и ту же карту дорог нарисовали дважды: схемой с буквами и таблицей с номерами П1–П7
Задание №2
Таблицы истинности: какой столбец какая переменная
Дана логическая функция и обрезок её таблицы истинности, где не подписано, какой столбец какой переменной принадлежит
Задание №3
Базы данных: три таблицы и один ответ
Файл с тремя связанными таблицами: движение товаров, справочник товаров и справочник магазинов
Задание №4
Условие Фано: код без путаницы
Буквам назначены двоичные коды, часть кодов известна
Задание №5
Автомат: из числа N делаем число R
Автомат берёт число N и по шагам строит из него число R, обычно работая с двоичной записью
Задание №6
Черепаха рисует, а мы считаем точки
Черепаха выполняет программу и рисует замкнутую фигуру (или две)
Задание №7
Размер картинки и звука: считаем объём
Рассчитать, сколько памяти занимает картинка или звук при заданных параметрах, или найти параметр по заданному объёму
Задание №8
Комбинаторика, перестановки и слова по порядку
Подсчёт количества допустимых слов или определение номера слова в алфавитном списке с ограничениями на повторы и соседние буквы
Задание №9
Таблица с числами: считаем подходящие строки
Дан файл, где в каждой строке по несколько чисел
Задание №10
IP-адреса и маски: сеть, хосты, широковещание
Есть IP-адреса и маска сети
Задание №11
Сколько байт нужно на объект: считаем память
В системе хранятся объекты: коды, пароли, блоки данных
Задание №12
Машина Тьюринга: пишем свой симулятор
На ленте записано двоичное число, головка стоит рядом, программа задана таблицей
Задание №13
Калькулятор: считаем программы
У Калькулятора есть несколько команд («прибавить 1», «умножить на 2»...)
Задание №14
Системы счисления: огромные числа и неизвестные цифры
Два типа: посчитать, сколько каких цифр в записи огромного числа, или подобрать неизвестную цифру x, чтобы выполнялось условие
Задание №15
Подбираем параметр A, чтобы формула была всегда истинной
Дана формула с параметром A и переменной x
Задание №16
Рекурсивные функции: когда перебор не влезает
Функция задана рекуррентным соотношением
Задание №17
Обработка числовой последовательности из файла
Одно из самых надежных и простых заданий на 1 первичный балл
Задание №18
Динамическое программирование в таблицах (Робот-сборщик)
Робот перемещается из левой верхней клетки (A1) в правую нижнюю клетку поля NxN, двигаясь только ВПРАВО и ВНИЗ
Задание №19
Задания №19–21. Игра с камнями: код Кабанова
Одна игра и три вопроса про начальное количество камней S
Задание №20
Задания №19–21. Игра с камнями: код Кабанова
Одна игра и три вопроса про начальное количество камней S
Задание №21
Задания №19–21. Игра с камнями: код Кабанова
Одна игра и три вопроса про начальное количество камней S
Задание №22
Многопоточные процессы и время выполнения
Определение минимального времени завершения всех процессов при заданных зависимостях между ними (ID предыдущих процессов).
Задание №23
Графы и алгоритмы
Чтение описания ориентированного взвешенного графа из текстового файла (например, 23-1.txt), поиск кратчайшего пути с ограничением на максимальное число рёбер и вычисление суммы но
Задание №24
Анализ символьных строк (до 5 000 000 символов)
В текстовом файле записана гигантская строка (до 5 000 000 знаков)
Задание №25
Обработка целочисленной информации (Маски и делители)
Поиск чисел по маске (символы `?` — ровно один, `*` — любое количество) или чисел с особыми свойствами делителей.
Задание №26
Жадные алгоритмы, сортировка и оптимизация
Одно из двух самых ценных заданий ЕГЭ (2 первичных балла!)
Задание №27
Анализ больших данных (Кластеризация / Префиксные суммы)
Финальное и самое престижное задание ЕГЭ (2 первичных балла)
ОГЭ по информатике: задания 1–15
ОГЭ №1
ОГЭ. Количественные параметры информационных объектов
Вычисление информационного объема символьного текста и нахождение длины удаленного слова с учетом обязательных знаков препинания (запятой и пробела).
ОГЭ №2
ОГЭ. Кодирование и декодирование сообщений
Дана кодовая таблица и зашифрованная строка
ОГЭ №3
ОГЭ. Значение логического выражения
Нахождение наименьшего или наибольшего целого числа X, для которого составное логическое высказывание истинно (или ложно).
ОГЭ №4
ОГЭ. Формальные описания реальных объектов (Графы)
Дана весовая матрица расстояний между населенными пунктами A, B, C, D, E, F
ОГЭ №5
ОГЭ. Простой линейный алгоритм для формального исполнителя
Исполнитель преобразует число на экране по программе из 5 команд (например, `11211`)
ОГЭ №6
ОГЭ. Программа с условным оператором
Программа получает на вход пару чисел (s, t)
ОГЭ №7
ОГЭ. Информационно-коммуникационные технологии (URL)
Составление последовательности цифр, кодирующей URL-адрес файла в сети Интернет по фрагментам.
ОГЭ №8
ОГЭ. Запросы для поисковых систем (Круги Эйлера)
Нахождение количества страниц, найденных поисковым сервером по запросу, с использованием формулы кругов Эйлера.
ОГЭ №9
ОГЭ. Анализ информации в виде схем (Количество путей)
Определение количества различных путей из начального пункта А в конечный пункт по ориентированному графу (со стрелками).
ОГЭ №10
ОГЭ. Сравнение чисел в разных системах счисления
Даны три числа в разных системах счисления (2, 8, 16)
ОГЭ №11
ОГЭ. Поиск информации в файлах и текстах
Поиск в тексте произведения имени героя, названия улицы или фамилии по фрагменту текста в архиве подкаталогов.
ОГЭ №12
ОГЭ. Количество файлов в подкаталогах
Подсчёт общего количества файлов определённого типа (расширения или размера) во всех подкаталогах заданного каталога.
ОГЭ №13
ОГЭ. Создание презентации (13.1) или форматирование текста (13.2)
Выполнение одного из двух заданий по выбору: презентация из 3 слайдов с жесткими критериями макета (13.1) или форматирование текста со шрифтом, абзацным отступом и таблицей (13.2).
ОГЭ №14
ОГЭ. Обработка больших массивов данных в электронных таблицах
Решение 3 вопросов по таблице из 1000 строк: два вопроса на формулы (СЧЁТЕСЛИ, СРЗНАЧЕСЛИ) и построение круговой диаграммы с числовыми подписями.
ОГЭ №15
2 ОГЭ. Короткая программа на Python
Написание короткой программы на Python для обработки последовательности целых чисел с условиями делимости (например, кратно 4 и оканчивается на 2).
Шпаргалка по Python
Python
Функция print() и вывод
Функция print() — главный инструмент вывода результатов, таблиц истинности и отладки алгоритмов в ЕГЭ/ОГЭ
Python
Ввод данных input() и приведение типов
Чтение данных из стандартного ввода и приведение типов — фундаментальный навык для ОГЭ (Задание 6, 15.2) и олимпиадного программирования.
Python
Строки, срезы и методы str
Работа со строками — ядро заданий №12 (Исполнитель Редактор), №24 (Анализ символьных строк) и №8 ЕГЭ
Python
Списки, кортежи и list comprehension
Списки — основная структура данных для обработки последовательностей чисел, пар, троек и результатов динамического программирования.
Python
Словари dict и множества set
Множества обеспечивают мгновенный поиск элементов за O(1), а словари незаменимы для группировки данных по ключам и подсчёта частот.
Python
Модуль itertools (product, permutations)
Модуль itertools — главный чит-код для решения Заданий №2, №8 и №24 ЕГЭ
Python
Работа с файлами (open, readlines)
Файлы используются в Заданиях №9, №10, №17, №24, №26, №27 ЕГЭ
Python
Рекурсия и lru_cache
Рекурсия — основа Заданий №16 (Вычисление рекуррентных функций), №19–21 (Теория игр) и №23 (Динамика траекторий).
Python
Системы счисления (bin, oct, hex, int)
Системы счисления — ядро Заданий №5, №14 ЕГЭ и №10 ОГЭ