Как устроены олимпиады и онлайн-судьи

С чего начинается спортивное программирование: формат соревнований, онлайн-судьи и язык вердиктов.

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

Зачем это нужно

Олимпиадная информатика — это спорт, где вместо штанги ты поднимаешь задачи. На ВсОШ (Всероссийская олимпиада школьников), на Codeforces и в USACO тебе дают условие, ограничения и примеры, а ты должен написать программу, которая за отведённое время и память правильно ответит на все тесты, включая те, которых ты не видишь. Этот навык ценится сам по себе (дипломы, поступление без экзаменов, оффер в большую IT-компанию), но ещё важнее то, что он перестраивает мышление: ты учишься превращать расплывчатую задачу в строгую модель и подбирать к ней алгоритм с гарантией по времени.

Этот курс ведёт от полного перебора до дерева отрезков и динамики, и весь код — на Python, потому что на нём идею видно без шума синтаксиса. Где Python принципиально медленнее C++, мы это честно оговариваем.

Из чего состоит задача

Любая олимпиадная задача — это пять частей. Научись читать их в одном и том же порядке, и половина ошибок исчезнет сама.

• Условие (легенда). История про рыцарей и замки. Твоя работа — отбросить антураж и понять, что именно требуется посчитать.
• Формат ввода. Сколько чисел, в каком порядке, в каких строках. Здесь же — ограничения: например, 1 ≤ n ≤ 10^5. Это самая важная строчка во всём условии (об этом — отдельный урок).
• Формат вывода. Что и как печатать. Лишний пробел или перевод строки часто прощается, но не всегда.
• Примеры. Пара тестов «вход → выход», на которых можно проверить понимание. Они почти всегда тривиальные и не ловят твои баги — на них рассчитывать нельзя.
• Ограничения по времени и памяти. Обычно 1–2 секунды и 256 МБ. Именно они определяют, какая асимптотика «пройдёт».

Язык вердиктов

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

Ключевая мысль: WA и TLE лечатся по-разному. WA — это «программа делает не то»; TLE — это «программа делает то, но слишком медленно». Спутать диагноз — значит чинить не то.

Системы оценивания

Есть два больших мира. На Codeforces (формат ICPC) задача засчитывается только целиком: прошёл все тесты — получил баллы, упал хоть на одном — ноль. Здесь ценится скорость и аккуратность. На ВсОШ и многих школьных олимпиадах (формат IOI) задача разбита на подзадачи (группы тестов) со своими баллами и ограничениями. Часто первая группа — это маленькие n, которые решает даже полный перебор. Это меняет стратегию: иногда выгодно быстро забрать «лёгкие» баллы простым решением, а уже потом думать над полным.

Первое решение: A + B

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

import sys

def main():
    data = "3\n10 20\n5 5\n100 1".split("\n")  # имитация input()
    it = iter(data)
    n = int(next(it))                 # сколько пар
    out = []
    for _ in range(n):
        a, b = map(int, next(it).split())
        out.append(str(a + b))
    print("\n".join(out))             # один print в конце — так быстрее

main()

Здесь мы читаем число тестов, в цикле разбираем каждую строку через map(int, ...split()) и копим ответы в список, чтобы вывести их одним print. В реальном решении вместо строки-заглушки будет sys.stdin — об этом следующий урок.

Вывод:

30
10
101

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

• Решай чуть выше своего уровня: слишком лёгкое не учит, слишком сложное демотивирует.
• Не подсматривай разбор сразу. Застрял на 30–40 минут — посмотри идею, но код пиши сам.
• Веди список приёмов. Спортивное программирование — это узнавание паттернов: «о, это бинпоиск по ответу», «о, это два указателя».
• После AC читай чужие короткие решения той же задачи — там много идиом.

Итог

• Онлайн-судья прогоняет код на скрытых тестах и выдаёт вердикт; примеры в условии багов не ловят.
• WA — ошибка в логике, TLE — медленный алгоритм; это разные болезни.
• Формат ICPC — «всё или ничего», формат IOI/ВсОШ — подзадачи с частичными баллами.
• Скелет решения: прочитать ввод → посчитать → вывести одним блоком.