Python для ЕГЭ по информатике: шаблоны решений

На ЕГЭ можно писать на C#, C++, Pascal, Java или Python. Python выбирают чаще всего: программы короче, а в стандартной библиотеке есть всё, что нужно для экзамена. Ниже — шаблоны, которые покрывают большую часть «программных» заданий.

Какие задания решают программой

• Обязательно программой: 16 (рекурсия), 17, 24, 25, 26, 27 (большие файлы и перебор).
• Удобно программой, хотя можно и руками: 2, 5, 6, 8, 12, 14, 15, 19–21, 23 — короткий перебор быстрее и надёжнее расчёта на бумаге.
• Без программы: 1, 4, 7, 11, 13 и задания с таблицами (3, 9, 18, 22 решают в электронных таблицах).

Чтение файла (17, 26)

a = [int(x) for x in open('17.txt')]
count, best = 0, -10**9
for x, y in zip(a, a[1:]):        # пары соседних элементов
    if x % 3 == 0 or y % 3 == 0:
        count += 1
        best = max(best, x + y)
print(count, best)

Перебор слов (8)

from itertools import product
cnt = 0
for w in product('КОДЕР', repeat=5):
    if w.count('К') == 2:
        cnt += 1
print(cnt)

Рекурсия с запоминанием (16, 19–21, 23)

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def f(n):
    if n < 3:
        return n
    return f(n - 1) + 2 * f(n - 2)

print(f(100))

lru_cache запоминает уже вычисленные значения, и рекурсия, которая без него считалась бы часами, отрабатывает мгновенно. Тот же приём решает задачи на количество программ (23) и теорию игр (19–21).

Строки (24)

s = open('24.txt').read().strip()
best = cur = 1
for a, b in zip(s, s[1:]):
    cur = cur + 1 if a != b else 1   # длина текущей цепочки
    best = max(best, cur)
print(best)

Системы счисления (14)

x = 4**2020 + 2**2017 - 15
print(bin(x).count('1'))           # двоичная запись
print(int('FF', 16), int('777', 8))  # перевод в десятичную

Что выучить в первую очередь

• Целочисленное деление // и остаток %, функции bin, int(s, p).
• Перебор с itertools.product и permutations.
• Чтение файла в список, сортировка sorted, срезы.
• lru_cache и sys.setrecursionlimit для рекурсии.

Решать эти задания на реальных файлах можно в разделе «Тренировка» — к каждому заданию приложен файл для скачивания. Подробнее о формате экзамена — как проходит компьютерный ЕГЭ.