Короткие заготовки по заданиям: меняете условие и данные — получаете ответ. Каждый шаблон запускается прямо здесь на файле-примере. Разбор всех типов задания с решением — на страницах заданий, формулы — в теории.
01
Таблица истинности: какой столбец какой переменной
Переписываете функцию из условия и фрагмент таблицы, программа перебирает порядок столбцов. Импликация a → b — это a <= b, эквивалентность — a == b.
Python
from itertools import permutations, product
def F(x, y, z, w):
return ((x <= y) and not z) or w # (x → y) ∧ ¬z ∨ w
# Фрагмент таблицы из условия; None — пустая клетка
frag = [
[0, None, None, None],
[0, 1, None, 0],
[1, 0, None, 1],
]
value = 0 # значение F в строках фрагмента
rows = [r for r in product((0, 1), repeat=4) if F(*r) == value]
for order in permutations('xyzw'):
for chosen in permutations(rows, len(frag)):
if all(v is None or row['xyzw'.index(order[j])] == v
for f_row, row in zip(frag, chosen)
for j, v in enumerate(f_row)):
print(''.join(order))
break
Перебор N с построением записи по правилу из условия. Правило меняется от варианта к варианту, перебор и перевод — нет; to_base нужна, если запись не двоичная.
Python
def to_base(n, base):
digits = ''
while n > 0:
digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[n % base] + digits
n //= base
return digits or '0'
for n in range(1, 1000):
b = bin(n)[2:] # или to_base(n, 3)
# правило из условия: например, дважды дописать
# справа остаток от деления суммы цифр на 2
for _ in range(2):
b += str(b.count('1') % 2)
r = int(b, 2)
if r > 130: # условие на R
print(n) # наименьшее N
break
Программу Черепахи переписываете командами turtle и умножаете длины на масштаб k. Точки в целых узлах помогают посчитать ответ по рисунку — в песочнице он появится под выводом.
Python
from turtle import *
tracer(0) # рисовать сразу, без анимации
k = 20 # масштаб: единица условия — 20 точек экрана
left(90) # голова Черепахи — вдоль оси ординат
for i in range(2):
forward(8 * k); right(90); forward(12 * k); right(90)
# точки в целых узлах вокруг фигуры
up()
for x in range(-2, 15):
for y in range(-2, 11):
goto(x * k, y * k)
dot(3)
done()
Вывода нет — в песочнице под кодом появится рисунок.
product перебирает слова в алфавитном порядке, если буквы в строке уже отсортированы. Номер слова — счётчик enumerate с единицы.
Python
from itertools import product
letters = sorted('КОРТ') # алфавитный порядок
count = 0
first = None
for number, w in enumerate(product(letters, repeat=4), start=1):
word = ''.join(w)
if word[0] != 'Р' and word.count('О') == 1:
count += 1
if first is None:
first = number
print(count, first)
Пока (нашлось) и Если (нашлось) — это while и if с in, заменить(v, w) — replace с третьим аргументом 1: Редактор заменяет только первое вхождение.
Python
s = '1' + '8' * 80
while '18' in s or '288' in s or '3888' in s:
if '18' in s:
s = s.replace('18', '2', 1)
elif '288' in s:
s = s.replace('288', '3', 1)
else:
s = s.replace('3888', '1', 1)
print(s)
print(sum(int(c) for c in s)) # если спрашивают сумму цифр
Рекурсия: из числа x в y ведёт столько программ, сколько ведёт из результатов каждой команды. Обязательная точка — произведение двух счётов, запрещённая — return 0.
Python
from functools import lru_cache
@lru_cache(None)
def ways(x, y):
if x == y:
return 1
if x > y or x == 11: # перелёт или запрещённое число
return 0
return ways(x + 1, y) + ways(x * 2, y) # команды A и B
# от 2 до 20 через 8
print(ways(2, 8) * ways(8, 20))
int(строка, основание) переводит запись в десятичное число при основании до 36. Если основание больше или нужна запись числа, пригодится to_base списком цифр.
Python
ALPHA = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def to_base(n, base):
digits = []
while n > 0:
digits.append(n % base)
n //= base
return digits[::-1] or [0]
# 1) неизвестная цифра x в записях
for v in range(15):
x = ALPHA[v]
total = int('9' + x + '7', 15) + int('1' + x + '4', 15)
if total % 13 == 0:
print(x, total // 13)
break
# 2) сколько цифр 4 в пятеричной записи выражения
n = 5 ** 20 + 4 * 5 ** 7 - 3
print(to_base(n, 5).count(4))
Перебираете A, для каждого проверяете выражение на всех x из достаточно большого диапазона. Подходящие A собираете — ответ наибольшее или наименьшее из них.
Python
def div(n, m):
return n % m == 0
good = []
for A in range(1, 500):
if all(div(x, A) or not div(x, 6) or div(x, 9) for x in range(1, 2000)):
good.append(A)
print(max(good)) # ДЕЛ(x, A) ∨ (ДЕЛ(x, 6) → ДЕЛ(x, 9))
lru_cache запоминает значения, и рекурсия идёт быстро. Глубокую рекурсию считайте снизу вверх: так не упрётесь в предел глубины.
Python
from functools import lru_cache
@lru_cache(None)
def F(n):
if n < 3:
return n
if n % 2 == 0:
return F(n - 1) + n
return F(n - 2) * 2
for i in range(1, 3001): # снизу вверх — без глубокой рекурсии
F(i)
print(F(30) - F(28))
zip(a, a[1:]) даёт пары соседних чисел. Условие пары и что выводить — из условия; минимум или максимум по всей последовательности считаете до цикла.
Python
with open('17.txt') as f:
a = [int(line) for line in f if line.strip()]
big = max(x for x in a if abs(x) % 10 == 5) # наибольший, оканчивающийся на 5
count, best = 0, 0
for x, y in zip(a, a[1:]):
if (x % 3 == 0) != (y % 3 == 0) and x + y < big:
count += 1
best = max(best, x + y)
print(count, best)
В строке файла — ребро «откуда куда вес». Алгоритм Дейкстры с heapq находит расстояния от одной вершины до всех; для неориентированного графа добавьте ребро в обе стороны.
Python
import heapq
from collections import defaultdict
graph = defaultdict(list)
with open('23.txt') as f:
for line in f:
if line.split():
u, v, w = line.split()
graph[int(u)].append((int(v), float(w)))
start, finish = 1, 5
dist = {start: 0.0}
heap = [(0.0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist.get(v, float('inf')):
dist[v] = d + w
heapq.heappush(heap, (d + w, v))
print(int(dist[finish])) # целая часть длины пути
Идёте по строке и держите длину текущей подходящей цепочки: символ подходит — длина растёт, нет — начинается заново. Сложные условия — то же окно с двумя указателями.
Python
with open('24.txt') as f:
s = f.read().strip()
# 1) самая длинная цепочка без двух одинаковых символов рядом
best = cur = 1
for i in range(1, len(s)):
cur = cur + 1 if s[i] != s[i - 1] else 1
best = max(best, cur)
print(best)
# 2) самая длинная подстрока, где Z встречается не больше двух раз
left = zs = best = 0
for right, c in enumerate(s):
zs += c == 'Z'
while zs > 2:
zs -= s[left] == 'Z'
left += 1
best = max(best, right - left + 1)
print(best)
Делители ищутся до корня из числа: вместе с d берётся n // d. Так перебор миллионов чисел укладывается в секунды.
Python
from math import isqrt
def divisors(n):
result = set()
for d in range(2, isqrt(n) + 1): # без 1 и самого числа
if n % d == 0:
result.add(d)
result.add(n // d)
return sorted(result)
found = 0
for n in range(700_000, 10 ** 7):
d = divisors(n)
if len(d) == 4: # ровно четыре нетривиальных делителя
print(n, max(d))
found += 1
if found == 3:
break
В первой строке файла — ограничение и число записей. Сортируете по возрастанию и берёте подряд, пока влезает; второй ответ — замена последнего взятого на самый большой, который ещё влезает.
Python
with open('26.txt') as f:
s, n = map(int, f.readline().split())
a = sorted(int(f.readline()) for _ in range(n))
count = total = 0
for x in a:
if total + x > s:
break
total += x
count += 1
free = s - (total - a[count - 1]) # место без последнего взятого
biggest = max(x for x in a[count - 1:] if x <= free)
print(count, biggest)
Точки делятся на кластеры обходом: в один кластер попадают точки ближе порога друг к другу. Центр — точка с наименьшей суммой расстояний до остальных точек кластера.
Python
from math import dist
with open('27.txt') as f:
points = [tuple(map(float, line.replace(',', '.').split()))
for line in f if line.split()]
# обход: соседи ближе порога — в одном кластере
clusters, left = [], set(range(len(points)))
while left:
stack = [left.pop()]
cluster = []
while stack:
i = stack.pop()
cluster.append(points[i])
near = [j for j in left if dist(points[i], points[j]) < 2]
left -= set(near)
stack += near
clusters.append(cluster)
centers = [min(c, key=lambda p: sum(dist(p, q) for q in c)) for c in clusters]
px = sum(c[0] for c in centers) / len(centers)
py = sum(c[1] for c in centers) / len(centers)
print(int(px * 10000), int(py * 10000))
Да. На станции КЕГЭ стоят среды для C#, C++, Pascal, Java и Python, язык выбираете сами. Проверяют только ответ: код никто не смотрит.
Можно ли принести свои шаблоны на экзамен?
Нет: на станции нет ни интернета, ни своих файлов. Шаблоны нужно помнить — поэтому они короткие. Прорешайте каждый на нескольких заданиях, и к экзамену он будет писаться по памяти.
Чем шаблон отличается от решения на странице задания?
Шаблон — общая заготовка для типа задания: меняете условие и данные, остальное остаётся. На странице задания — разбор каждого типа с полным решением и тренажёр с проверкой ответа.
Нужны ли сторонние библиотеки?
Нет. Все шаблоны используют только стандартную библиотеку Python: itertools, functools, math, heapq, fnmatch, turtle — они есть и на станции КЕГЭ.