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

Приветствую! Здесь вы наверняка найдете, что ищете. Примеры в лаборатории рассчитаны на то, что мы разбираем что-то конкретное.

Текущая статья посвящена готовым примерам кода на Python для ЕГЭ и школьных олимпиад — ввод-вывод, перебор, графы, ДП.

Поэтому за теорией по текущей теме вам — в энциклопедию. Если ещё не погружались, то маршрут прост:

1. Основы
2. Система и сеть
3. Данные и разметка
4. Код и разработка
5. Языки
6. Искусственный интеллект
7. Проект
8. Инфраструктура и безопасность
9. Спин-офф

Обязательно пройдитесь.

А теперь приступим к нашему предмету.

---

Навигация по примерам

Раздел	Тема
Каркас ввода-вывода	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

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

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

Достаточно стандартной библиотеки: списки, словари, множества, 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, inputsplit()))
print(sum(a))

Пример:

Вход:
5
3 1 4 1 5

Выход:
14

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

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

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

---

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

a = list(map(int, inputsplit()))
print(max(a))

Пример:

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

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

---

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

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

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

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

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

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

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

---

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

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

n = int(input())
a = list(map(int, inputsplit()))
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, inputsplit()))
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.readsplit()   # все токены подряд в списке строк
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, inputsplit()))
    print(sum(a))

Пример:

2
3
1 2 3
2
10 20

Выход:

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, inputsplit()))
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³). Подходит только для маленьких массивов.

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

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

---

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

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

rows, cols = map(int, inputsplit())
field = [inputstrip() for _ in range(rows)]   # список строк — «строки таблицы»
target = inputstrip()
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 [inputstrip() for _ in range(rows)] читает rows строк подряд.

---

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

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

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

from collections import Counter

a = list(map(int, inputsplit()))
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, inputsplit()))
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 = inputstrip()
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, inputsplit()))
b = set(map(int, inputsplit()))
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, inputsplit()))
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. Бинарный поиск в отсортированном массиве

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

Пример: 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, inputsplit()))
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, inputsplit())   # 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 inputsplit()]
pref = [0]
for x in a:
    pref.append(pref[-1] + x)

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

---

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

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

n, q = map(int, inputsplit())
diff = [0] * (n + 2)          # +2 — чтобы diff[r+1] не вышел за границу
for _ in range(q):
    l, r, v = map(int, inputsplit())
    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 = inputstriplower()   # 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 — сравниваем «головы» двух списков, меньший забираем в результат.

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

---

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

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

a = list(map(int, inputsplit()))
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, inputsplit())
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, inputsplit())
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, inputsplit())
print(pow_mod(a, n, mod))

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

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

---

8. Строки

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

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

Пример: python → nohtyp.

---

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

from collections import Counter

a = inputstriplower()
b = inputstriplower()
print("yes" if Counter(a) == Counter(b) else "no")

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

---

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

text = inputstrip()
sub = inputstrip()
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 = inputstrip()
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 (обход в глубину): идём вперёд, пока можно; # — стена, . — проход.

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

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

---

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

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

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

---

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

Пример: треугольник 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, inputsplit()))
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, inputsplit())
w = []
c = []
for _ in range(n):
    wi, ci = map(int, inputsplit())
    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 = inputstrip()
b = inputstrip()
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 = inputstrip()
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, inputsplit()))
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. Полезные приёмы на экзамене

Приём	Когда применять	Сложность (типично)
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)

---

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

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

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

import sys

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

def ints():
    return map(int, inputsplit())

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

---

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

def solve():
    n = int(input())
    a = list(map(int, inputsplit()))
    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 — окна и виджеты

---