Вариант 9 · Июль 2026

Решение:
Проанализировав схему, видим, что пункт E является уникальным узлом со степенью 4, следовательно, в таблице ему соответствует строка под номером 3. В силу симметрии графа пары вершин A и D, B и G, а также C и F являются взаимозаменяемыми. Допустим, что пункты A и D — это номера 1 и 4 (поскольку только эти точки не связаны напрямую с вершиной E). Исходя из этого, для G и B остаются позиции 7 и 6 (или наоборот). Следовательно, вершинам C и F будут соответствовать номера 2 и 5 (или в обратном порядке — 5 и 2).

Ответ: 25

Источник: ФИПИ

Решение:

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

Дизъюнкция $( y \rightarrow \neg ( x \rightarrow w ) ) \lor z$ равна нулю, когда $z = 0$ и ложна импликация $y \rightarrow \neg ( x \rightarrow w )$, то есть $y = 1$ и $\neg ( x \rightarrow w ) = 0$. Последнее равносильно $x \rightarrow w = 1$ и запрещает пару $x = 1,\ w = 0$. Остаются три набора:

w	x	y	z	F
0	0	1	0	0
1	0	1	0	0
1	1	1	0	0

На всех наборах $y = 1$ и $z = 0$, поэтому в столбце $y$ нет нулей, а в столбце $z$ нет единиц. В фрагменте нули стоят в первом, втором и четвёртом столбцах, откуда $y$ — третий столбец; единицы стоят в первом и втором столбцах, откуда $z$ — четвёртый. В третьей строке фрагмента первый столбец равен 0, а второй равен 1, то есть переменные $w$ и $x$ принимают там разные значения, а это единственный набор $w = 1,\ x = 0$. Значит первый столбец — $x$, второй — $w$.

Те же три набора нетрудно получить и перебором:

from itertools import product


def impl(a, b):
    return (not a) or b


def F(w, x, y, z):
    return impl(y, not impl(x, w)) or z


for w, x, y, z in product((0, 1), repeat=4):
    if not F(w, x, y, z):
        print(w, x, y, z)

Ответ: xwyz

Решение:

Количество упаковок в наличии растёт при поступлении и уменьшается при продаже, поэтому искомое увеличение равно разности суммарного поступления и суммарной продажи.

Шаг 1. В таблице «Магазин» отбираем магазины Заречного района и выписываем их ID магазина (их четыре).

Шаг 2. В таблице «Товар» находим строку «Яйцо диетическое» и запоминаем её артикул.

Шаг 3. В таблице «Движение товаров» оставляем строки с этим артикулом и магазинами из шага 1. Все записи файла относятся к первой декаде июня, поэтому дополнительный фильтр по дате ничего не отсекает.

Шаг 4. Двумя формулами СУММЕСЛИМН считаем сумму столбца «Количество упаковок, шт.» отдельно по типу операции «Поступление» и по типу «Продажа»: 1420 и 454 упаковки. Увеличение: $1420 - 454 = 966$ упаковок.

Ответ: 966

Решение:

Известно: Л — 00, М — 01, Н — 11. Кодовые слова нужно подобрать сразу для двух букв — П и Р, и обе они должны попасть в свободную часть дерева.

Ветвь 0 занята целиком (слова 00 и 01), в ветви 1 занято слово 11. Свободна единственная вершина — 10.

Само слово 10 условию задачи не противоречит, но если отдать его букве П, то для буквы Р места не останется: все слова, начинающиеся с 10, окажутся продолжением слова П, а остальные ветви уже заняты. Поэтому вершину 10 нужно разбить надвое: 100 и 101.

Значит, кратчайшая возможная длина кодового слова для буквы П равна 3, а из двух вариантов 100 и 101 выбираем меньший по числовому значению.

Ответ: 100

Решение:

Пусть $r=N\bmod 4$ — последняя цифра четверичной записи $N$. Разберём, что приписывается справа в каждом случае.

• $r=0$: приписываются две последние четверичные цифры, то есть запись удлиняется на два разряда, а приписанное значение равно $N\bmod 16$. Значит $R=16N+(N\bmod 16)$.
• $r=1$: $2r=2=2_4$ — один разряд, поэтому $R=4N+2$.
• $r=2$: $2r=4=10_4$ — два разряда, поэтому $R=16N+4$.
• $r=3$: $2r=6=12_4$ — два разряда, поэтому $R=16N+6$.

Сверим с примерами из условия: $N=11$, $r=3$, $R=16\cdot 11+6=182$; $N=12$, $r=0$, $R=16\cdot 12+12=204$. Совпадает.

Ключевое наблюдение: только при $r=1$ число увеличивается в 4 раза, во всех остальных случаях — в 16 раз.

Нужно наименьшее $N$, при котором $R\ge 1088$. Рассмотрим все четыре случая.

• $r=1$: $4N+2\ge 1088\Rightarrow N\ge 272$. Наименьшее число вида $4k+1$ — это $N=273$.
• $r=2$: $16N+4\ge 1088\Rightarrow N\ge 68$. Наименьшее число вида $4k+2$ — это $N=70$, $R=1124$.
• $r=3$: $16N+6\ge 1088\Rightarrow N\ge 68$. Наименьшее число вида $4k+3$ — это $N=71$, $R=1142$.
• $r=0$: $N=64$ даёт $R=1024$ — мало; следующее кратное четырём $N=68$ даёт $R=16\cdot 68+4=1092\ge 1088$ — подходит.

Обратим внимание на «ловушку»: $N=66$ даёт $R=1060$, а $N=67$ даёт $R=1078$ — оба меньше 1088. Наименьшее из чисел 273, 70, 71, 68 — это 68.

def alg(n):
    q = ''
    m = n
    while m:
        q = str(m % 4) + q
        m //= 4
    if n % 4 == 0:
        q += q[-2:]
    else:
        t = (n % 4) * 2
        q += str(t) if t < 4 else str(t // 4) + str(t % 4)
    return int(q, 4)

print(min(n for n in range(1, 1000) if alg(n) >= 1088))

Ответ: 68

Решение:

Хвост поднят, поэтому Вперёд 100 Направо 90 Вперёд 100 ничего не рисует — Черепаха просто оказывается в точке $(100;100)$. После Направо 45 голова смотрит под углом $-45^{\circ}$ к оси $Ox$, и хвост опускается.

Цикл Повтори 10 [Вперёд 30 Направо 90] замыкается уже за 4 команды: рисуется квадрат со стороной 30, повёрнутый на $45^{\circ}$, с вершинами $(100;100)$, $(100+15\sqrt{2};\,100-15\sqrt{2})$, $(100;\,100-30\sqrt{2})$, $(100-15\sqrt{2};\,100-15\sqrt{2})$.

У такого квадрата одна диагональ горизонтальна, другая вертикальна, а стороны имеют угловые коэффициенты $\pm 1$. Поэтому точка лежит строго внутри тогда и только тогда, когда $|x-100|+|y-c|\lt 15\sqrt{2}$, где $c=100-15\sqrt{2}$ — ордината центра.

Обозначим $t=100-y$; условие превращается в $|x-100|+\bigl|15\sqrt{2}-t\bigr|\lt 15\sqrt{2}$:

• при $t\le 15\sqrt{2}\approx 21{,}21$, то есть $t=1,\dots,21$, получаем $|x-100|\lt t$ — ровно $2t-1$ точек;
• при $t\gt 15\sqrt{2}$, то есть $t=22,\dots,42$, получаем $|x-100|\lt 30\sqrt{2}-t\approx 42{,}43-t$ — ровно $85-2t$ точек.

$\sum\limits_{t=1}^{21}(2t-1)=21^{2}=441$ и $\sum\limits_{t=22}^{42}(85-2t)=41+39+\dots+1=21^{2}=441$.

Всего $441+441=882$. Проверим программой:

from math import sin, cos, radians

P = [(0.0, 0.0)]
x = y = 0.0
a = 90.0                      # голова смотрит вдоль оси Oy

def F(n):                     # Вперёд n
    global x, y
    x = round(x + n * cos(radians(a)), 9)   # round убирает шум float
    y = round(y + n * sin(radians(a)), 9)
    P.append((x, y))

def R(m):                     # Направо m
    global a
    a -= m

F(100); R(90); F(100); R(45)  # хвост поднят - это не рисуется
P = [(x, y)]                  # опустили хвост
for i in range(4):            # квадрат замыкается за 4 команды
    F(30); R(90)

def inside(px, py):           # фигура выпуклая, обход по часовой стрелке
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        if (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1) >= -1e-9:
            return False      # точка на линии или снаружи
    return True

xs = [p[0] for p in P]; ys = [p[1] for p in P]
print(sum(inside(px, py)
          for px in range(int(min(xs)) - 1, int(max(xs)) + 2)
          for py in range(int(min(ys)) - 1, int(max(ys)) + 2)))

Ответ: 882

Решение:

В палитре 8192 цвета, а $8192 = 2^{13}$, значит на один пиксель отводится 13 бит.

Объём одной фотографии: $1024 \cdot 960 \cdot 13 = 12\,779\,520$ бит.

Объём пакета из 160 снимков: $12\,779\,520 \cdot 160 = 2\,044\,723\,200$ бит.

Скорость передачи $14\,680\,064 = 14 \cdot 2^{20}$ бит/с, поэтому время передачи пакета равно $$t = \frac{2\,044\,723\,200}{14\,680\,064} = \frac{1950}{14} = \frac{975}{7} \approx 139{,}29 \text{ с.}$$

Целая часть полученного числа — 139.

print(1024 * 960 * 13 * 160 // 14680064)

Ответ: 139

Решение:

Условие означает: среди четырёх цифр числа есть пара одинаковых, стоящих рядом, а две оставшиеся цифры отличаются и друг от друга, и от цифры этой пары (иначе одинаковых цифр было бы больше двух). Пара может занимать позиции 1–2, 2–3 или 3–4.

• Позиции 1–2. Повторяющаяся цифра $d$ стоит первой, поэтому $d \ne 0$ — 9 вариантов. На 3-ю и 4-ю позиции ставим две различные цифры, отличные от $d$: $9 \cdot 8 = 72$ варианта. Итого $9 \cdot 72 = 648$.
• Позиции 2–3. Если $d = 0$, то первая цифра — любая из 9 ненулевых, последняя — любая из 8 оставшихся: $9 \cdot 8 = 72$. Если $d \ne 0$ (9 вариантов), первая цифра ненулевая и не равна $d$ — 8 вариантов, последняя не равна ни $d$, ни первой — тоже 8: $9 \cdot 8 \cdot 8 = 576$. Итого $72 + 576 = 648$.
• Позиции 3–4. Рассуждение полностью симметрично предыдущему: тоже 648.

Всего $3 \cdot 648 = 1944$.

from collections import Counter

count = 0
for n in range(1000, 10000):
    s = str(n)
    c = Counter(s)
    if sorted(c.values()) != [1, 1, 2]:
        continue
    d = [k for k in c if c[k] == 2][0]
    if any(s[i] == s[i + 1] == d for i in range(3)):
        count += 1
print(count)

Ответ: 1944

Решение:

В файле 6400 строк, в каждой шесть натуральных чисел. Строка подходит, если выполнены оба условия:

• ровно одно значение встречается в строке ровно два раза, а остальные четыре числа попарно различны — то есть среди шести чисел ровно одно «двойное» и ровно четыре «одиночных»;
• среднее арифметическое четырёх неповторяющихся чисел не превосходит суммы повторяющихся чисел; повторяющееся число $x$ стоит дважды, поэтому их сумма равна $2x$.

Проще всего перебрать строки программой, подсчитывая, сколько раз встречается каждое число (класс Counter):

import csv
from collections import Counter

count = 0
for row in csv.reader(open('data.csv'), delimiter=';'):
    nums = [int(x) for x in row]
    c = Counter(nums)
    twice = [v for v, k in c.items() if k == 2]   # значения, встречающиеся 2 раза
    once = [v for v, k in c.items() if k == 1]    # значения, встречающиеся 1 раз
    if len(twice) == 1 and len(once) == 4:
        if sum(once) / 4 <= 2 * twice[0]:
            count += 1
print(count)   # 2241

Условие len(twice) == 1 and len(once) == 4 как раз и означает «ровно одно число повторяется ровно два раза, остальные различны»: оно отбрасывает строки, где какое-то число встречается три и более раз или где повторяющихся пар несколько. Программа находит 2241 подходящую строку. Ответ: 2241

Решение:

Открываем файл и выделяем текст VII главы — фрагмент от заголовка «VII» до заголовка следующей главы.

Нужны вхождения сочетания букв, которые не являются отдельным словом, поэтому считаем в два приёма.

1. Ищем «шарик» без учёта регистра и с выключенным «Только слово целиком» — все вхождения сочетания букв: 41.
2. Тот же поиск с включённым «Только слово целиком»: отдельное слово «шарик»/«Шарик» в этой главе не встречается ни разу — 0 (пёс здесь уже стал Шариковым).

Итого внутри других слов: $41-0=41$. Это «Шариков» (31 раз), «Шарикова» (7), «Шарикову» (2), «Шариковский» (1).

Проверка программой (глава сохранена в текстовый файл):

import re

text = open('glava7.txt', encoding='utf-8').read()
vsego = len(re.findall('шарик', text)) + len(re.findall('Шарик', text))
otdelno = len(re.findall(r'\bшарик\b', text)) + len(re.findall(r'\bШарик\b', text))
print(vsego - otdelno)

Программа печатает 41.Ответ: 41

Решение:

Пароль набирается из 36-символьного набора цифр и строчных латинских букв, значит мощность алфавита составляет $36$ символов. На один символ нужно минимальное целое $i$, при котором $2^i \ge 36$. Так как $2^{5} = 32 \lt 36 \lt 64 = 2^{6}$, получаем $i = 6$ бит.

Один пароль из 9 символов занимает $9 \cdot 6 = 54$ бита. Число байт должно быть целым и минимальным: $54 = 8 \cdot 6 + 6$, поэтому под него отводится 7 байт.

На всех пользователей отведено одинаковое число байт, поэтому на одного пользователя приходится $400 : 20 = 20$ байт.

Из них 7 байт занимает пароль, значит на дополнительные сведения остаётся $20 - 7 = 13$ байт.

import math

N = 36                        # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(9 * i / 8)      # байт на пароль
print(400 // 20 - b)          # доп. сведения, байт

Ответ: 13

Решение:

Символ «>» работает как указатель, который движется по строке слева направо. Каждая замена берёт цифру, стоящую сразу за указателем, и записывает результат слева от «>», то есть обработанная часть строки больше не меняется:

• >0 → 22> : цифра 0 заменяется на две двойки, вклад в сумму 4;
• >1 → 2> : цифра 1 заменяется на двойку, вклад 2;
• >2 → 1> : цифра 2 заменяется на единицу, вклад 1.

Каждая цифра исходной строки обрабатывается ровно один раз, поэтому порядок цифр не важен, а сумма цифр результата равна $$15 \cdot 4 + n \cdot 2 + 15 \cdot 1 = 75 + 2n.$$

Осталось перебрать $n$: при $n=1$ сумма $77 = 7 \cdot 11$ — составное число; при $n=2$ сумма $79$ — простое. Наименьшее подходящее значение $n = 2$.

def zamenit(s, v, w):
    return s.replace(v, w, 1)   # первое слева вхождение

def prostoe(x):
    d = 2
    while d * d <= x:
        if x % d == 0:
            return False
        d += 1
    return x > 1

def rabota(s):
    while ">0" in s or ">1" in s or ">2" in s:
        if ">0" in s:
            s = zamenit(s, ">0", "22>")
        if ">1" in s:
            s = zamenit(s, ">1", "2>")
        if ">2" in s:
            s = zamenit(s, ">2", "1>")
    return s

n = 1
while True:
    s = rabota(">" + "0" * 15 + "1" * n + "2" * 15)
    summa = sum(int(c) for c in s if c != ">")
    if prostoe(summa):
        print(n, summa)   # 2 79
        break
    n += 1

Ответ: 2

Решение:

Маска 255.255.224.0 — это 11111111.11111111.11100000.00000000, в ней 19 единиц и 13 нулей. Значит, первые 19 битов адреса закреплены за сетью и берутся из 140.250.64.0, а остальные 13 битов свободны.

Максимум нулей будет, если все свободные биты обнулить, то есть на самом адресе сети. Нули фиксированной части: 140 = 10001100 — 5 нулей, 250 = 11111010 — 2 нуля, а от третьего байта 64 = 01000000 берутся только первые 3 бита 010 — ещё 2 нуля. Итого в фиксированной части 9 нулей, и вместе со всеми свободными битами получаем $9 + 13 = 22$.

def ip(a, b, c, d):
    return ((a * 256 + b) * 256 + c) * 256 + d

base = ip(140, 250, 64, 0)
print(max(format(base + i, '032b').count('0') for i in range(2 ** 13)))   # 22

Ответ: 22

Решение:

Приведём всё к степеням тройки: $9^{800}=3^{1600}$, $81=3^4$. Тогда

$$N = 3^{2020} + 3^{1600} - 3^{1020} - 3^{4}.$$

Разберём запись по разрядам (нумеруем разряды справа, начиная с нулевого).

$3^{1600}-3^{1020} = 3^{1020}\left(3^{580}-1\right)$ — это 580 двоек в разрядах с 1599-го по 1020-й.

Теперь вычитаем $3^4$: заём берётся из младшей двойки (разряд 1020), она становится единицей, а все разряды с 1019-го по 5-й превращаются в двойки; в разряде 4 получается $3-1=2$. Итого двойки стоят в разрядах с 1019-го по 4-й — это 1016 двоек, а разряды 3, 2, 1, 0 нулевые.

Старшая единица $3^{2020}$ остаётся на месте, между ней и разрядом 1599 стоят нули (разряды с 2019-го по 1600-й, их 420).

Итого запись: 1, 420 нулей, 579 двоек, 1, 1016 двоек, 4 нуля. Количество двоек: $579 + 1016 = 1595$.

def to_base(n, b):
    s = ''
    while n:
        s = str(n % b) + s
        n //= b
    return s

n = 3**2020 - 3**1020 + 9**800 - 81
print(to_base(n, 3).count('2'))     # 1595

Ответ: 1595

Решение:

Дизъюнкция ложна только тогда, когда ложны все три её слагаемых. Значит, выражение тождественно истинно ровно тогда, когда не найдётся пары целых неотрицательных $x$ и $y$, для которой одновременно $y \le x$, $x \le 60$ и $x + 2y \ge A$.

Иначе говоря, на всём «опасном» множестве $0 \le y \le x \le 60$ обязано выполняться неравенство $x + 2y \lt A$. Осталось найти наибольшее значение суммы $x + 2y$ на этом множестве. Чем больше $x$, тем больше и допустимое $y$, поэтому максимум достигается в самой «дальней» точке $x = y = 60$ и равен $60 + 2 \cdot 60 = 180$.

Значит, нужно $A \gt 180$, и наименьшее целое такое число — $A = 181$. Проверим: при $A = 181$ в любой точке проверочного множества $x + 2y \le 180 \lt 181$, то есть истинно первое слагаемое; вне этого множества истинно второе ($y \gt x$) или третье ($x \gt 60$) слагаемое. При $A = 180$ выражение ломается на паре $x = y = 60$: там все три скобки ложны.

best = max(x + 2 * y
           for x in range(0, 61)
           for y in range(0, x + 1))
print(best + 1)   # 181

Ответ: 181

Решение:

Сначала найдём $F(2)$, которое входит в правило для нечётных $n$: число 2 чётное и $2 \gt 1$, поэтому $F(2) = 3 \cdot F(1) = 3$. Значит при нечётном $n \gt 1$ правило принимает вид $F(n) = 5n + F(n-1) + 3$.

Каждое значение зависит только от предыдущего, поэтому просто идём по возрастанию $n$:

$F(1) = 1$, $F(2) = 3 \cdot 1 = 3$, $F(3) = 5 \cdot 3 + 3 + 3 = 21$, $F(4) = 3 \cdot 21 = 63$, $F(5) = 5 \cdot 5 + 63 + 3 = 91$, $F(6) = 3 \cdot 91 = 273$ и так далее.

n	F(n)
1	1
2	3
3	21
4	63
5	91
6	273
7	311
8	933
9	981
10	2943
11	3001
12	9003
13	9071
14	27213
15	27291
16	81873
17	81961
18	245883
19	245981
20	737943
21	738051
22	2214153
23	2214271

Последний шаг: $F(23) = 5 \cdot 23 + F(22) + 3 = 115 + 2214153 + 3 = 2214271$.

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n <= 1:
        return 1
    if n % 2 == 1:
        return 5 * n + F(n - 1) + F(2)
    return 3 * F(n - 1)

print(F(23))   # 2214271

Ответ: 2214271

Решение:

Задача решается в два прохода. Сначала находим порог — максимальный элемент всей последовательности, кратный 3; в этом файле он равен 999. Затем перебираем пары соседних элементов и отбираем те, у которых хотя бы одно число делится на 3, а сумма пары не превосходит найденного порога.

Проверка делимости на 3 через остаток в Python корректна и для отрицательных чисел: $x \bmod 3 = 0$ тогда и только тогда, когда $x$ кратно 3.

a = [int(s) for s in open('52900_17.txt')]

m = max(x for x in a if x % 3 == 0)   # 999 - порог

count = 0
best = None
for x, y in zip(a, a[1:]):
    if (x % 3 == 0 or y % 3 == 0) and x + y <= m:
        count += 1
        if best is None or x + y > best:
            best = x + y

print(count, best)   # 2439 998

Подходящих пар 2439, наибольшая из их сумм равна 998 (это меньше порога 999, поэтому условие выполнено).Ответ: 2439 998

Решение:

Робот ходит только вправо и вниз, поэтому в любую клетку он приходит либо сверху, либо слева и ни одной клетки не проходит дважды. Значит, работает динамическое программирование: для каждой клетки достаточно хранить максимальную и минимальную суммы, которые можно накопить, дойдя до неё из левой верхней клетки.

Пусть $a_{ij}$ — номинал монеты в клетке, $M_{ij}$ и $m_{ij}$ — максимальная и минимальная накопленные суммы. Тогда $M_{ij}=\max(M_{i-1,j},\,M_{i,j-1})+a_{ij}$ и $m_{ij}=\min(m_{i-1,j},\,m_{i,j-1})+a_{ij}$, причём соседняя клетка учитывается только тогда, когда между ней и текущей нет стены. Для левой верхней клетки $M_{11}=m_{11}=a_{11}$.

В приложенном файле поле имеет размер $20\times20$, стены показаны утолщёнными линиями. Вертикальные внутренние стены (движение вправо запрещено) стоят:

• между 2-м и 3-м столбцами — в строках 2–8;
• между 4-м и 5-м столбцами — в строках 5–13;
• между 6-м и 7-м столбцами — в строках 10–18;
• между 9-м и 10-м столбцами — в строках 2–9;
• между 12-м и 13-м столбцами — в строках 6–14;
• между 15-м и 16-м столбцами — в строках 9–18.

Горизонтальные внутренние стены (движение вниз запрещено) стоят между 2-й и 3-й строками в столбцах 4–8 и между 17-й и 18-й строками в столбцах 9–14.

Скопируем содержимое таблицы в текстовый файл 18.txt (числа разделены пробелами или знаками табуляции) и обработаем его программой.

f = open('18.txt')
a = [[int(x) for x in s.split()] for s in f]
N = len(a)

# стена снизу от клетки (i, j); строки и столбцы нумеруются с нуля
def wall_down(i, j):
    return (i == 1 and 3 <= j <= 7) or (i == 16 and 8 <= j <= 13)

# стена справа от клетки (i, j)
def wall_right(i, j):
    return ((j == 1 and 1 <= i <= 7) or (j == 8 and 1 <= i <= 8) or
            (j == 3 and 4 <= i <= 12) or (j == 11 and 5 <= i <= 13) or
            (j == 5 and 9 <= i <= 17) or (j == 14 and 8 <= i <= 17))

MX = [[0] * N for i in range(N)]   # максимум, накопленный к клетке
MN = [[0] * N for i in range(N)]   # минимум
for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            MX[i][j] = MN[i][j] = a[0][0]
            continue
        v = []
        if i > 0 and not wall_down(i - 1, j):
            v.append((MX[i - 1][j], MN[i - 1][j]))
        if j > 0 and not wall_right(i, j - 1):
            v.append((MX[i][j - 1], MN[i][j - 1]))
        MX[i][j] = max(x for x, y in v) + a[i][j]
        MN[i][j] = min(y for x, y in v) + a[i][j]

print(MX[N - 1][N - 1], MN[N - 1][N - 1])

Программа выводит 1099 1026: максимальная сумма равна 1099, минимальная — 1026. Ответ: 1099 1026

Решение:

Позиция игры описывается одним числом $s$ — количеством камней в куче. Игрок, который ходит из позиции $s$, выигрывает своим ходом, если хотя бы один его ход сразу даёт кучу в 205 камней или больше.

Ходы: $s\to s+1$, $s\to s+5$ и $s\to 4s$. Игра заканчивается одним ходом, если $s+1\ge205$ ($s\ge204$), или $s+5\ge205$ ($s\ge200$), или $4s\ge205$ ($s\ge51{,}25$, для целого $s$ — $s\ge52$). Значит, из позиции $s\ge52$ ходящий выигрывает одним ходом.

Нужно $S\le51$ (Петя не выигрывает сразу) и одновременно $S+1\ge52$, $S+5\ge52$, $4S\ge52$, то есть $S\ge51$, $S\ge47$ и $S\ge13$. Остаётся $S=51$.

Проверка: из 51 Петя получает 52, 56 или 204 — все не меньше 52, поэтому Ваня заканчивает игру своим ходом. Сам Петя выиграть сразу не мог: $52\lt205$, $56\lt205$, $204\lt205$.

def win1(s):
    return s + 1 >= 205 or s + 5 >= 205 or 4 * s >= 205

for S in range(1, 205):
    if not win1(S) and win1(S + 1) and win1(S + 5) and win1(4 * S):
        print(S)

Ответ: 51

Решение:

Напомним условия игры: перед игроками две кучи камней, за ход можно добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в одной из куч вдвое; игра заканчивается, когда суммарное количество камней в кучах становится не менее $59$. Начальная позиция — $(5,\ S)$, первым ходит Петя.

Позицию будем оценивать с точки зрения игрока, который ходит из неё. Обозначим: В1 — из позиции можно выиграть первым же ходом; П1 — любой ход не заканчивает игру и переводит соперника в В1 (то есть ходящий проигрывает следующим ходом соперника); В2 — позиция не В1, но есть ход, переводящий соперника в П1, то есть ходящий выигрывает ровно вторым своим ходом при любой игре соперника.

$S = 24$. Сразу Петя выиграть не может ($5 + 2\cdot 24 = 53 \lt 59$). Петя удваивает первую кучу — получается позиция $(10,\ 24)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(11,\ 24)$ — Петя удваивает вторую кучу: $11 + 48 = 59$;
• $(10,\ 25)$ — Петя удваивает вторую кучу: $10 + 50 = 60$;
• $(20,\ 24)$ — Петя удваивает вторую кучу: $20 + 48 = 68$;
• $(10,\ 48)$ — Петя добавляет камень: $10 + 49 = 59$.

$S = 26$. Сразу Петя выиграть не может ($5 + 2\cdot 26 = 57 \lt 59$). Петя добавляет камень в первую кучу — получается позиция $(6,\ 26)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(7,\ 26)$ — Петя удваивает вторую кучу: $7 + 52 = 59$;
• $(6,\ 27)$ — Петя удваивает вторую кучу: $6 + 54 = 60$;
• $(12,\ 26)$ — Петя удваивает вторую кучу: $12 + 52 = 64$;
• $(6,\ 52)$ — Петя добавляет камень: $6 + 53 = 59$.

Полный перебор удобнее доверить программе:

N = 59

def moves(p):
    a, b = p
    return [(a + 1, b), (a, b + 1), (2 * a, b), (a, 2 * b)]

def over(p):                 # игра закончена
    return p[0] + p[1] >= N

def win1(p):                 # В1: выигрыш своим первым ходом
    return any(over(q) for q in moves(p))

def lose1(p):                # П1: любой ход отдаёт победу сопернику
    return all(not over(q) and win1(q) for q in moves(p))

def win2(p):                 # В2: выигрыш вторым ходом, но не первым
    return not win1(p) and any(not over(r) and lose1(r) for r in moves(p))

print(*[s for s in range(1, 54) if win2((5, s))][:2])   # два наименьших

Ответ: 24 26

Решение:

Напомним условие игры из задания 19. Перед игроками одна куча камней, игроки ходят по очереди, первым ходит Петя. За один ход игрок может добавить в кучу один или пять камней либо увеличить количество камней в куче в четыре раза. Игра заканчивается в тот момент, когда количество камней в куче становится не менее 105; побеждает тот, кто сделал последний ход. В начальный момент в куче $S$ камней, $1 \le S \le 104$.

Классифицируем позиции (ходит тот, чья очередь):

• $W_1$ — ходящий выигрывает своим первым ходом, то есть одним ходом заканчивает игру;
• $L_1$ — ходящий сразу выиграть не может, а любой его ход отдаёт сопернику позицию из $W_1$; значит, соперник выигрывает своим первым ходом;
• $W_2$ — ходящий сразу выиграть не может, но у него есть ход в $L_1$, поэтому он выигрывает своим вторым ходом;
• $L_2$ — ходящий сразу выиграть не может, и каждый его ход ведёт в $W_1$ или в $W_2$; значит, соперник выигрывает первым или вторым своим ходом.

Первым ходит Петя, поэтому два условия задачи вместе означают: стартовая позиция принадлежит $L_2$, но не принадлежит $L_1$ — иначе Ваня гарантированно выигрывал бы первым ходом. Нужно наименьшее такое $S$. Проще всего перебрать все $S$ программой, вычисляя $W_1$, $L_1$, $W_2$, $L_2$ прямо по этим определениям:

N = 105

def moves(s):
    return [s + 1, s + 5, 4 * s]

def over(s):
    return s >= N

def win1(p):                  # ходящий выигрывает своим первым ходом
    return any(over(q) for q in moves(p))

def lose1(p):                 # соперник выигрывает своим первым ходом
    return not win1(p) and all(win1(q) for q in moves(p))

def win2(p):                  # ходящий выигрывает своим вторым ходом
    return not win1(p) and any(lose1(q) for q in moves(p))

def lose2(p):                 # соперник выигрывает первым или вторым ходом
    return not win1(p) and all(win1(q) or win2(q) for q in moves(p))

for s in range(1, 105):
    if lose2(s) and not lose1(s):
        print(s)
        break

Перебор идёт по возрастанию $S$, поэтому первое напечатанное значение и есть минимальное: $S = 20$. Проверим его вручную. Из стартовой позиции $20$ Петя может получить:

• $21$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $26$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $27$ — в $108$; из $31$ — в $124$; из $104$ — в $105$);
• $25$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $26$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $27$ — в $108$; из $31$ — в $124$; из $104$ — в $105$);
• $80$ — Ваня выигрывает сразу: одним ходом он получает $320$, а это уже не меньше 105.

Значит, при любой игре Пети Ваня выигрывает первым или вторым ходом. Гарантировать выигрыш именно первым ходом он не может: Пете достаточно сделать тот ход, после которого Ване приходится тратить второй ход. Оба условия выполнены.

Ответ: 20

Решение:

В файле 14 процессов с идентификаторами 101–114. Зависимости распадаются на две не связанные между собой группы:

• 101 и 102 → 103 → 104 и 105; 104 → 106; 105 и 106 → 107 → 108 (длительности 4, 3, 1, 5, 7, 3, 1, 2 мс);
• 109 → 111 и 114; 111 и 114 → 113; независимый 110 → 112 (длительности 8, 16, 14, 14, 6, 5 мс).

Приостанавливать начатый процесс нельзя, но начинать процесс позже, чем он стал доступен, никто не запрещает — в задании спрашивается, какая длительность одновременной работы пяти процессов возможна. Поэтому цепочку зависимых процессов удобно считать одной непрерывной «лентой»: внутри цепочки процессы идут вплотную друг за другом, а сами ленты можно двигать по времени.

Сколько процессов вообще могут работать одновременно? Одновременно могут выполняться только попарно независимые процессы. В первой группе любые три процесса обязательно связаны цепочкой зависимостей, независимых пар всего три (104 и 105, 105 и 106, 101 и 102) — значит, оттуда одновременно работают не более двух процессов. Во второй группе 109 предшествует 111 и 114, а 113 следует за ними, из пары 110 и 112 второй зависит от первого; максимум независимых процессов здесь — три (например, 111, 114 и 110). Итого одновременно могут идти не более $2 + 3 = 5$ процессов, то есть пятёрка процессов — это ровно две «ленты» первой группы и три «ленты» второй.

Вторая группа три непрерывные ленты держит долго: сразу после 109 (8 мс) параллельно запускаются 111 (16 мс) и 114 (14 мс), а третью ленту даёт цепочка 110 → 112 ($6 + 5 = 11$ мс). Ограничения нет: $\min(16, 14, 11) = 11$ мс.

Первая группа — узкое место. После 103 параллельно могут идти только 104 и 105. Первая лента — цепочка 104 → 106 ($5 + 3 = 8$ мс), вторая лента — процесс 105 (7 мс). Продлить вторую ленту нечем: следующий за 105 процесс 107 требует ещё и завершения 106, а 106 заканчивается на 1 мс позже, чем 105, — на стыке лента простаивает. Поэтому две ленты первой группы заняты одновременно не дольше 7 мс.

Итог: $\min(11, 7) = 7$ мс. Такое расписание действительно существует (общее время выполнения всей совокупности при этом остаётся минимальным — 38 мс):

ID	Время, мс	Зависит от	Старт, мс	Финиш, мс
101	4	—	0	4
102	3	—	0	3
103	1	101; 102	4	5
109	8	—	0	8
104	5	103	8	13
105	7	103	8	15
110	6	—	8	14
111	16	109	8	24
114	14	109	8	22
106	3	104	13	16
112	5	110	14	19
107	1	105; 106	16	17
108	2	107	17	19
113	14	111; 114	24	38

На отрезке с 8-й по 15-ю миллисекунду одновременно работают ровно пять процессов: сначала 104, 105, 110, 111, 114; с 13-й мс вместо завершившегося 104 включается 106; с 14-й мс вместо 110 — процесс 112. В момент 15 мс заканчивается 105, и остаётся четыре процесса. Длина отрезка — $15 - 8 = 7$ мс. Проверка:

sched = {101: (0, 4),   102: (0, 3),   103: (4, 5),   109: (0, 8),
         104: (8, 13),  105: (8, 15),  110: (8, 14),
         111: (8, 24),  114: (8, 22),
         106: (13, 16), 112: (14, 19), 107: (16, 17),
         108: (17, 19), 113: (24, 38)}

best = cur = 0
for t in range(38):                       # t - миллисекунда [t, t+1)
    k = sum(1 for s, e in sched.values() if s <= t < e)
    cur = cur + 1 if k >= 5 else 0
    best = max(best, cur)
print(best)

Ответ: 7

Решение:

Обе команды только уменьшают число на экране, поэтому траектория строго убывает и одно и то же число не может встретиться в ней дважды. Значит, каждая подходящая программа однозначно разбивается на две независимые части: сначала число $50$ превращается в $20$, затем $20$ превращается в $1$. По правилу умножения искомое количество равно произведению количеств программ для этих двух участков.

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$. Если $x = y$, подходит только пустая программа, то есть $f(x, x) = 1$; если $x \lt y$, то $f(x, y) = 0$ — увеличивать число команды не умеют. Иначе первая команда переводит $x$ либо в $x - 1$, либо в $\left\lfloor x/2 \right\rfloor$, поэтому

$$f(x, y) = f(x - 1,\, y) + f\big(\left\lfloor x/2 \right\rfloor,\, y\big).$$

Число $10$ в траектории появляться не должно, поэтому переход в него просто запрещаем — соответствующее слагаемое не учитываем.

from functools import lru_cache

@lru_cache(None)
def f(x, y):          # сколько программ переводят x в y, минуя число 10
    if x == y:
        return 1
    if x < y:
        return 0
    s = 0
    for z in (x - 1, x // 2):
        if z != 10:
            s += f(z, y)
    return s

print(f(50, 20) * f(20, 1))

Получаем $f(50, 20) = 12$ и $f(20, 1) = 135$, то есть всего $12 \cdot 135 = 1620$ программ. Ответ: 1620

Решение:

Нужен самый длинный участок, целиком состоящий из символов X и Y. Символы Z разрезают файл на такие участки, поэтому достаточно найти длину самого длинного «куска» между соседними Z.

Проход по файлу: счётчик cur увеличиваем на каждом символе, отличном от Z, и обнуляем на каждом Z; ответ — максимум счётчика.

s = open('44249_24.txt').read().strip()

mx = cur = 0
for c in s:
    if c != 'Z':
        cur += 1
        if cur > mx:
            mx = cur
    else:
        cur = 0

print(mx)

То же самое в одну строку через разбиение строки: print(max(len(p) for p in s.split('Z'))). Программа выводит 34. Ответ: 34

Решение:

Перебирать подряд все числа до $10^8$ не нужно: искомое число обязано делиться на 149, поэтому переберём сразу кратные $n=149k$ — их всего $\lfloor 10^8/149\rfloor=671140$, это мгновенно.

Проверку маски удобно поручить модулю fnmatch: в его шаблонах ? означает ровно один символ, а * — любую, в том числе пустую, последовательность символов, то есть ровно то, что написано в условии. Число превращаем в строку и сравниваем с маской 11*223.

from fnmatch import fnmatch

for k in range(1, 10 ** 8 // 149 + 1):
    n = 149 * k
    if fnmatch(str(n), '11*223'):
        print(n, k)

Маска 11*223 означает: число начинается на 11, заканчивается на 223, а между ними стоит произвольное (возможно, пустое) количество цифр. Программа находит 8 чисел; в ответе они записываются по строкам таблицы — сначала число, потом частное.

Число	Частное от деления на 149
1166223	7827
11000223	73827
11149223	74827
11298223	75827
11447223	76827
11596223	77827
11745223	78827
11894223	79827

Ответ: 1166223 7827 11000223 73827 11149223 74827 11298223 75827 11447223 76827 11596223 77827 11745223 78827 11894223 79827

Решение:

Сортируем диаметры по убыванию и жадно строим башню, начиная с самого большого коржа: очередной корж кладём, если его диаметр хотя бы на 4 меньше диаметра последнего положенного. Обратите внимание: пример в условии разобран для порога 3, но в самом задании требуется разница не менее 4 единиц.

Почему жадность верна: пропуск самого большого доступного коржа не удлиняет башню (такой корж всегда можно положить в основание), а порог для следующих коржей только уменьшает. Идя сверху вниз, мы на каждом шаге сохраняем максимальный запас, поэтому получаем и наибольшее число коржей, и максимально возможный диаметр самого маленького коржа — это последний взятый корж.

f = open('26.txt')
n = int(f.readline())
a = sorted((int(x) for x in f), reverse=True)

cnt = 0
last = None
for x in a:
    if last is None or x <= last - 4:
        cnt += 1
        last = x
print(cnt, last)

Программа выводит:

2172 50

Ответ: 2172 50

Решение:

Сначала забудем про делимость и возьмём из каждой пары большее число. Полученная сумма $S$ — наибольшая из всех возможных, поэтому если она не делится на 33, то она и есть ответ.

Пусть $S$ делится на 33. Тогда в некоторых парах придётся взять меньшее число. Замена в паре $(a,b)$ уменьшает сумму ровно на $d=|a-b|$, а замены в нескольких парах — на сумму соответствующих разностей. Итоговая сумма $S-\sum d$ не делится на 33 тогда и только тогда, когда $\sum d$ не кратна 33 (ведь само $S$ кратно 33). Но если бы все слагаемые в $\sum d$ были кратны 33, то и вся сумма была бы кратна 33; значит, хотя бы одна разность $d$ не кратна 33, и потому $\sum d \ge d_{\min}$, где $d_{\min}$ — наименьшая положительная разность, не кратная 33. Эта оценка достижима: достаточно поменять выбор в одной-единственной паре. Итак, ответ равен $S$, если $S$ не делится на 33, и $S-d_{\min}$ иначе.

Алгоритм линейный: один проход по файлу, в котором накапливаются $S$ и $d_{\min}$.

def solve(name, m):
    f = open(name)
    n = int(f.readline())
    s = 0                       # сумма больших чисел из каждой пары
    best = 10**9                # минимальная «допустимая» разность
    for _ in range(n):
        a, b = map(int, f.readline().split())
        s += max(a, b)
        d = abs(a - b)
        if d > 0 and d % m != 0:
            best = min(best, d)
    if s % m != 0:
        return s
    return s - best

print(solve('A.txt', 33), solve('B.txt', 33))

Файл A: сумма больших чисел равна $650905$; она даёт остаток $13$ при делении на 33, то есть уже не делится на 33 — уменьшать ничего не нужно, ответ $650905$.Файл B: сумма больших чисел равна $666122358$ и делится на 33. Наименьшая ненулевая разность внутри пары, не кратная 33, равна $1622$, поэтому ответ $666122358 - 1622 = 666120736$.Ответ: 650905 666120736