Быстрый ввод и вывод в Python

Как не получить TLE на пустом месте: правильное чтение ввода и формирование вывода в Python.

Быстрый ввод/вывод — приём, при котором всё чтение идёт через sys.stdin, а вывод копится в список и печатается одним print, чтобы не тратить время на тысячи системных вызовов.

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

Python удобен, но его обычные input() и print() медленны. Каждый вызов input() — отдельная операция чтения строки с разбором, каждый print() — отдельный сброс в поток. На задаче, где надо прочитать 10^6 чисел, наивный код может потратить на один только ввод-вывод больше секунды и упереться в TLE, хотя алгоритм у тебя правильный. Это самая обидная разновидность TLE: ты проигрываешь не алгоритмом, а «обвязкой». Поэтому быстрый ввод/вывод — обязательная гигиена, которую ставят рефлекторно.

Идея «на пальцах»

Сравним два подхода. Наивный читает построчно функцией input() — и тратит на каждую строку отдельный вызов. Быстрый — один раз забирает весь ввод как большой кусок памяти, а потом нарезает его уже внутри программы, где это дёшево. Аналогия: можно сходить в магазин 100 раз за одним продуктом, а можно один раз привезти всё на машине. Второе быстрее не потому, что продуктов меньше, а потому, что меньше «походов».

Канонический шаблон чтения

Самый универсальный приём — прочитать весь ввод, разбить по пробелам и переводам строк в один поток токенов, и брать из него числа по мере надобности.

import sys

def main():
    # В реальном решении: data = sys.stdin.buffer.read().split()
    # Здесь имитируем ввод строкой, чтобы пример был запускаемым:
    raw = "5\n4 2 7 1 9"
    data = raw.split()              # ['5', '4', '2', '7', '1', '9']
    idx = 0
    n = int(data[idx]); idx += 1    # сколько чисел
    a = []
    for _ in range(n):
        a.append(int(data[idx])); idx += 1
    a.sort()
    # Вывод одним блоком:
    print(" ".join(map(str, a)))

main()

Главное здесь — data = ...read().split(): один вызов чтения превращает весь ввод в список токенов. Дальше мы просто двигаем указатель idx. Метод split() без аргументов сам игнорирует любые пробелы и переводы строк, поэтому неважно, как именно числа разбиты по строкам.

Вывод:

1 2 4 7 9

Удобная обёртка через итератор

Возиться с индексом idx руками неудобно. Чище — сделать генератор токенов и брать из него по одному через next.

import sys

def main():
    raw = "3\n10 20\n5 5\n100 1"
    tokens = iter(raw.split())
    inp = lambda: next(tokens)      # следующий токен
    n = int(inp())
    res = []
    for _ in range(n):
        a, b = int(inp()), int(inp())
        res.append(a + b)
    sys.stdout.write("\n".join(map(str, res)) + "\n")

main()

iter(...) и next(...) дают «ленту» токенов: не важно, лежат два числа на одной строке или на разных — мы просто берём следующее. Вывод собираем в res и пишем разом через sys.stdout.write.

Вывод:

30
10
101

Три правила вывода

• Не печатай в цикле. 10^6 вызовов print — это 10^6 сбросов потока. Копи в список и выведи "\n".join(...) один раз.
• Преобразуй числа в строки оптом через map(str, ...), а не конкатенацией в цикле.
• Следи за форматом. Если требуется вывести числа через пробел — это " ".join, если по одному на строку — "\n".join.

Подводные камни Python на олимпиадах

Отдельно про рекурсию: предел по умолчанию — около 1000 вложенных вызовов. Для дерева на 10^5 вершин этого мало, и DFS «упадёт». Поэтому в начале решения почти всегда стоит import sys; sys.setrecursionlimit(1 << 20), а в тяжёлых случаях обход переписывают через явный стек (увидим это в разделе про графы).

Когда быстрый ввод реально нужен

Эмпирика: если по ограничениям читается больше ~10^5 чисел, ставь быстрый ввод сразу. Если данных мало (например, n ≤ 1000), хватит и обычного input() — не усложняй. Но привычка читать через sys.stdin ничего не стоит и страхует от обидных TLE, поэтому многие используют шаблон всегда.

Итог

• Читай весь ввод одним вызовом sys.stdin.buffer.read().split() и иди по токенам.
• Никогда не печатай в цикле — копи результат и выводи одним print/sys.stdout.write.
• Для DFS поднимай setrecursionlimit или переходи на стек.
• Python медленнее C++ в десятки раз — это нормально, важно беречь константу и асимптотику.