Олимпиадные задачи для начинающих: ввод, перебор, примеры

Чем олимпиадные задачи отличаются от школьных

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

Что сравниваем	Учебное упражнение	Олимпиадная постановка
Проверка	учитель смотрит код	автоматическая, на скрытых тестах
Ввод	можно писать «Введите число:»	никаких подсказок, только данные
Вывод	можно пояснять словами	строго в указанном формате
Ограничения	обычно не важны	время работы и размер данных заданы явно
Оценка	верно или неверно	баллы за каждый пройденный тест или группу тестов

Отсюда главный навык олимпиадника — дисциплина. Решение может быть идеальным по идее, но если программа выводит «Ответ: 15» вместо «15», проверяющая система поставит ноль. Хорошая новость в том, что первые олимпиадные задачи требуют только того, что входит в базовый курс: ввода, условий, циклов и списков. По федеральной образовательной программе эти темы изучают на информатике в 8–9 классах^[1], а уровень школьного этапа олимпиады обычно начинается именно с них.

Как читать условие: 5 обязательных частей

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

Легенда. Сюжет: монеты, часы, роботы. Из него нужно вытащить математическую суть.
Формат входных данных. Что стоит в каждой строке: одно число, несколько через пробел, строка текста.
Формат выходных данных. Что и в каком виде вывести: через пробел, каждое на новой строке, с какой точностью.
Ограничения. Например, n не больше 10^9 — это подсказка, какой метод пройдёт по времени, а какой нет.
Примеры. Один-два теста с ответами. Решение обязано выдавать на них ровно такой вывод.

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

Ввод и вывод в Python без лишних слов

В олимпиадной задаче input() вызывают без текста подсказки: проверяющая система подаёт только данные, и любая лишняя надпись попадёт в вывод. Писать подсказку здесь нельзя, даже вежливую. Несколько чисел в одной строке читают через split().

a, b = map(int, input().split())
nums = list(map(int, input().split()))
print(a + b)
print(*nums)

Метод split() режет строку по пробелам, а map(int, ...) превращает каждую часть в число. Если в строке ровно два числа, их сразу раскладывают по переменным; если сколько угодно, складывают в список. Запись print(*nums) выводит элементы списка через пробел — без квадратных скобок и запятых, как обычно требуют форматы вывода. Различие «каждое число в своей строке» и «все в одной строке через пробел» — самая частая причина ошибки на первом тесте. Функции map и split описаны в документации Python в разделах о встроенных функциях и методах строк. Подробнее о разборе ввода — в уроке о функции input и split.

Перебор — первый метод олимпиадника

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

Возьмём задачу 4 из тренажёра: сколькими способами набрать сумму монетами по 2 и 5 рублей? Можно долго рассуждать о делимости, а можно перебрать количество двушек от 0 до S // 2 и для каждого проверить, делится ли остаток суммы на 5. При S не больше 1000 вариантов не наберётся и пятисот — это мгновенно.

s = 20
ways = 0
for twos in range(s // 2 + 1):
    rest = s - 2 * twos
    if rest % 5 == 0:
        ways += 1
print(ways)

Для S = 20 подходят три варианта: 0 двушек и 4 пятёрки, 5 двушек и 2 пятёрки, 10 двушек без пятёрок. Перед тем как писать перебор, оцените по ограничениям, сколько вариантов придётся проверить. Грубый ориентир для Python: миллион простых проверок обычно укладывается в ограничение по времени, а миллиард — нет. Если перебор слишком долгий, ищите способ сократить его — об этом следующий раздел. Похожие упражнения на делимость и цифры собраны в подборке задач на числа с автопроверкой.

Разбор: делители и ускорение до корня

Если n достигает 10^12, перебирать все числа от 1 до n слишком долго. Но делители идут парами: если d делит n, то и n // d тоже делитель. Поэтому достаточно перебрать d только до квадратного корня из n.

n = 36
small = []
big = []
d = 1
while d * d <= n:
    if n % d == 0:
        small.append(d)
        if d != n // d:
            big.append(n // d)
    d += 1
print(small + big[::-1])

[1, 2, 3, 4, 6, 9, 12, 18, 36]

Для n = 10^12 цикл сделает около миллиона шагов вместо триллиона. Проверка d != n // d нужна, чтобы не записать корень дважды: для 36 это число 6. В тренажёре задача 3 рассчитана на n до 10 000, и там подойдёт простой перебор, но идею с корнем полезно знать заранее: она встречается в задачах про простые числа и делители очень часто.

Разбор: часы и формула вместо цикла

Иногда перебор не нужен вовсе: задачу 5 про часы можно решить одной формулой. Время удобно перевести в минуты от полуночи, прибавить k и взять остаток от деления на 1440 — столько минут в сутках.

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

Как проверять своё решение

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

Тип теста	Пример	Что ловит
Минимальный ввод	`n = 1`, один элемент	цикл не выполняется ни разу
Нули и отрицательные	0, −5	неверную начальную переменную максимума
Одинаковые значения	4 4 4	строгое и нестрогое сравнение
Максимальный ввод	n по верхней границе	слишком медленный перебор

В тренажёре над статьёй это делается автоматически: нажмите «✓ Проверить», и решение запустится на нескольких тестах, включая крайние случаи. Справа появится, какие тесты пройдены, а для непройденных — «Ожидалось» и «Получилось». Кнопка «Подсказка» откроет наводку, а «Показать решение» — готовый код; открывать его стоит после нескольких своих попыток.

ВсОШ по информатике: 4 этапа

Всероссийская олимпиада школьников по информатике проходит в 4 этапа: школьный, муниципальный, региональный и заключительный. Порядок её проведения утверждён приказом Минпросвещения России от 27.11.2020 № 678^[2].

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

Как готовиться: план для начинающего

Готовиться лучше регулярно, по 2–3 задачи несколько раз в неделю: распределённая практика даёт более прочный результат, чем долгие занятия раз в месяц^[3].

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

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

Когда олимпиадная подготовка не подходит

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

Ученик пишет на Python меньше 2–3 месяцев. Сначала нужны базовые темы, иначе формат и ограничения только отпугнут.
Ребёнку 8–10 лет и ему интереснее игры. Проекты в Scratch или текстовые игры дадут больше мотивации.
Цель — сдать ОГЭ. Экзамен из 16 заданий проверяет более широкий набор тем, и готовиться к нему нужно по его материалам.
Решение 1 задачи вызывает слёзы и ссоры. Давление разрушает интерес быстрее, чем любая трудная задача.

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

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

Чего делать нельзя

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

Нельзя писать подсказки в input() — текст «Введите число» попадёт в ответ.
Не стоит выводить пояснения вроде «Ответ:» — только то, что требует формат.
Не следует игнорировать ограничения: по ним видно, пройдёт ли перебор.
Не стоит начинать максимум с нуля: все числа могут оказаться отрицательными.
Нельзя отправлять решение, не проверив крайние случаи вроде n = 1.
Не допускается сидеть над одной задачей весь тур: если идеи нет 20–30 минут, переходите к следующей.

Синтаксис и встроенные функции, которые пригодились в примерах, описаны в официальной документации Python^[4].

Источники

[1] Приказ Минпросвещения России от 18.05.2023 № 370 «Об утверждении федеральной образовательной программы основного общего образования».

[2] Приказ Минпросвещения России от 27.11.2020 № 678 «Об утверждении Порядка проведения всероссийской олимпиады школьников».

[3] Cepeda N. J., Pashler H., Vul E., Wixted J. T., Rohrer D. Distributed practice in verbal recall tasks: A review and quantitative synthesis // Psychological Bulletin. 2006. Vol. 132, № 3. P. 354–380.

[4] The Python Tutorial (официальная документация Python 3). Python Software Foundation.

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

Можно ли решать олимпиадные задачи на Python?

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

С какого класса можно участвовать?

Школьный этап открыт для учеников разных классов; конкретные параллели и задания для них определяют организаторы. Уточните у учителя информатики.

Что делать, если решение проходит не все тесты?

Подумайте, какие крайние случаи вы не проверили: минимальный ввод, нули, одинаковые числа, максимальный размер. Часто ошибка именно там.

Нужна ли для этого математика?

На начальном уровне хватает делимости, остатков и аккуратного счёта. Чем дальше, тем больше пригодятся комбинаторика и логика.

Сколько задач решать в неделю?

Лучше 5–8 задач, разобранных до конца, чем 30 начатых. Важно возвращаться к нерешённым через несколько дней.

Чем помогает тренажёр на этой странице?

Он проверяет решения на тестах, как проверяющая система на соревновании, и показывает, где вывод разошёлся с ожидаемым. Это хорошая разминка перед настоящим туром.