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

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

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

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

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

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

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

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

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

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

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

Что доступно в вашем классе

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

Лестница целиком, со сроками и с тем, что даёт диплом каждой ступени, — на странице этапов ВсОШ по информатике.

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

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

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

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

Задания прошлых лет

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

Чужих условий мы у себя не копируем. Где их взять у организатора и как разбирать — на странице заданий ВсОШ.

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

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

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

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

Подборка ровно своего класса, по двенадцать задач с разбором тем: 9 класс, 10 класс, 11 класс.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На чём писать

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разница между «понимаю приём» и «применю его на туре» видна только на задаче, которую решаешь сам. Открыть первую задачу с автопроверкой — без регистрации и бесплатно.