Вариант 7 · Август 2026

Решение:

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

Оба слагаемых выражения $\neg ( ( x \lor \neg y ) \land w ) \lor ( z \equiv y )$ обязаны быть нулевыми. Из $(z \equiv y) = 0$ получаем $z \ne y$, а из $\neg ( ( x \lor \neg y ) \land w ) = 0$ — что $( x \lor \neg y ) \land w = 1$, то есть $w = 1$ и $x \lor \neg y = 1$. При $y = 0,\ z = 1$ второе условие выполнено за счёт $\neg y$ и $x$ любое; при $y = 1,\ z = 0$ требуется $x = 1$. Наборы:

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

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

from itertools import product


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


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

Ответ: xwzy

Решение:

Нужно найти две суммы по таблице «Аренда» и взять модуль их разности. Для этого к строкам «Аренды» добавляем марку автомобиля (связь по полю «ID автомобиля») и фамилию клиента (связь по полю «ID клиента»).

Шаг 1. В таблице «Клиенты» находим ID Сачкова Х. Э. и ID Гудкова Н. Г.

Шаг 2. В таблице «Автомобили» отбираем машины марки Hyundai и выписываем их ID автомобиля.

Шаг 3. В таблице «Аренда» оставляем строки с этими автомобилями и датой аренды с 1 января по 30 июня включительно, а затем отдельно суммируем «Сумму аренды, руб.» по каждому из двух клиентов (формула СУММЕСЛИМН).

Шаг 4. У Сачкова Х. Э. одна поездка на 276 рублей. У Гудкова Н. Г. семь поездок: 178, 204, 205, 336, 183, 345 и 418 рублей, в сумме $178 + 204 + 205 + 336 + 183 + 345 + 418 = 1869$ рублей. Модуль разности: $|276 - 1869| = 1593$.

Ответ: 1593

Решение:

Известно: А — 00, Б — 01, В — 100, Г — 111. Нужны три новых кодовых слова с наименьшей суммарной длиной.

Ветвь 0 занята целиком (слова 00 и 01), поэтому все новые слова начинаются с единицы. В ветви 10 занято слово 100 — свободна вершина 101; в ветви 11 занято слово 111 — свободна вершина 110.

Свободных слов длины не более 3 всего два: 101 и 110. Букв же три, поэтому все три слова длины 3 получить нельзя — одну из вершин придётся разбить надвое.

Например, набор 101, 1100, 1101 даёт сумму длин $3 + 4 + 4 = 11$. Столько же даёт и набор 110, 1010, 1011. Меньше получить нельзя.

Ответ: 11

Решение:

В обоих случаях алгоритм приписывает справа ровно один разряд, поэтому запись $R$ на один разряд длиннее записи $N$. Замена двух левых разрядов на 10 или 11 старший разряд не убирает.

Если в записи $N$ не больше четырёх разрядов, то в записи $R$ их не больше пяти, а значит $R\le 11111_2=31\lt 40$. Поэтому в записи $N$ должно быть не менее пяти разрядов, то есть $N\ge 16$.

Проверяем $N=16=10000_2$: сумма цифр равна 1 — нечётная, поэтому справа приписываем 1 и получаем $100001$, а затем два левых разряда заменяем на 11: $110001_2=49\gt 40$ — подходит.

Значит, наименьшее подходящее число — 16.

def alg(n):
    b = bin(n)[2:]
    if sum(map(int, b)) % 2 == 0:
        b = '10' + (b + '0')[2:]
    else:
        b = '11' + (b + '1')[2:]
    return int(b, 2)

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

Ответ: 16

Решение:

После Направо 30 голова Черепахи направлена под углом $60^\circ$ к оси абсцисс. Первый цикл даёт два отрезка длины 12 с поворотом на $120^\circ$ между ними, затем Направо 300 — это поворот налево на $60^\circ$, и второй цикл добавляет ещё два таких же отрезка. Всего четыре стороны длины 12, а суммарный поворот $120^\circ+60^\circ+120^\circ+60^\circ=360^\circ$, то есть линия замыкается.

Это ромб со стороной 12 и углами $60^\circ$ и $120^\circ$; его вершины $(0;0)$, $(6;\,6\sqrt3)$, $(12;\,0)$, $(6;\,-6\sqrt3)$. Горизонтальная диагональ равна 12, вертикальная — $12\sqrt3\approx 20{,}78$, площадь $12^2\sin 60^\circ=72\sqrt3\approx 124{,}7$.

Считать удобно по вертикалям. Стороны ромба лежат на прямых $y=\pm\sqrt3\,x$ и $y=\pm\sqrt3\,(12-x)$, поэтому точка $(x;y)$ лежит строго внутри тогда и только тогда, когда $0\lt x\lt 12$ и $|y|\lt \sqrt3\cdot\min(x,\,12-x)$. Перебираем $x=1,\dots,11$; по симметрии столбцы $x$ и $12-x$ дают одинаковое количество точек:

• $x=1$ и $x=11$: $|y|\lt 1{,}73$ — по 3 точки;
• $x=2$ и $x=10$: $|y|\lt 3{,}46$ — по 7 точек;
• $x=3$ и $x=9$: $|y|\lt 5{,}20$ — по 11 точек;
• $x=4$ и $x=8$: $|y|\lt 6{,}93$ — по 13 точек;
• $x=5$ и $x=7$: $|y|\lt 8{,}66$ — по 17 точек;
• $x=6$: $|y|\lt 10{,}39$ — 21 точка.

Складываем: $2\cdot(3+7+11+13+17)+21=102+21=123$. Вершины $(0;0)$ и $(12;0)$ в подсчёт не попали — они лежат на линии.

k = 3 ** 0.5
n = 0
for x in range(1, 12):
    for y in range(-21, 22):
        if abs(y) < k * min(x, 12 - x):
            n += 1
print(n)

Программа выводит 123. Ответ: 123

Решение:

Пусть цвет одного пикселя кодируется $i$ битами. Всего в изображении $4000 \cdot 8000 = 32000000$ пикселей, значит файл (без заголовка) занимает $32000000 \cdot i$ бит.

Переведём отведённую память в биты: $15625 \cdot 1024 \cdot 8 = 128000000$ бит.

Файл должен поместиться в отведённую память: $32000000 \cdot i \le 128000000$, откуда $i \le \frac{128000000}{32000000} = 4$.

Наибольшее подходящее целое $i = 4$.

При $i$ битах на пиксель можно закодировать $2^i$ различных цветов, поэтому в изображении может быть $2^{4} = 16$ цветов.

W, H = 4000, 8000
V = 15625 * 1024 * 8  # отведённая память в битах
i = V // (W * H)      # максимальное целое число бит на пиксель
print(i, 2 ** i)      # 4 16

Ответ: 16

Решение:

Буквы в алфавитном порядке: К, Н, О, Р, С, Я. Наименьшее подходящее слово строим жадно, слева направо ставя минимальную букву, при которой условия ещё можно выполнить.

Условия: букв К не более трёх, букв Я ровно две.

• 1-я, 2-я и 3-я буквы — К (минимальная буква, а три К разрешены);
• 4-я буква: К уже нельзя, следующая по алфавиту — Н. Она подходит: тогда на оставшиеся две позиции как раз встанут обе Я;
• 5-я буква не может быть Н (иначе для двух Я останется только одна позиция), поэтому 5-я и 6-я — Я.

Получилось слово КККНЯЯ. Заменим буквы цифрами шестеричной системы (К=0, Н=1, О=2, Р=3, С=4, Я=5): КККНЯЯ → $000155_6$, значение $$1 \cdot 6^2 + 5 \cdot 6 + 5 = 36 + 30 + 5 = 71.$$ Номер слова равен $71 + 1 = 72$.

from itertools import product

for n, w in enumerate(product('КНОРСЯ', repeat=6), 1):
    s = ''.join(w)
    if s.count('К') <= 3 and s.count('Я') == 2:
        print(n, s)
        break

Ответ: 72

Решение:

Откроем файл. В строке 1 записаны часы (0:00 … 23:00), в столбце A — даты, а измерения занимают блок B2:Y92: 91 день по 24 замера, всего 2184 числа.

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

=СРЗНАЧ(B2:Y92)-МИН(B2:Y92)

В англоязычной версии редактора это =AVERAGE(B2:Y92)-MIN(B2:Y92). Получаем $10{,}4653\ldots - 0{,}3 = 10{,}1653\ldots$ Целая часть равна 10. То же самое на Python (для CSV-версии файла):

import csv

values = []
rows = list(csv.reader(open('data.csv', encoding='cp1251'), delimiter=';'))
for row in rows[1:]:                      # пропускаем строку с часами
    for cell in row[1:]:                  # пропускаем столбец с датой
        values.append(float(cell.replace(',', '.')))

print(sum(values) / len(values) - min(values))   # 10.1653...

В ответе записываем только целую часть. Ответ: 10

Решение:

Откроем файл с текстом повести и воспользуемся поиском (Ctrl+F). Вводим шапка и включаем режим «Только слово целиком»: иначе будут посчитаны формы «шапках», «шапками», «шапкам» и т. п., которые по условию не учитываются. Флажок «Учитывать регистр» не ставим — годятся и «шапка», и «Шапка».

Редактор находит 4 вхождения именно словоформы «шапка»: «…и шапка в золоте…», «…и шапка заломлена набекрень…», «…у кого шапка…», «Разлетелась медная шапка…».

Проверка программой:

import re

text = open('text.txt', encoding='cp1251').read()
matches = re.findall(r'(?<![А-Яа-яЁё])[Шш]апка(?![А-Яа-яЁё])', text)
print(len(matches))   # 4

Ответ: 4

Решение:

В идентификаторе используются 10 десятичных цифр и 4000 символов специального алфавита, значит мощность алфавита составляет $10 + 4000 = 4010$ символов. На один символ нужно минимальное целое $i$, при котором $2^i \ge 4010$. Так как $2^{11} = 2048 \lt 4010 \lt 4096 = 2^{12}$, получаем $i = 12$ бит.

Один идентификатор из 141 символ занимает $141 \cdot 12 = 1692$ бита. Число байт должно быть целым и минимальным: $1692 = 8 \cdot 211 + 4$, поэтому под него отводится 212 байт.

Все 2560 идентификаторов занимают $2560 \cdot 212 = 542720$ байт, то есть $542720 : 1024 = 530$ Кбайт.

import math

N = 10 + 4000                 # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(141 * i / 8)    # байт на один идентификатор
print(2560 * b // 1024)       # ответ в Кбайт

Ответ: 530

Решение:

Команда заменить(v, w) — это s.replace(v, w, 1) (меняется только первое слева вхождение), команда нашлось(v) — это проверка v in s. Значит исполнителя можно точно смоделировать на Python.

Три конструкции ЕСЛИ внутри цикла выполняются последовательно, так что за один проход тела цикла может произойти несколько замен. Аналитически сумму цифр не выразить, но диапазон $3 \lt n \lt 10000$ невелик, поэтому перебираем все допустимые $n$ программой.

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

def rabota(s):
    while "31" in s or "411" in s or "1111" in s:
        if "31" in s:
            s = zamenit(s, "31", "1")
        if "411" in s:
            s = zamenit(s, "411", "13")
        if "1111" in s:
            s = zamenit(s, "1111", "4")
    return s

for n in range(4, 10000):
    s = rabota("4" + "1" * n)
    if sum(int(c) for c in s) == 34:
        print(n, s)
        break
# 187 1333413341341

Наименьшее подходящее значение — $n = 187$: остаётся строка 1333413341341 с суммой цифр 34. Ответ: 187

Решение:

Маска — это $k$ единиц подряд и затем нули, поэтому её третий слева байт зависит только от $k$: если граница сети проходит внутри третьего байта, он равен 10000000 = 128 при $k=17$, 11000000 = 192 при $k=18$, 11100000 = 224 при $k=19$ и так далее. Значит, чем меньше $k$, тем меньше третий байт, и надо найти наименьшее допустимое $k$.

Двоичные записи:
адрес узла 198.219.147.99 — 11000110.11011011.10010011.01100011,
адрес сети 198.219.128.0 — 11000110.11011011.10000000.00000000.

Единица на 17-й позиции (старший бит третьего байта) присутствует в адресе сети, поэтому она обязана попасть в сетевую часть: $k \ge 17$. Дальше третьи байты 10010011 и 10000000 совпадают лишь в трёх старших разрядах, различающийся четвёртый бит маска должна обнулить, поэтому $k \le 19$.

Подходят $k = 17, 18, 19$, то есть маски 255.255.128.0, 255.255.192.0 и 255.255.224.0. Наименьшее значение третьего байта — 128.

Проверка программой:

def to_bits(s):
    return ''.join(format(int(x), '08b') for x in s.split('.'))

ip = to_bits('198.219.147.99')
net = to_bits('198.219.128.0')
ok = [k for k in range(33) if ip[:k] + '0' * (32 - k) == net]
bytes3 = [int(('1' * k + '0' * (32 - k))[16:24], 2) for k in ok]
print(ok, bytes3, min(bytes3))

Ответ: 128

Решение:

Распишем операнды по степеням основания:

$135x9_{17} = 1 \cdot 17^4 + 3 \cdot 17^3 + 5 \cdot 17^2 + x \cdot 17 + 9$,

$9x531_{17} = 9 \cdot 17^4 + x \cdot 17^3 + 5 \cdot 17^2 + 3 \cdot 17 + 1$.

Сумма: $S = 10 \cdot 17^4 + (x + 3) \cdot 17^3 + 10 \cdot 17^2 + (x + 3) \cdot 17 + 10$.

Так как $17 \equiv -1 \pmod 9$, то $17^2 \equiv 1$, $17^3 \equiv -1$, $17^4 \equiv 1 \pmod 9$, поэтому

$S \equiv 10 - (x + 3) + 10 - (x + 3) + 10 = 24 - 2x \pmod 9$.

Условие кратности девяти: $24 - 2x \equiv 0 \pmod 9$, то есть $2x \equiv 6 \pmod 9$, откуда $x \equiv 3 \pmod 9$.

В алфавите 17-ричной системы цифры — это $0 \ldots 16$, значит подходят $x = 3$ и $x = 12$. Наибольшее значение — $x = 12$.

При $x = 12$: $S = 10 \cdot 83521 + 15 \cdot 4913 + 10 \cdot 289 + 15 \cdot 17 + 10 = 912060$, и $912060 : 9 = 101340$.

for x in range(17):
    a = 17**4 + 3*17**3 + 5*17**2 + x*17 + 9
    b = 9*17**4 + x*17**3 + 5*17**2 + 3*17 + 1
    if (a + b) % 9 == 0:
        print(x, (a + b) // 9)

Ответ: 101340

Решение:

Дизъюнкция ложна только тогда, когда ложны все три её слагаемых. Значит, выражение тождественно истинно ровно тогда, когда не найдётся пары целых неотрицательных $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(2024)$ и $F(2022)$ по отдельности не нужно: в разности почти всё сократится. Раскроем соотношение $F(n) = 2n + 1 + F(n - 1)$ два раза.

$$F(2024) = 2 \cdot 2024 + 1 + F(2023) = 4049 + F(2023),$$

$$F(2023) = 2 \cdot 2023 + 1 + F(2022) = 4047 + F(2022).$$

Подставим второе равенство в первое:

$$F(2024) = 4049 + 4047 + F(2022) = 8096 + F(2022).$$

Отсюда $F(2024) - F(2022) = 8096$. Обратите внимание: базовое значение $F(1) = 5$ в ответ не входит вовсе.

def F(n):
    r = 5
    for i in range(2, n + 1):
        r = 2 * i + 1 + r
    return r

print(F(2024) - F(2022))   # 8096

Ответ: 8096

Решение:

Задача решается одним проходом по файлу, но сначала нужно вычислить «планку» — максимальный элемент последовательности, оканчивающийся на 13. Число оканчивается на 13 тогда и только тогда, когда остаток от его деления на 100 равен 13. Для данного файла эта планка равна 98413.

Дальше перебираем все тройки идущих подряд элементов (то есть окна вида $a_i, a_{i+1}, a_{i+2}$) и проверяем два условия: ровно два числа тройки трёхзначные, то есть лежат в диапазоне от 100 до 999, и сумма всех трёх чисел не превосходит найденной планки. Считаем такие тройки и параллельно запоминаем наибольшую из их сумм.

Подходящих троек оказывается 959, а наибольшая сумма среди них равна 97471.

a = [int(line) for line in open('17.txt')]

limit = max(x for x in a if x % 100 == 13)   # 98413

count = 0
best = 0
for i in range(len(a) - 2):
    t = a[i:i + 3]
    if sum(100 <= x <= 999 for x in t) == 2 and sum(t) <= limit:
        count += 1
        best = max(best, sum(t))

print(count, best)   # 959 97471

Ответ: 959 97471

Решение:

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

Пусть $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}$.

В приложенном файле поле имеет размер $16\times16$. Единственная внутренняя стена (утолщённая линия) — горизонтальная, между 6-й и 7-й строками в столбцах с 5-го по 10-й: в эти клетки 7-й строки нельзя попасть сверху, только слева.

Скопируем содержимое таблицы в текстовый файл 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 == 5 and 4 <= j <= 9

# стена справа от клетки (i, j) — вертикальных внутренних стен нет
def wall_right(i, j):
    return False

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(MN[N - 1][N - 1], MX[N - 1][N - 1])

Программа выводит 508 731: минимальная сумма равна 508, максимальная — 731. В ответе сначала записывается минимальная сумма, затем максимальная. Ответ: 508 731

Решение:

Нужно найти наименьшее $S$, для которого выполняются сразу два требования: Петя не выигрывает первым же ходом, а Ваня выигрывает своим первым ходом при любом ходе Пети.

Первое требование. Петя выигрывает сразу, если $S + 1 \ge 129$ или $2S \ge 129$. Значит, «не выиграть за один ход» означает $S + 1 \le 128$ и $2S \le 128$, то есть $S \le 64$.

Второе требование. Из кучи в $n$ камней игрок выигрывает одним ходом, если $n + 1 \ge 129$ или $2n \ge 129$; при $n \le 128$ это равносильно $n \ge 65$ (тогда удвоение сразу даёт не меньше 130). После хода Пети в куче окажется $S + 1$ или $2S$, и оба этих числа должны быть не меньше 65: $S + 1 \ge 65$ даёт $S \ge 64$, а $2S \ge 65$ даёт $S \ge 33$. Более сильное из них — $S \ge 64$.

Оба требования выполняются одновременно только при $S = 64$. Проверка: Петя из 64 может получить 65 или 128 — игра не кончается; из 65 Ваня удваивает и получает 130, из 128 добавляет камень и получает 129. В обоих случаях Ваня побеждает своим первым ходом.

def win_now(s):                     # можно ли выиграть одним ходом из s
    return s + 1 >= 129 or 2 * s >= 129

for s in range(1, 129):
    if not win_now(s) and all(win_now(m) for m in (s + 1, 2 * s)):
        print(s)                    # 64
        break

Ответ: 64

Решение:

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

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

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

• $(19,\ 52)$ — Петя удваивает вторую кучу: $19 + 104 = 123$;
• $(18,\ 53)$ — Петя удваивает вторую кучу: $18 + 106 = 124$;
• $(36,\ 52)$ — Петя удваивает вторую кучу: $36 + 104 = 140$;
• $(18,\ 104)$ — Петя добавляет камень: $18 + 105 = 123$.

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

• $(11,\ 56)$ — Петя удваивает вторую кучу: $11 + 112 = 123$;
• $(10,\ 57)$ — Петя удваивает вторую кучу: $10 + 114 = 124$;
• $(20,\ 56)$ — Петя удваивает вторую кучу: $20 + 112 = 132$;
• $(10,\ 112)$ — Петя добавляет камень: $10 + 113 = 123$.

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

N = 123

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, 114) if win2((9, s))][:2])   # два наименьших

Ответ: 52 56

Решение:

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

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

• $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 = 2022

def moves(s):
    return [s + 1, 2 * 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, 2021):
    if lose2(s) and not lose1(s):
        print(s)
        break

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

• $1009$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $1010$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $1011$ — в $2022$; из $2020$ — в $4040$);
• $2016$ — Ваня выигрывает сразу: одним ходом он получает $4032$, а это уже не меньше 2022.

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

Ответ: 1008

Решение:

Момент завершения процесса $B$ равен $F(B) = \max F(A_i) + t(B)$, где $A_i$ — процессы, от которых он зависит; независимый процесс завершается в момент $t(B)$. Время работы всей совокупности — наибольшее из значений $F$. При увеличении $t$ это время не убывает, поэтому нужно взять наибольшее целое $t$, при котором оно ещё не превышает 19 мс.

Подставим $t = 9$ и заполним столбец $F$:

Наибольшее значение равно 19 мс, условие «не более 19 мс» выполнено. При $t = 10$ общее время стало бы равно 20 мс, что больше 19, поэтому 9 — максимально возможное целое значение.

Тот же перебор программой:

# данные из прилагаемого файла; None — неизвестное время t
data = {
     1: (4, []),
     2: (3, []),
     3: (2, [1, 2]),
     4: (3, [3]),
     5: (None, []),
     6: (5, [4, 5]),
     7: (5, []),
     8: (6, [7]),
     9: (5, [6, 8]),
    10: (12, []),
    11: (2, [10]),
    12: (2, [11]),
}

def total(t):
    finish = {}
    for i in sorted(data):
        dur, deps = data[i]
        if dur is None:
            dur = t
        finish[i] = max([finish[d] for d in deps], default=0) + dur
    return max(finish.values())

print(max(t for t in range(1, 1000) if total(t) <= 19))

Ответ: 9

Решение:

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

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$: $f(x, x) = 1$ (пустая программа), $f(x, y) = 0$ при $x \gt y$ (число уже «перескочило» цель, а уменьшать команды не умеют). В остальных случаях перебираем первую команду («прибавить 2», «прибавить 3» или «умножить на 5»):

$$f(x, y) = f(x + 2,\, y) + f(x + 3,\, y) + f(5x,\, y).$$

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

from functools import lru_cache

@lru_cache(None)
def f(x, y):          # сколько программ переводят число x в число y
    if x == y:
        return 1
    if x > y:
        return 0      # перескочили - назад команд нет
    s = 0
    for z in (x + 2, x + 3, x * 5):
        if z not in (6, 17):
            s += f(z, y)
    return s

print(f(1, 31))

Программа выводит $961$. Ответ: 961

Решение:

Запрещена только одна конфигурация — две буквы P подряд, то есть подстрока PP. Все остальные сочетания символов допустимы, поэтому серия обрывается ровно в тех местах, где встречается PP.

Идём по файлу и храним длину текущей допустимой серии cur. Если текущий и предыдущий символы оба равны P, старая серия закончилась, и новая начинается с текущего символа: cur = 1. Иначе cur += 1. Ответ — максимум cur.

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

mx = cur = 1
for i in range(1, len(s)):
    if s[i] == 'P' and s[i - 1] == 'P':
        cur = 1
    else:
        cur += 1
    if cur > mx:
        mx = cur

print(mx)

Важно, что при обрыве новая серия начинается именно со второй буквы P: она сама по себе запрещённой пары не образует и может стать началом следующего участка. Программа выводит 188. Ответ: 188

Решение:

Наибольший делитель числа $n$, не равный самому $n$, — это $n/p$, где $p$ — наименьший простой делитель $n$. Поэтому достаточно найти $p$ перебором $d$ от 2 до $\sqrt{n}$, а затем проверить, простое ли частное $n/p$.

Простые числа сразу отбрасываем: по условию для них такого делителя не существует. Заметим, что оставшееся условие равносильно тому, что число $n$ раскладывается минимум на три простых множителя с учётом кратности: если множителей всего два, то $n = p\cdot q$ и частное $n/p = q$ простое.

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

def big_div(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d      # наибольший делитель, не равный n
        d += 1
    return 0                   # n простое: такого делителя нет

n = 550000
found = 0
while found < 6:
    n += 1
    d = big_div(n)
    if d != 0 and not is_prime(d):
        print(n, d)
        found += 1

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

550002 275001
550004 275002
550005 183335
550008 275004
550010 275005
550011 183337

Ответ: 550002 275001 550004 275002 550005 183335 550008 275004 550010 275005 550011 183337

Решение:

Задача решается в два шага.

Шаг 1. Максимальное количество. Чтобы уместить как можно больше посылок, надо брать самые маленькие. Сортируем объёмы по возрастанию и набираем их подряд, пока сумма не превысит $S$. Полученное число $k$ и есть максимум: любой набор из $k+1$ посылок весит не меньше, чем $k+1$ самых маленьких, а те уже не помещаются.

Шаг 2. Максимальный размер. Количество $k$ фиксировано. Чтобы один из взятых посылок был как можно больше, остальные $k-1$ надо взять как можно легче — это $k-1$ самых маленьких из отсортированного списка. На оставшееся место $S - (a_1 + a_2 + \ldots + a_{k-1})$ ставим самый большой из тех, что туда влезают.

Первая строка прилагаемого файла содержит $S$ и $N$, далее идут $N$ объёмов посылок.

f = open('26.txt')
s, n = map(int, f.readline().split())
a = sorted(int(x) for x in f)

total = 0
k = 0
for x in a:
    if total + x <= s:
        total += x
        k += 1
    else:
        break

base = sum(a[:k - 1])                            # k-1 самых маленьких
big = max(x for x in a[k - 1:] if base + x <= s)  # самый большой, который ещё влезает
print(k, big)

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

629 50

Ответ: 629 50

Решение:

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

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

Файл A: сумма больших чисел равна $639036$; она даёт остаток $9$ при делении на 37, то есть уже не делится на 37 — уменьшать ничего не нужно, ответ $639036$.Файл B: сумма больших чисел равна $664021240$ и делится на 37. Наименьшая ненулевая разность внутри пары, не кратная 37, равна $6692$, поэтому ответ $664021240 - 6692 = 664014548$.Ответ: 639036 664014548