Олимпиада по информатике, 9–11 класс: школьный этап и подготовка

Школьный этап Всероссийской олимпиады по информатике в 9–11 классе — это уже не проверка аккуратности: комплект старшей группы отдельный, и в нём перебор «в лоб» перестаёт укладываться в ограничение по времени. Нужны приёмы, которые снижают сложность решения: сортировка, префиксные суммы, два указателя, бинарный поиск по ответу. Ниже — что именно спрашивают в этих классах, наши задачи того же типа с автопроверкой, план на четыре недели и то, куда результат ведёт дальше.

Чем комплект 9–11 класса отличается

Перебор перестаёт проходить по времени

Это главный водораздел между младшей и старшей группой. В 7–8 классе перебрать все варианты вложенными циклами — законное и обычно ожидаемое решение; в 9–11 размер входных данных подбирают так, что такое решение считается слишком долго и часть тестов не проходит. Поэтому решение начинается не с кода, а с вопроса «сколько операций это сделает».

Оценка сложности — часть решения, а не теория

Прикинуть порядок числа операций до написания кода дешевле, чем узнать про лимит после отправки. Сколько успевает Python на наших задачах — замерено у нас же, на странице про Python на олимпиадах; вывод из замеров простой: спасает не язык, а смена алгоритма.

Проверка идёт по группам тестов

Решение обычно гоняют на нескольких группах тестов, и частичное решение чаще всего приносит часть баллов. Значит, медленный, но правильный перебор писать стоит — он лучше пустого места. Точный регламент оценивания и проходной балл устанавливает региональный оргкомитет, и они различаются от региона к региону.

С 9 класса результат начинает работать на поступление

Школьный этап здесь — не отдельное соревнование, а вход в цепочку муниципальный → региональный → заключительный. Диплом заключительного этапа даёт поступление без вступительных испытаний, а диплом, полученный в 9 классе, действует четыре года — то есть работает и на поступление после 11-го.

Что спрашивают в 9–11 классе

Темы школьного этапа для этой группы — со ссылками на наши хабы, где по каждой есть объяснение и задачи:

• Жадные алгоритмы и обмен — Брать на каждом шаге локально лучший вариант — и уметь объяснить себе, почему он не испортит ответ дальше. Частая потеря баллов — жадность там, где она неверна.
• Жадные на отрезках — Классика этапа: выбрать как можно больше непересекающихся мероприятий, покрыть точки отрезками. Ключ почти всегда в том, по какому концу сортировать.
• Сортировка и что она упрощает — Сама сортировка пишется одной строкой, ценность в другом: после неё задача часто решается одним проходом вместо двух вложенных циклов.
• Префиксные суммы — Сумма на отрезке за одно действие вместо цикла. Первый приём, на котором видно, как подготовка данных заранее убирает вложенный цикл.
• Два указателя — Окно, которое едет по массиву: пара индексов вместо перебора всех пар. Требует аккуратности с границами — здесь теряют больше всего баллов.
• Бинарный поиск и поиск по ответу — Приём «угадать ответ и проверить его». Работает, когда ответ монотонен: если значение подходит, то и любое большее подходит тоже.
• Делители, остатки, простые числа — НОД, разложение на множители, арифметика остатков. Задача выглядит как про числа, а решается знанием одного свойства.
• Обход графа и сетки (BFS/DFS) — Комнаты и двери, клетки лабиринта, связные области на карте. На школьном этапе хватает обхода в ширину и в глубину, тяжёлых алгоритмов на графах не спрашивают.

Соседняя группа — олимпиада по информатике для 7–8 класса: там комплект легче, алгоритмов почти нет и решает аккуратность.

Задания прошлых лет: что с ними делать

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

Задачи для тренировки: 9–11 класс

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

• Сколько покупок поместится в бюджет — базовый
• Команда из лучших — базовый
• Фонари для парадного проспекта — средний
• Расписание школьной конференции — средний
• Кто на k‑м месте в таблице очков — базовый
• Шкафчики с почти одинаковыми кодами — базовый
• Баланс в школьной столовой — базовый
• Точка равновесия на стадионе — базовый
• Сдача без мелочи — базовый
• Склейка журналов двух роботов — базовый
• Полка с учебниками: первый не ниже — базовый
• Квадратный апгрейд — базовый

Больше задач по каждой теме — в хабах выше и в каталоге задач с фильтром по темам.

План подготовки за четыре недели

Короткая версия — что закрывать по неделям, если до этапа месяц и язык уже есть:

Неделя 1. Сложность и сортировка

Научиться до написания кода отвечать на вопрос «влезет ли». Плюс сортировка — не как алгоритм, а как приём: что в задаче упрощается, если данные упорядочить.

Неделя 2. Префиксные суммы и два указателя

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

Неделя 3. Бинарный поиск по ответу и жадные

Самая доходная пара на этапе: «угадать и проверить» и «брать лучшее на каждом шаге». К жадному обязательна привычка спрашивать себя, почему он верен.

Неделя 4. Тур на время

Никаких новых тем: 3–4 задачи за два часа без подсказок, потом разбор каждой неудачи до причины — не тот приём, не уложился в лимит, потерян крайний случай. Останется время — обход сетки и остатки.

Полный план с задачами на каждую неделю и чеком «умею» — на странице школьного этапа ВсОШ по информатике: там же формат тура, календарь сезона и разбор частых ошибок.

Что дальше: следующие этапы и поступление

Школьный этап в 9–11 классе — первая ступень цепочки, а не отдельное соревнование. Дальше идут муниципальный, региональный и заключительный этапы; окна сезона и формат каждого — на странице школьного этапа ВсОШ по информатике.

С 9 класса результат начинает работать на поступление: диплом заключительного этапа ВсОШ даёт поступление без вступительных испытаний на профильные направления, а диплом, полученный в 9 классе, действует четыре года — то есть засчитывается и после 11-го. Как это устроено, включая перечневые олимпиады, разобрано на странице «БВИ и льготы: что даёт олимпиада по информатике». Правила приёма каждый вуз публикует сам и меняет их между годами — проверять нужно на сайте вуза в год поступления.

На чём писать

Python разрешён на всех этапах ВсОШ по информатике, и на школьном этапе его скорости хватает: задачи этого уровня не рассчитаны на предельно быстрый язык. Дальше язык начинает упираться в ограничение по времени — но лечится это выбором алгоритма, а не переходом на другой язык. Подробный разбор с замерами — на странице «Python на олимпиадах»: где языка хватает, где он упирается в лимит и что делают вместо смены языка.

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

Вопросы и ответы

Что нужно уметь девятикласснику для школьного этапа по информатике?

Уверенной базы языка уже мало: нужны сортировка, префиксные суммы, два указателя и бинарный поиск по ответу, а главное — привычка оценивать, уложится ли решение в ограничение по времени. Отбора на школьный этап при этом нет: участвовать может любой школьник своей школы.

Правда ли, что в 9–11 классе перебор уже не проходит?

В части задач — да: размер входных данных подбирают так, чтобы решение «в лоб» не уложилось в лимит. Но писать его всё равно стоит: проверка обычно идёт по группам тестов, и медленное правильное решение чаще всего берёт часть баллов.

На каком языке решать в 9–11 классе — Python или C++?

Python разрешён на всех этапах ВсОШ по информатике, и на школьном этапе его скорости хватает. Дальше язык действительно начинает упираться в лимит, но лечится это сменой алгоритма, а не сменой языка — у нас это разобрано с замерами на своих задачах.

Где взять задания прошлых лет?

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

Зачем участвовать в 11 классе, если поступать уже в этом году?

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

Сколько времени нужно на подготовку?

Если язык уже есть — месяц по 30–40 минут в день закрывает базовый набор приёмов: план выше как раз на четыре недели. Если языка пока нет, сначала нужен он, и это ещё пара месяцев: начинать тогда надо не с этапа, а с курса.

С чего начать сегодня

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