Алгоритмы на Python — ЕГЭ и олимпиадка

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Для кого эта статья

Подборка готовых решений на Python 3 с разбором «что и зачем» в каждой строке. Материал рассчитан на:

подготовку к ЕГЭ по информатике (задания 16–27, где пишут программу);
школьные олимпиады и кружки по программированию;
первые шаги в олимпиадном программировании, когда уже знаете циклы и списки, но не понимаете, как «собрать» решение из условия.

Каждый пример можно скопировать, сохранить в файл .py и запустить локально: python task.py. Если есть файл с входом — python task.py < input.txt.

Сначала теория

Алгоритмы в общем виде — в разделе Алгоритмы. Синтаксис Python — в Первой программе. Ввод из файла (< input.txt, sys.stdin) — Python — файлы и текст. Те же приёмы на C++ — олимпиадные шаблоны C++. Визуальные примеры для отдыха от задач — Turtle.

Краткий указатель по разделам

Раздел	Что ищут в Google / на экзамене
Каркас ввода-вывода	`input()`, `map`, `split`, чтение массива
Стартовые задачи	сумма, максимум, чётные, FizzBuzz
1. Ускорение ввода	`sys.stdin`, много тестов
2. Перебор	двойной цикл, пары, тройки
3. Словари и множества	`Counter`, пара с суммой k
4. Сортировка и поиск	`sort`, бинарный поиск
5. Префиксные суммы	сумма на отрезке, разностный массив
6. Два указателя	палиндром, слияние, окно
7. Числа	НОД, решето, быстрая степень
8. Строки	анаграмма, подстрока
9. Графы	BFS, DFS, лабиринт
10. ДП	рюкзак, LCS, лестница
11. Рекурсия	перестановки, маски
12–13. Шпаргалка	заготовки перед сдачей

Основы решения задач на Python

На ЕГЭ и олимпиадах программа почти всегда устроена одинаково:

Прочитать вход по формату из условия.
Посчитать ответ алгоритмом (цикл, массив, поиск…).
Вывести ровно то, что просят — без лишних слов и с правильными пробелами.

Достаточно стандартной библиотеки: списки, словари, множества, sort, math, иногда collections и itertools.

Обязательный каркас

Три шаблона покрывают большинство задач на массив чисел.

Шаблон A — одно число

Задача: прочитать число n и вывести удвоенное.

n = int(input())   # input() возвращает строку; int() превращает её в целое
print(n * 2)       # print() добавляет перевод строки в конце

Пример:

Вход:  7
Выход: 14

Разбор:

Строка	Смысл
`input()`	Ждёт строку с клавиатуры (или из файла при перенаправлении).
`int(...)`	Без этого `n` была бы строкой `"7"`, и `"7" * 2` дало бы `"77"`, а не `14`.
`print(...)`	Пишет в stdout — туда смотрит проверяющая система на ЕГЭ.

Шаблон B — массив из n чисел (две строки входа)

Задача: дана длина n, затем n целых — найти сумму.

n = int(input())
a = list(map(int, input().split()))
print(sum(a))

Пример:

Вход:
5
3 1 4 1 5

Выход:
14

Разбор по шагам:

input().split() — режет строку "3 1 4 1 5" по пробелам → список строк ['3', '1', '4', '1', '5'].
map(int, ...) — к каждой строке применяет int → итератор чисел.
list(...) — материализует список [3, 1, 4, 1, 5].
sum(a) — встроенная сумма элементов.

Цепочка list(map(int, input().split())) — самый частый однострочник в задачах на Python. Запомните его как «прочитать массив целых из строки».

Шаблон C — все числа в одной строке (без n)

a = list(map(int, input().split()))
print(max(a))

Пример:

Вход:  3 1 4 1 5
Выход: 5

Когда какой шаблон: смотрите на формат входа в условии. Если первая строка — только длина, берите B. Если сразу числа — C.

ЕГЭ и олимпиада

На ЕГЭ хватает input(). На олимпиадах с огромным входом (10⁵+ чисел) ускоряют чтение через sys.stdin — раздел 1. Формат вывода должен буквально совпадать с условием: лишний пробел или Yes вместо yes — минус баллы.

Стартовые задачи

Простые задачи, на которых отрабатывают цикл, условие и индексацию.

Сумма двух чисел

Классическая «первая задача» на любой платформе (Codeforces A, учебник, пробник ЕГЭ).

a = int(input())
b = int(input())
print(a + b)

Вход: две строки с числами. Выход: одна строка — сумма.

Частая ошибка: читать одной строкой a, b = map(int, input().split()), когда в условии числа на разных строках — тогда программа ждёт пробел там, где его нет.

Количество чётных в списке

Условие: дан массив, сколько элементов делятся на 2 без остатка.

n = int(input())
a = list(map(int, input().split()))
count = 0
for x in a:
    if x % 2 == 0:   # остаток от деления на 2 равен нулю → число чётное
        count += 1   # то же, что count = count + 1
print(count)

Пример: 4 → 2 3 4 6 → ответ 2 (элементы 2 и 4).

Разбор цикла: переменная x по очереди принимает каждое значение из a. Счётчик count накапливает результат — шаблон «инициализировать нулём → в цикле увеличивать».

Оператор %: 7 % 2 == 1 (нечётное), 8 % 2 == 0 (чётное). Для отрицательных чисел на ЕГЭ это тоже работает в Python 3.

Максимум и индекс (нумерация с 1)

В школьных условиях элементы часто нумеруют с 1, а в Python индексы с 0.

a = list(map(int, input().split()))
best = a[0]      # пока считаем первый элемент максимальным
pos = 1          # человеческий индекс первого элемента
for i in range(1, len(a)):   # i = 1, 2, … len(a)-1
    if a[i] > best:
        best = a[i]
        pos = i + 1            # переводим индекс Python в «школьный»
print(best, pos)

Пример: 3 9 1 9 → максимум 9, первое вхождение на позиции 2 (если в условии «первый максимум»).

Разбор: range(1, len(a)) не проверяет a[0] повторно — он уже в best. Если нужен последний максимум, уберите > и используйте >=.

FizzBuzz до n

Задача на приоритет условий: число, делящееся и на 3, и на 5, должно дать FizzBuzz, а не просто Fizz или Buzz.

n = int(input())
for i in range(1, n + 1):   # от 1 до n включительно
    if i % 15 == 0:         # 15 = 3 * 5 — проверяем оба делителя сразу
        print("FizzBuzz")
    elif i % 3 == 0:
        print("Fizz")
    elif i % 5 == 0:
        print("Buzz")
    else:
        print(i)

Почему % 15 первым: если написать сначала % 3, число 15 попадёт в ветку Fizz и до FizzBuzz не дойдёт.

range(1, n + 1): верхняя граница в range не включается, поэтому + 1.

Примеры алгоритмов

1. Ввод-вывод и ускорение

1.1. Пакетное чтение через `sys.stdin`

Когда нужно: десятки тысяч чисел; обычный input() в цикле может не уложиться в лимит времени.

Идея: прочитать весь вход одним куском, разбить на «слова», брать числа по очереди через итератор.

import sys

data = sys.stdin.read().split()   # все токены подряд в списке строк
it = iter(data)                   # итератор — «курсор» по списку

n = int(next(it))                 # первое число — длина массива
a = [int(next(it)) for _ in range(n)]   # следующие n чисел
print(sum(a))

Пример входа:

5
10 20 30 40 50

Выход: 150

Разбор:

Конструкция	Зачем
`sys.stdin.read()`	Читает поток целиком до EOF.
`.split()`	Без аргумента режет по любым пробельным символам — переносы строк не мешают.
`iter(data)` + `next(it)`	Ручной разбор формата: «сначала n, потом n чисел».
list comprehension	Компактно собрать массив.

1.2. Вывод массива одной строкой

На ЕГЭ часто просят: «выведите элементы через пробел».

a = [3, 1, 4, 1, 5]
print(" ".join(map(str, a)))
# 3 1 4 1 5

Разбор: map(str, a) превращает числа в строки; " ".join(...) склеивает через пробел. print(*a) тоже работает, но join удобнее, если нужен свой разделитель (",").

Ошибка: print(a) выведет [3, 1, 4, 1, 5] со скобками — формат не совпадёт с условием.

1.3. Несколько тестов в одном запуске

Формат олимпиад: первая строка t — сколько независимых задач в файле.

t = int(input())
for _ in range(t):          # _ — «цикл t раз, счётчик не нужен»
    n = int(input())
    a = list(map(int, input().split()))
    print(sum(a))

Пример:

Выход:

6
30

Каждый проход цикла — отдельный тест со своим входом и одной строкой ответа.

2. Перебор, условия и вложенные циклы

Полный перебор — первый рабочий вариант, когда n небольшое (до ~500–2000). Сложность обычно O(n²) или O(n³).

2.1. Подсчёт пар с суммой k

Условие: сколько неупорядоченных пар (i, j), i < j, дают a[i] + a[j] == k.

n = int(input())
a = list(map(int, input().split()))
k = int(input())
count = 0
for i in range(n):
    for j in range(i + 1, n):   # j строго больше i — пара не считается дважды
        if a[i] + a[j] == k:
            count += 1
print(count)

Пример: a = [1, 2, 3, 2], k = 4 → пары (0,2): 1+3 и (1,3): 2+2 → ответ 2.

Сложность: O(n²) — для n = 10⁵ будет слишком медленно. Ускорение — раздел 3.2.

2.2. Есть ли тройка с суммой 0

Три вложенных цикла — O(n³). Подходит только для маленьких массивов.

a = list(map(int, input().split()))
n = len(a)
found = False
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if a[i] + a[j] + a[k] == 0:
                found = True
                break
        if found:
            break
    if found:
        break
print("yes" if found else "no")

Разбор break: во внутреннем цикле break выходит только из него. Флаги found и дополнительные break во внешних циклах останавливают перебор, как только ответ найден.

Тернарный оператор: "yes" if found else "no" — короткая запись if-else для одного выражения.

2.3. Поиск символа на поле (двумерный массив)

Условие: таблица rows × cols, найти координаты первой клетки с символом target (1-based).

rows, cols = map(int, input().split())
field = [input().strip() for _ in range(rows)]   # список строк — «строки таблицы»
target = input().strip()
found = False
for r in range(rows):
    for c in range(cols):
        if field[r][c] == target:
            print(r + 1, c + 1)   # +1 для нумерации с 1
            found = True
            break
    if found:
        break

Разбор field[r][c]: r — номер строки (0 сверху), c — номер столбца. Строка в Python — последовательность символов, field[r][c] — символ в клетке.

List comprehension [input().strip() for _ in range(rows)] читает rows строк подряд.

3. Словари, множества и частоты

Словарь хранит «ключ → значение», множество — уникальные элементы с быстрой проверкой «есть ли уже».

3.1. Подсчёт вхождений каждого числа

from collections import Counter

a = list(map(int, input().split()))
freq = Counter(a)              # Counter сам считает частоты
for x in sorted(freq):         # ключи по возрастанию
    print(x, freq[x])

Пример: 3 1 4 1 5 → строки 1 2, 3 1, 4 1, 5 1.

Без Counter (то же самое вручную):

freq = {}
for x in a:
    freq[x] = freq.get(x, 0) + 1

dict.get(x, 0) — если ключа нет, вернёт 0 вместо ошибки.

3.2. Пара с суммой k за O(n)

Идея: идём по массиву; для текущего x нужен «партнёр» k - x, который мы уже видели.

a = list(map(int, input().split()))
k = int(input())
seen = set()       # множество уже встреченных чисел
found = False
for x in a:
    if k - x in seen:    # проверка за O(1) в среднем
        found = True
        break
    seen.add(x)          # добавляем x только после проверки — нельзя использовать элемент с самим собой дважды
print("yes" if found else "no")

Пример: a = [2, 7, 11, 15], k = 9 → 2 + 7 → yes.

Почему seen.add(x) после проверки: для k = 6, x = 3 нельзя считать пару (3, 3), если в массиве одна тройка.

Сложность: O(n) времени, O(n) памяти.

3.3. Первый неповторяющийся символ

Два прохода: сначала частоты, потом первый символ с частотой 1.

s = input().strip()
freq = {}
for ch in s:
    freq[ch] = freq.get(ch, 0) + 1
for ch in s:
    if freq[ch] == 1:
        print(ch)
        break
else:
    print("-")    # else у for выполнится, если break не сработал

Конструкция for … else: блок else привязан к циклу, не к if. Выполняется, если цикл завершился без break.

3.4. Пересечение двух списков

a = set(map(int, input().split()))
b = set(map(int, input().split()))
print(len(a & b))    # & — пересечение множеств

Пример: {1,2,3} и {2,3,4} → {2,3} → длина 2.

4. Сортировка и поиск

Теория — Алгоритмы сортировки и поиска. В Python на практике почти всегда sorted() или .sort() — внутри Timsort, O(n log n).

4.1. Сортировка и параметр `key`

pairs = [(3, "c"), (1, "a"), (2, "b")]
pairs.sort()                    # по первому элементу кортежа
print(pairs)                    # [(1, 'a'), (2, 'b'), (3, 'c')]

pairs.sort(key=lambda p: p[1], reverse=True)   # по второму полю, по убыванию

lambda p: p[1] — анонимная функция «взять второй элемент». reverse=True — от большего к меньшему.

Частый кейс на ЕГЭ: сортировка списка кортежей (оценка, имя) по оценке, при равенстве — по имени:

pairs.sort(key=lambda p: (-p[0], p[1]))

Минус перед p[0] разворачивает порядок по числу без reverse=True для всего списка.

4.2. k-й по величине элемент

a = list(map(int, input().split()))
k = int(input())
print(sorted(a)[k - 1])    # k=1 → индекс 0 — первый в отсортированном списке

Пример: 7 2 9 2, k = 2 → сортировка [2, 2, 7, 9] → второй элемент 2.

Нюанс: при «k-й различный» нужна другая логика — сначала sorted(set(a)).

4.3. Бинарный поиск в отсортированном массиве

Идея: на каждом шаге отбрасываем половину диапазона. Работает только если массив отсортирован.

def bin_search(a, target):
    lo, hi = 0, len(a) - 1      # границы текущего диапазона
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid           # нашли — индекс в Python (с 0)
        if a[mid] < target:
            lo = mid + 1         # ответ правее mid
        else:
            hi = mid - 1         # ответ левее mid
    return -1                    # не нашли

a = sorted(map(int, input().split()))
x = int(input())
idx = bin_search(a, x)
print(idx + 1 if idx >= 0 else 0)   # перевод в 1-based, если так в условии

Пример: a = [1, 3, 5, 7], x = 5 → индекс 2 → вывод 3 (если 1-based).

Инвариант цикла: если target есть в массиве, он всегда лежит между lo и hi.

Сложность: O(log n) — для миллиона элементов ~20 шагов.

4.4. Бинарный поиск по ответу

Тип задачи: «найти минимальное целое x, при котором условие выполняется». Прямой формулы нет — зато для любого x легко проверить «подходит / не подходит», и при увеличении x условие становится истинным (монотонность).

Пример: прочитать n страниц, в день не больше k страниц — минимум дней?

def enough(days, n, k):
    return days * k >= n    # за days дней прочитаем не меньше n страниц

n = int(input())
k = int(input())
lo, hi = 1, n               # ответ между 1 и n дней
while lo < hi:
    mid = (lo + hi) // 2
    if enough(mid, n, k):
        hi = mid            # mid подходит — пробуем меньше
    else:
        lo = mid + 1        # mid мало — нужно больше дней
print(lo)

Пример: n = 10, k = 3 → дней минимум 4 (3+3+3+1).

Разбор: ищем левую границу «первого подходящего» значения. Когда lo == hi, это и есть ответ.

5. Префиксные суммы и разностные массивы

5.1. Сумма на отрезке [l, r] за O(1)

Проблема: много запросов «сумма с l по r» — наивный цикл каждый раз O(n). Префиксные суммы считают один раз, запрос — O(1).

a = list(map(int, input().split()))
pref = [0]                    # pref[0] = 0 — «пустой» префикс
for x in a:
    pref.append(pref[-1] + x) # pref[i] = сумма a[0] + … + a[i-1]

l, r = map(int, input().split())   # 1-based в условии
print(pref[r] - pref[l - 1])

Пример: a = [2, 3, 5, 1], pref = [0, 2, 5, 10, 11]. Отрезок l=2, r=3 (элементы 3 и 5): pref[3] - pref[1] = 10 - 2 = 8.

Картинка в голове: pref[r] — сумма до r включительно; вычитаем «лишнее» до l-1.

5.2. Много запросов к массиму 0/1

Тот же приём: pref[i] = сколько единиц в a[0..i-1].

a = [int(x) for x in input().split()]
pref = [0]
for x in a:
    pref.append(pref[-1] + x)

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(pref[r] - pref[l - 1])

5.3. Разностный массив — много «прибавить v на отрезке [l, r]»

Идея: вместо того чтобы прибавлять v каждому элементу от l до r (медленно), помечаем начало и конец отрезка в массиве diff.

n, q = map(int, input().split())
diff = [0] * (n + 2)          # +2 — чтобы diff[r+1] не вышел за границу
for _ in range(q):
    l, r, v = map(int, input().split())
    diff[l] += v
    diff[r + 1] -= v          # «отмена» прибавления после r

a = [0] * (n + 1)
for i in range(1, n + 1):
    a[i] = a[i - 1] + diff[i]  # восстановление итогового массива
print(*a[1:])

Пример: n=5, один запрос «на [2,4] прибавить 3» → к элементам 2,3,4 прибавится 3.

Когда встречается: задачи на обновление диапазона; на ЕГЭ реже, на олимпиадах — чаще.

6. Два указателя

Два индекса двигаются по массиву или строке; часто после сортировки или на отсортированных данных.

6.1. Палиндром

s = input().strip().lower()   # lower() — «A» и «a» считаем одинаковыми
i, j = 0, len(s) - 1          # i слева, j справа
ok = True
while i < j:
    if s[i] != s[j]:
        ok = False
        break
    i += 1
    j -= 1
print("yes" if ok else "no")

Пример: "aba" → yes, "ab" → no.

Сложность: O(n) — один проход.

6.2. Слияние двух отсортированных списков

Как в merge sort — сравниваем «головы» двух списков, меньший забираем в результат.

a = list(map(int, input().split()))
b = list(map(int, input().split()))
i = j = 0
merged = []
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        merged.append(a[i])
        i += 1
    else:
        merged.append(b[j])
        j += 1
merged.extend(a[i:])    # хвост того списка, который не закончился
merged.extend(b[j:])
print(*merged)

Пример: 1 3 5 + 2 4 6 → 1 2 3 4 5 6.

6.3. Скользящее окно — длиннейший подмассив с суммой ≤ k

right расширяет окно, left сжимает, пока сумма cur слишком большая.

a = list(map(int, input().split()))
k = int(input())
best_len = 0
left = 0
cur = 0
for right in range(len(a)):
    cur += a[right]
    while cur > k and left <= right:
        cur -= a[left]
        left += 1
    if cur <= k:
        best_len = max(best_len, right - left + 1)
print(best_len)

Пример: a = [1, 2, 3, 4], k = 5 → подмассив [2, 3] длины 2.

Сложность: O(n) — каждый элемент left и right сдвигают не более одного раза.

7. Числа и классика

Подробнее — Евклид и классические алгоритмы.

7.1. НОД и НОК

import math

a, b = map(int, input().split())
g = math.gcd(a, b)              # наибольший общий делитель
lcm = abs(a * b) // g           # НОК = |a*b| / НОД; // — целочисленное деление
print(g, lcm)

Пример: 12 и 18 → НОД 6, НОК 36.

Зачем на ЕГЭ: сокращение дробей, периодичность событий, задачи «встретятся ли через n шагов».

7.2. Алгоритм Евклида вручную

Тот же НОД без math — полезно, если на экзамене ограничивают импорт.

a, b = map(int, input().split())
while b:
    a, b = b, a % b    # пара (a,b) → (b, остаток от a/b)
print(abs(a))

Пример: НОД(252, 198): (252,198) → (198,54) → (54,36) → (36,18) → (18,0) → ответ 18.

7.3. Решето Эратосфена — все простые до n

n = int(input())
if n < 2:
    print()
else:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:           # достаточно проверять делители до √n
        if is_prime[p]:
            for k in range(p * p, n + 1, p):   # кратные p начиная с p²
                is_prime[k] = False
        p += 1
    print(*[i for i in range(2, n + 1) if is_prime[i]])

Пример: n=10 → 2 3 5 7.

Идея: для каждого простого p вычёркиваем составные кратные. Начинаем с p*p, потому что меньшие кратные уже вычеркнуты меньшими простыми.

7.4. Быстрое возведение в степень по модулю

Нужно для больших степеней без переполнения — O(log n) умножений.

def pow_mod(a, n, mod):
    result = 1
    a %= mod
    while n:
        if n & 1:                      # младший бит n = 1?
            result = result * a % mod
        a = a * a % mod
        n >>= 1                        # n //= 2
    return result

a, n, mod = map(int, input().split())
print(pow_mod(a, n, mod))

Разбор битов: n & 1 — нечётное ли n; n >>= 1 — делим степень пополам. Это двоичное разложение показателя.

Пример: 2^10 mod 1000 → 24.

8. Строки

8.1. Разворот строки

s = input().strip()
print(s[::-1])    # срез с шагом -1 — с конца к началу

Пример: python → nohtyp.

8.2. Анаграмма — те же буквы в другом порядке

from collections import Counter

a = input().strip().lower()
b = input().strip().lower()
print("yes" if Counter(a) == Counter(b) else "no")

Пример: listen и silent → yes.

8.3. Поиск подстроки

text = input().strip()
sub = input().strip()
idx = text.find(sub)    # -1, если не найдено
print(idx + 1 if idx >= 0 else 0)   # 1-based позиция

Пример: ababc, abc → первое вхождение с индекса 2 → вывод 3 (1-based).

8.4. Разбиение CSV-подобной строки

line = input().strip()
parts = line.split(";")
print(len(parts))
for p in parts:
    print(p.strip())    # strip убирает пробелы по краям каждой части

Пример: "a; b ; c" → три части после strip.

9. Графы — сетка, BFS и DFS

Теория — Графы. На школьном уровне часто достаточно клеточного поля (лабиринт) или списка смежности.

9.1. DFS — сколько проходимых клеток

DFS (обход в глубину): идём вперёд, пока можно; # — стена, . — проход.

def dfs(grid, r, c, visited):
    rows, cols = len(grid), len(grid[0])
    if r < 0 or c < 0 or r >= rows or c >= cols:   # вышли за поле
        return
    if grid[r][c] == "#" or (r, c) in visited:     # стена или уже были
        return
    visited.add((r, c))
    dfs(grid, r + 1, c, visited)   # вниз, вверх, вправо, влево
    dfs(grid, r - 1, c, visited)
    dfs(grid, r, c + 1, visited)
    dfs(grid, r, c - 1, visited)

rows, cols = map(int, input().split())
grid = [input().strip() for _ in range(rows)]
visited = set()
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == ".":
            dfs(grid, r, c, visited)
print(len(visited))

Разбор: visited не даёт заходить в одну клетку дважды. Внешний двойной цикл запускает DFS из каждой непосещённой . — так считают компоненты связности (острова).

Осторожно: глубокая рекурсия на большом поле может дать RecursionError — тогда BFS или итеративный DFS со стеком.

9.2. BFS — кратчайший путь в лабиринте

BFS (в ширину): сначала обходим всех соседей на расстоянии 1, потом на 2… На невзвешенном графе первый раз, когда дошли до цели — кратчайший путь.

from collections import deque

def bfs(grid, sr, sc):
    rows, cols = len(grid), len(grid[0])
    q = deque([(sr, sc, 0)])    # очередь: (строка, столбец, расстояние)
    seen = {(sr, sc)}
    while q:
        r, c, dist = q.popleft()
        if grid[r][c] == "G":   # цель — клетка 'G'
            return dist
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
                if (nr, nc) not in seen:
                    seen.add((nr, nc))
                    q.append((nr, nc, dist + 1))
    return -1

rows, cols = map(int, input().split())
grid = [input().strip() for _ in range(rows)]
sr, sc = map(int, input().split())
print(bfs(grid, sr - 1, sc - 1))

Почему deque: вынимать из начала очереди (popleft) за O(1); у списка pop(0) было бы O(n).

9.3. Граф как списки соседей — DFS итеративно

from collections import defaultdict

n, m = map(int, input().split())   # n вершин, m рёбер
g = defaultdict(list)
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)                 # неориентированный граф

start = int(input())
stack = [start]
seen = {start}
order = []
while stack:
    v = stack.pop()                # LIFO — как рекурсивный DFS
    order.append(v)
    for to in sorted(g[v], reverse=True):
        if to not in seen:
            seen.add(to)
            stack.append(to)
print(*order)

Пример: треугольник 1—2—3, старт 1 → порядок обхода зависит от порядка соседей в стеке.

10. Динамическое программирование

ДП — когда ответ строится из уже посчитанных подзадач; обычно таблица dp[…] и переход «взять / не взять», «слева / сверху».

10.1. Числа Фибоначчи

Рекурсия fib(n-1)+fib(n-2) без памяти — экспонента. Итерация — O(n).

n = int(input())
if n <= 1:
    print(n)
else:
    a, b = 0, 1          # F(0), F(1)
    for _ in range(2, n + 1):
        a, b = b, a + b  # сдвигаем пару вперёд
    print(b)

Пример: n=6 → 8 (0,1,1,2,3,5,8).

10.2. Максимальная сумма подмассива — алгоритм Кадane

Задача: найти подряд идущие элементы с максимальной суммой (массив может содержать отрицательные).

a = list(map(int, input().split()))
best = cur = a[0]
for x in a[1:]:
    cur = max(x, cur + x)    # либо начинаем новый отрезок с x, либо тянем старый
    best = max(best, cur)
print(best)

Пример: -2 1 -3 4 -1 2 1 -5 4 → подмассив [4,-1,2,1] → сумма 6.

Смысл cur: лучшая сумма подмассива, обязательно заканчивающегося на текущем элементе.

10.3. Рюкзак 0/1

Условие: n предметов, у каждого вес w[i] и ценность c[i]; рюкзак вместимости W. Каждый предмет либо один раз, либо никогда.

n, W = map(int, input().split())
w = []
c = []
for _ in range(n):
    wi, ci = map(int, input().split())
    w.append(wi)
    c.append(ci)

dp = [0] * (W + 1)              # dp[cap] — max ценность при весе ≤ cap
for i in range(n):
    for cap in range(W, w[i] - 1, -1):   # обратный порядок — предмет не используют дважды
        dp[cap] = max(dp[cap], dp[cap - w[i]] + c[i])
print(dp[W])

Разбор перехода: для ёмкости cap либо не берём предмет i (dp[cap]), либо берём (dp[cap-w[i]] + c[i]).

Почему cap от W вниз: при прямом порядке один предмет мог бы «засчитаться» несколько раз (это другая задача — полный рюкзак).

10.4. LCS — длина общей подпоследовательности

Подпоследовательность — элементы в том же порядке, но не обязательно подряд. abc и axc → LCS ac, длина 2.

a = input().strip()
b = input().strip()
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[n][m])

Индексы: a[i-1] — i-й символ строки a при 1-based i в цикле.

10.5. Лестница — 1 или 2 ступеньки за шаг

n = int(input())
if n <= 2:
    print(n)
else:
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # пришли с (i-1) или с (i-2)
    print(dp[n])

Пример: n=4 → 5 способов (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2).

Связь с Фибоначчи: те же коэффициents, другие начальные условия.

11. Рекурсия и перебор с возвратом

11.1. Факториал

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

n = int(input())
print(fact(n))

База: fact(1) = 1. Шаг: n! = n * (n-1)!. Без базы рекурсия бесконечна.

11.2. Все перестановки строки

from itertools import permutations

s = input().strip()
for p in sorted(set(permutations(s))):
    print("".join(p))

Осторожно: n! растёт быстро — для n>10 может быть слишком долго.

11.3. Все подмножества через битовую маску

Маска — число от 0 до 2^n - 1; бит i говорит «брать ли элемент a[i]».

n = int(input())
a = list(map(int, input().split()))
for mask in range(1 << n):    # 1 << n = 2**n
    subset = [a[i] for i in range(n) if mask & (1 << i)]
    if subset:
        print(*subset)

Пример: a = [10, 20], маски 01, 10, 11 → {10}, {20}, {10,20}.

mask & (1 << i) — проверка i-го бита маски.

12. Полезные приёмы на экзамене

Сложность по строкам кода

Таблица ниже — кратко. Построчный разбор O(1)…O(n!), трассировка бинарного поиска, ловушки in и pop(0) — в Big-O — шпаргалка с примерами.

Приём	Когда применять	Сложность (типично)
`sort` + два указателя	пары, triplets, слияние	O(n log n)
`Counter` / `defaultdict`	частоты, группировка	O(n)
Префиксные суммы	много запросов суммы на отрезке	O(n + q)
Бинарный поиск по ответу	«минимальное x, при котором…»	O(log R × проверка)
BFS	кратчайший путь без весов	O(V + E)
DFS	острова, лабиринты, компоненты	O(V + E)
DP	оптимум, рюкзак, LCS	зависит от таблицы
`math.gcd`, решето	числа, делимость	O(log n) / O(n log log n)

Граничные случаи — чек-лист перед сдачей

Пустой массив или n = 0
Один элемент
Все числа одинаковые или все отрицательные (Кадane!)
Максимальные значения из условия — не переполнится ли int (в Python редко, но время может)
1-based vs 0-based в ответе
Лишний пробел или перевод строки в выводе

13. Переиспользуемые заготовки

Скопируйте в начало файла на олимпиаде и допишите только solve().

13.1. Быстрый ввод

import sys

input = sys.stdin.readline   # readline быстрее, чем input()

def ints():
    return map(int, input().split())

Важно: после readline() в строке может остаться \n — для int(input()) это не мешает.

13.2. Шаблон «t тестов»

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    return sum(a)

t = int(input())
for _ in range(t):
    print(solve())

Каждый вызов solve() читает свой кусок входа и возвращает строку или число для печати.

13.3. Константы для DP и графов

INF = 10 ** 18       # «бесконечность» для min-путей
NEG_INF = -10 ** 18
MOD = 10 ** 9 + 7    # частый модуль в олимпиадах

При сложении под mod: (a + b) % MOD. При умножении: (a * b) % MOD.

Куда двигаться дальше

Уровень	Материал
Школьная база	Базовая информатика — алгоритмы
Сложность O(n)	Нотация O · шпаргалка Big-O
Сортировка и поиск	глава 2
Графы	глава 4, Дейкстра
Самопроверка	чек-лист алгоритмов
Те же идеи на C++	Олимпиадные шаблоны C++
Отдых от задач	Turtle · Panda3D · Tkinter — окна и виджеты

См. также

Другие статьи этого же раздела в боковом меню (как на странице "О разделе").

Для кого эта статья​

Краткий указатель по разделам​

Основы решения задач на Python​

Обязательный каркас​

Шаблон A — одно число​

Шаблон B — массив из n чисел (две строки входа)​

Шаблон C — все числа в одной строке (без n)​

Стартовые задачи​

Сумма двух чисел​

Количество чётных в списке​

Максимум и индекс (нумерация с 1)​

FizzBuzz до n​

Примеры алгоритмов​

1. Ввод-вывод и ускорение​

1.1. Пакетное чтение через sys.stdin​

1.2. Вывод массива одной строкой​

1.3. Несколько тестов в одном запуске​

2. Перебор, условия и вложенные циклы​

2.1. Подсчёт пар с суммой k​

2.2. Есть ли тройка с суммой 0​

2.3. Поиск символа на поле (двумерный массив)​

3. Словари, множества и частоты​

3.1. Подсчёт вхождений каждого числа​

3.2. Пара с суммой k за O(n)​

3.3. Первый неповторяющийся символ​

3.4. Пересечение двух списков​

4. Сортировка и поиск​

4.1. Сортировка и параметр key​

4.2. k-й по величине элемент​

4.3. Бинарный поиск в отсортированном массиве​

4.4. Бинарный поиск по ответу​

5. Префиксные суммы и разностные массивы​

5.1. Сумма на отрезке [l, r] за O(1)​

5.2. Много запросов к массиму 0/1​

5.3. Разностный массив — много «прибавить v на отрезке [l, r]»​

6. Два указателя​

6.1. Палиндром​

6.2. Слияние двух отсортированных списков​

6.3. Скользящее окно — длиннейший подмассив с суммой ≤ k​

7. Числа и классика​

7.1. НОД и НОК​

7.2. Алгоритм Евклида вручную​

7.3. Решето Эратосфена — все простые до n​

7.4. Быстрое возведение в степень по модулю​

8. Строки​

8.1. Разворот строки​

8.2. Анаграмма — те же буквы в другом порядке​

8.3. Поиск подстроки​

8.4. Разбиение CSV-подобной строки​

9. Графы — сетка, BFS и DFS​

9.1. DFS — сколько проходимых клеток​

9.2. BFS — кратчайший путь в лабиринте​

9.3. Граф как списки соседей — DFS итеративно​

10. Динамическое программирование​

10.1. Числа Фибоначчи​

10.2. Максимальная сумма подмассива — алгоритм Кадane​

10.3. Рюкзак 0/1​

10.4. LCS — длина общей подпоследовательности​

10.5. Лестница — 1 или 2 ступеньки за шаг​

11. Рекурсия и перебор с возвратом​

11.1. Факториал​

11.2. Все перестановки строки​

11.3. Все подмножества через битовую маску​

12. Полезные приёмы на экзамене​

13. Переиспользуемые заготовки​

13.1. Быстрый ввод​

13.2. Шаблон «t тестов»​

13.3. Константы для DP и графов​

Куда двигаться дальше​

Связанные темы

См. также

📄️Готовые решения

📄️Простой консольный чат на CSharp

📄️HTML + CSS — готовые макеты

📄️Примеры фигур Turtle на Python

📄️Примеры фигур Panda3D на Python

📄️Docker Compose — готовые стеки

📄️Nginx — конфиги под задачу

📄️Dockerfile — 10 типовых образов

📄️Prometheus + Grafana — запросы

Для кого эта статья

Краткий указатель по разделам

Основы решения задач на Python

Обязательный каркас

Шаблон A — одно число

Шаблон B — массив из n чисел (две строки входа)

Шаблон C — все числа в одной строке (без n)

Стартовые задачи

Сумма двух чисел

Количество чётных в списке

Максимум и индекс (нумерация с 1)

FizzBuzz до n

Примеры алгоритмов

1. Ввод-вывод и ускорение

1.1. Пакетное чтение через `sys.stdin`

1.2. Вывод массива одной строкой

1.3. Несколько тестов в одном запуске

2. Перебор, условия и вложенные циклы

2.1. Подсчёт пар с суммой k

2.2. Есть ли тройка с суммой 0

2.3. Поиск символа на поле (двумерный массив)

3. Словари, множества и частоты

3.1. Подсчёт вхождений каждого числа

3.2. Пара с суммой k за O(n)

3.3. Первый неповторяющийся символ

3.4. Пересечение двух списков

4. Сортировка и поиск

4.1. Сортировка и параметр `key`

4.2. k-й по величине элемент

4.3. Бинарный поиск в отсортированном массиве

4.4. Бинарный поиск по ответу

5. Префиксные суммы и разностные массивы

5.1. Сумма на отрезке [l, r] за O(1)

5.2. Много запросов к массиму 0/1

5.3. Разностный массив — много «прибавить v на отрезке [l, r]»

6. Два указателя

6.1. Палиндром

6.2. Слияние двух отсортированных списков

6.3. Скользящее окно — длиннейший подмассив с суммой ≤ k

7. Числа и классика

7.1. НОД и НОК

7.2. Алгоритм Евклида вручную

7.3. Решето Эратосфена — все простые до n

7.4. Быстрое возведение в степень по модулю

8. Строки

8.1. Разворот строки

8.2. Анаграмма — те же буквы в другом порядке

8.3. Поиск подстроки

8.4. Разбиение CSV-подобной строки

9. Графы — сетка, BFS и DFS

9.1. DFS — сколько проходимых клеток

9.2. BFS — кратчайший путь в лабиринте

9.3. Граф как списки соседей — DFS итеративно

10. Динамическое программирование

10.1. Числа Фибоначчи

10.2. Максимальная сумма подмассива — алгоритм Кадane

10.3. Рюкзак 0/1

10.4. LCS — длина общей подпоследовательности

10.5. Лестница — 1 или 2 ступеньки за шаг

11. Рекурсия и перебор с возвратом

11.1. Факториал

11.2. Все перестановки строки

11.3. Все подмножества через битовую маску

12. Полезные приёмы на экзамене

13. Переиспользуемые заготовки

13.1. Быстрый ввод

13.2. Шаблон «t тестов»

13.3. Константы для DP и графов

Куда двигаться дальше