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

Решение:

Степени вершин схемы: A — 3, B — 2, C — 2, D — 5, E — 2, F — 2, G — 2.

Число звёздочек в строках таблицы: 1 — 2, 2 — 2, 3 — 3, 4 — 2, 5 — 2, 6 — 2, 7 — 5.

Степень 5 только у D и только у пункта 7, степень 3 только у A и только у пункта 3. Значит, D = 7 и A = 3.

Соседи A на схеме — это C, D и G. Соседи пункта 3 — это 1, 4 и 7; пункт 7 — это D, поэтому вершинам C и G отвечают пункты 1 и 4.

Соседи D на схеме — это A, C, G, B и E. Соседи пункта 7 — это 1, 2, 3, 4 и 6. Пункт 3 — это A, пункты 1 и 4 — это C и G, значит, вершинам B и E отвечают оставшиеся пункты 2 и 6. (Заодно F — это пункт 5, единственный не соединённый с 7.)

Записываем номера в порядке возрастания.

Ответ: 26

Решение:

Функция $F = ( ( x \rightarrow y ) \rightarrow w ) \lor ( z \rightarrow ( y \land w ) )$ зависит от четырёх переменных, поэтому её полная таблица истинности содержит $2^4 = 16$ строк, а расставить переменные w, x, y, z по четырём столбцам можно $4! = 24$ способами.

Найдём все наборы, на которых $F = 0$. Таких наборов всего три (значения записаны в «алфавитном» порядке $w,\ x,\ y,\ z$):

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

Значит, каждая строка фрагмента — это одна из этих трёх строк, только с переставленными столбцами. Но в каком порядке идут сами строки фрагмента, неизвестно, поэтому соответствие «столбец → переменная» надёжнее всего установить перебором всех 24 расстановок.

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

Всё это удобно поручить программе. В Python импликация $a \rightarrow b$ — это a <= b.

from itertools import product, permutations

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

# фрагмент таблицы: '.' — незаполненная клетка, второе число — значение F
frag = [('10..', 0),
        ('..1.', 0),
        ('.10.', 0)]

def fits(mask, vals):
    return all(m == '.' or int(m) == v for m, v in zip(mask, vals))

for p in permutations('wxyz'):
    # для каждой строки фрагмента — все её допустимые дополнения
    variants = []
    for mask, f in frag:
        variants.append([vals for vals in product((0, 1), repeat=4)
                         if fits(mask, vals) and F(**dict(zip(p, vals))) == f])
    # строки фрагмента должны быть попарно различны
    for lines in product(*variants):
        if len(set(lines)) == len(lines):
            print(''.join(p))
            break

Программа печатает единственную расстановку — zyxw. Проверим её вручную. Столбцы идут в порядке $z,\ y,\ x,\ w$; восстановим пустые клетки (восстановленные значения выделены курсивом):

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

Все строки различны, известные клетки совпадают с фрагментом, и функция на них принимает требуемые значения — расстановка найдена верно.

Ответ: zyxw

Решение:

«Есть в наличии на складах» означает разность между тем, что поступило с производства, и тем, что выдано покупателям, посчитанную по всем операциям до конца указанного дня включительно.

Шаг 1. В таблице «Производственные базы» отбираем базы, в адресе которых указана Владимирская область, и выписываем их ID производственной базы (таких баз три).

Шаг 2. В таблице «Продукты» находим строку с наименованием «шиповник» и запоминаем её артикул.

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

Шаг 4. Двумя формулами СУММЕСЛИМН считаем сумму по полю «Количество, кг» отдельно для типа операции «Поступило с производства» и для типа «Выдано покупателю»: получается 72 кг и 31 кг. Остаток на складах: $72 - 31 = 41$ кг.

Ответ: 41

Решение:

Условие Фано нарушается, если новое кодовое слово является началом одного из используемых слов или одно из используемых слов является началом нового.

Заняты слова А — 00, Б — 01, В — 10, Г — 11, то есть все четыре двоичных слова длины 2. Слово из одного символа брать нельзя (символов должно быть больше одного), а совпадать с уже используемыми словами новое слово тоже не должно — значит, среди слов длины 2 подходящих нет.

Переходим к словам длины 3. Наименьшее числовое значение у слова 000. Проверяем его: слово 00 (буква А) является началом слова 000, поэтому условие Фано нарушается — это то, что требуется.

Значит, самое короткое подходящее слово с минимальным числовым значением — 000.

Ответ: 000

Решение:

Пусть $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 1025$. Рассмотрим все четыре случая.

• $r=1$: $4N+2\ge 1025\Rightarrow N\ge 256$. Наименьшее число вида $4k+1$ — это $N=257$.
• $r=2$: $16N+4\ge 1025\Rightarrow N\ge 64$. Наименьшее число вида $4k+2$ — это $N=66$, $R=16\cdot 66+4=1060$.
• $r=3$: $16N+6\ge 1025\Rightarrow N\ge 64$. Наименьшее число вида $4k+3$ — это $N=67$, $R=1078$.
• $r=0$: $N=64$ даёт $R=16\cdot 64+0=1024$ — ровно на единицу меньше нужного, не подходит. Следующее кратное четырём $N=68$ даёт $R=16\cdot 68+4=1092$.

Наименьшее из чисел 257, 66, 67, 68 — это 66.

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) >= 1025))

Ответ: 66

Решение:

Первый цикл: две итерации [Направо 90 Вперёд 1 Направо 90 Вперёд 11] уже возвращают Черепаху в исходную точку с исходным направлением, поэтому шесть итераций — это один и тот же прямоугольник, обведённый три раза. Его вершины: $(0;0)$, $(1;0)$, $(1;-11)$, $(0;-11)$, то есть $0\le x\le 1$, $-11\le y\le 0$. Целых точек в нём вместе с границей $2\cdot 12=24$.

При поднятом хвосте Черепаха переходит: Вперёд 3 — в $(0;3)$, Направо 90 — голова смотрит вправо, Вперёд 5 — в $(5;3)$. Второй цикл Повтори 10 [Вперёд 12 Направо 90] рисует квадрат со стороной 12, который замыкается уже после четырёх итераций; десять итераций обводят тот же квадрат два с половиной раза. Его вершины: $(5;3)$, $(17;3)$, $(17;-9)$, $(5;-9)$, то есть $5\le x\le 17$, $-9\le y\le 3$, и целых точек в нём $13\cdot 13=169$.

Фигуры не пересекаются и даже не касаются: у первой $x\in[0;1]$, у второй $x\in[5;17]$. Поэтому в объединении $24+169=193$ точки.

Ответ: 193

Решение:

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

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

Файл должен поместиться в отведённую память: $184320 \cdot i \le 1966080$, откуда $i \le \frac{1966080}{184320} \approx 10{,}67$.

Число бит на пиксель — целое, поэтому наибольшее подходящее значение $i = 10$.

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

W, H = 360, 512
V = 240 * 1024 * 8  # отведённая память в битах
i = V // (W * H)    # максимальное целое число бит на пиксель
print(i, 2 ** i)    # 10 1024

Ответ: 1024

Решение:

В четверичной системе счисления используются цифры 0, 1, 2, 3.

Если цифры строго убывают, то они попарно различны. Наоборот, любые три различные цифры можно расположить по убыванию единственным способом. Значит, подходящих записей ровно столько, сколько трёхэлементных подмножеств у множества из четырёх цифр: $$C_4^3 = \frac{4!}{3!\,1!} = 4.$$

Старшая цифра при этом наибольшая из трёх, поэтому она заведомо не равна нулю, и все 4 набора — настоящие трёхзначные числа: $321_4$, $320_4$, $310_4$, $210_4$.

from itertools import product

print(sum(1 for d in product(range(4), repeat=3) if d[0] > d[1] > d[2]))

Ответ: 4

Решение:

Откроем файл. В строке 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).

Параметры поиска:

• «Только слово целиком» — включено: слова «большевики», «большевиками», «большевизме», внутри которых есть сочетание «больше», считать нельзя;
• «Учитывать регистр» — включено: нужно слово со строчной буквы, а вариант «Больше» с прописной в тексте один раз встречается и в ответ не идёт.

«Найти все» даёт 15 совпадений.

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

import re

text = open('text.txt', encoding='utf-8').read()
print(len(re.findall(r'\bбольше\b', text)))

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

Решение:

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

Один идентификатор из 98 символов занимает $98 \cdot 11 = 1078$ бит. Число байт должно быть целым и минимальным: $1078 = 8 \cdot 134 + 6$, поэтому под него отводится 135 байт.

Все 13 312 идентификаторов занимают $13312 \cdot 135 = 1797120$ байт, то есть $1797120 : 1024 = 1755$ Кбайт.

import math

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

Ответ: 1755

Решение:

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

Прогоним программу на коротких строках вида «22 + $k$ единиц + 22»: $k=5$ — 121222, $k=6$ — 1212122, $k=7$ — 121222, $k=8$ — 1212122, … Начиная с $k=5$ ответ определяется чётностью $k$: нечётное $k$ даёт 121222, чётное — 1212122.

Число 2050 чётное, значит получится 1212122. Проверим прямым моделированием.

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

s = "22" + "1" * 2050 + "22"
while "211" in s or "112" in s:
    s = zamenit(s, "11", "1")
    if "21" in s:
        s = zamenit(s, "21", "12")
    else:
        s = zamenit(s, "12", "1")
print(s)   # 1212122

Ответ: 1212122

Решение:

В маске сначала идут единицы, а потом только нули, поэтому вопрос сводится к тому, сколько старших разрядов IP-адреса сохраняется в адресе сети.

Сравним адрес узла 42.118.219.133 и адрес сети 42.118.216.0 побайтно.

Первые два байта совпадают (42 и 118), значит первые $16$ разрядов маски — единицы.

Третий байт: $219_{10}=11011011_2$, а в адресе сети $216_{10}=11011000_2$. Записи различаются только в двух младших разрядах — конъюнкция их обнулила. Значит, в третьем байте маски два младших разряда обязательно нули, а остальные шесть могут быть единицами: $11111100_2 = 252_{10}$. Проверка: поразрядная конъюнкция $11011011_2$ и $11111100_2$ даёт $11011000_2 = 216_{10}$ — верно. Больше шести единиц взять нельзя: при единице во втором справа разряде сохранилась бы единица адреса узла и получилось бы 218.

После первого нуля в маске идут только нули, поэтому четвёртый байт маски равен 0; это согласуется с последним байтом адреса сети, который тоже равен 0.

Итого единиц в маске: $8+8+6+0=22$.

ip  = [42, 118, 219, 133]
net = [42, 118, 216, 0]

def mask_bytes(k):
    bits = '1' * k + '0' * (32 - k)
    return [int(bits[i:i + 8], 2) for i in range(0, 32, 8)]

for k in range(32, -1, -1):          # ищем наибольшее число единиц
    m = mask_bytes(k)
    if all(a & b == c for a, b, c in zip(ip, m, net)):
        print(k)                     # 22
        break

Ответ: 22

Решение:

Основание 25, делитель $24 = 25-1$. Так как $25 \equiv 1 \pmod{24}$, число сравнимо по модулю 24 с суммой своих 25-ричных цифр.

• $1x2x3x4x5_{25}$: $1+2+3+4+5 + 4x = 15 + 4x$;
• $2x024_{25}$: $2+x+0+2+4 = 8 + x$;
• $1x099_{25}$: $1+x+0+9+9 = 19 + x$.

Всего $42 + 6x \equiv 0 \pmod{24}$, то есть $6x \equiv 6 \pmod{24}$, откуда $x \equiv 1 \pmod{4}$. В алфавите 25-ричной системы подходят $x = 1, 5, 9, 13, 17, 21$; наибольшее — $x = 21$.

Подставляем $x=21$ и делим сумму на 24:

b = 25

def num(ds):
    n = 0
    for d in ds:
        n = n * b + d
    return n

for x in range(b - 1, -1, -1):           # ищем наибольшее x
    s = (num([1, x, 2, x, 3, x, 4, x, 5])
         + num([2, x, 0, 2, 4])
         + num([1, x, 0, 9, 9]))
    if s % 24 == 0:
        print(x, s // 24)                # 21 11727433732
        break

Ответ: 11727433732

Решение:

Дизъюнкция ложна только тогда, когда ложны все три слагаемых. Значит выражение $(x \ge A) \lor (y \ge A) \lor (x \cdot y \le 270)$ не является тождественно истинным ровно тогда, когда найдутся целые положительные $x, y$, для которых

$x \lt A$, $y \lt A$ и $x \cdot y \gt 270$.

Нужно взять наибольшее $A$, при котором такой пары не существует.

Для целых $x \lt A$ и $y \lt A$ верно $x \le A - 1$ и $y \le A - 1$, поэтому наибольшее возможное произведение равно $(A - 1)^{2}$. Контрпримера нет тогда и только тогда, когда

$$(A - 1)^{2} \le 270.$$

Так как $16^{2} = 256 \le 270$, а $17^{2} = 289 \gt 270$, получаем $A - 1 \le 16$, то есть $A \le 17$. При $A = 17$ любое произведение не больше $16 \cdot 16 = 256 \le 270$ — выражение истинно; при $A = 18$ пара $x = y = 17$ даёт $289 \gt 270$ и обращает выражение в 0.

best = 0
for A in range(0, 100):
    if all(x >= A or y >= A or x * y <= 270
           for x in range(1, A + 1) for y in range(1, A + 1)):
        best = A
print(best)   # 17

Ответ: 17

Решение:

Вычислять $F(2024)$ целиком не нужно — выражение сворачивается, потому что рекуррентное соотношение связывает три подряд идущих значения.

Запишем правило при $n = 2021$: $F(2021) = 2021 \cdot 2020 + F(2020) - F(2019)$, откуда $F(2020) - F(2019) = F(2021) - 2021 \cdot 2020$. Значит искомое выражение равно $F(2024) + F(2021) - 2021 \cdot 2020$.

Теперь раскроем $F(2024)$. При $n = 2024$: $F(2024) = 2024 \cdot 2023 + F(2023) - F(2022)$, а при $n = 2023$: $F(2023) = 2023 \cdot 2022 + F(2022) - F(2021)$, то есть $F(2023) - F(2022) = 2023 \cdot 2022 - F(2021)$. Поэтому $F(2024) = 2024 \cdot 2023 + 2023 \cdot 2022 - F(2021)$.

Слагаемые с $F(2021)$ взаимно уничтожаются:

$$F(2024) + F(2020) - F(2019) = 2024 \cdot 2023 + 2023 \cdot 2022 - 2021 \cdot 2020 = 4094552 + 4090506 - 4082420 = 4102638.$$

Тот же ответ даёт программа. Рекурсию «в лоб» здесь применять нельзя (каждый вызов порождает два новых, время растёт экспоненциально) — заполняем таблицу значений по возрастанию $n$:

F = [0] * 2025
F[1], F[2] = 1, 2
for n in range(3, 2025):
    F[n] = n * (n - 1) + F[n - 1] - F[n - 2]

print(F[2024] + F[2020] - F[2019])   # 4102638

Ответ: 4102638

Решение:

Читаем файл в список и перебираем пары соседних элементов $(a_i,\ a_{i+1})$.

Последнюю цифру берём как остаток от деления модуля числа на 10: у отрицательных чисел в Python обычный остаток даёт не ту цифру (например, $-9578 \bmod 10 = 2$, а оканчивается число на 8).

Пара подходит, если у обоих чисел последние цифры совпадают и нечётны. Среди таких пар ищем максимальное произведение модулей.

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

count = 0
best = 0
for x, y in zip(a, a[1:]):
    dx, dy = abs(x) % 10, abs(y) % 10
    if dx % 2 == 1 and dx == dy:
        count += 1
        p = abs(x) * abs(y)
        if p > best:
            best = p

print(count, best)   # 227 96784219

Получаем 227 пар, наибольшее произведение модулей — 96784219.Ответ: 227 96784219

Решение:

Робот ходит только вправо и вниз, поэтому в любую клетку он может прийти лишь слева или сверху. Это классическая динамика по таблице: рядом с исходным полем $20 \times 20$ строим ещё две таблицы того же размера — в первой накапливаем максимально возможную сумму, во второй минимально возможную.

В левую верхнюю клетку обеих таблиц записываем саму монету (в этом файле это 99). Остальные клетки заполняем построчно слева направо по правилу: значение равно монете из исходной таблицы плюс наибольшее (соответственно наименьшее) из значений соседей слева и сверху, причём сосед учитывается только тогда, когда между ним и текущей клеткой нет утолщённой линии — стены. Если оба входа перекрыты стенами, клетка недостижима и остаётся пустой. Например, если исходные данные лежат в диапазоне A1:T20, а таблицу максимумов разместить в A23:T42, то в клетку B24 (она отвечает клетке R2C2 поля) пишем =B2+МАКС(A24;B23), а там, где вход перекрыт стеной, соответствующий аргумент из формулы просто убираем.

Маршрут заканчивается в «угловой» клетке — той, у которой перекрыты и правый, и нижний переходы. В этом файле таких достижимых клеток три: R15C18, R20C12 и R20C20. Ответ ищем только среди них, а не по всей таблице. Наибольшая накопленная сумма получается в правой нижней клетке R20C20 и равна 2167, наименьшая — в клетке R15C18 и равна 718.

import openpyxl

ws = openpyxl.load_workbook('18.xlsx').active
N = 20
coin = [[ws.cell(r + 1, c + 1).value for c in range(N)] for r in range(N)]

def thick(r, c, side):          # утолщённая линия = стена
    return getattr(ws.cell(r + 1, c + 1).border, side).style == 'thick'

def wall_right(r, c):
    return c == N - 1 or thick(r, c, 'right') or thick(r, c + 1, 'left')

def wall_down(r, c):
    return r == N - 1 or thick(r, c, 'bottom') or thick(r + 1, c, 'top')

hi = [[None] * N for _ in range(N)]
lo = [[None] * N for _ in range(N)]
hi[0][0] = lo[0][0] = coin[0][0]
for r in range(N):
    for c in range(N):
        if hi[r][c] is None:
            continue
        for nr, nc, blocked in ((r, c + 1, wall_right(r, c)),
                                (r + 1, c, wall_down(r, c))):
            if blocked:
                continue
            a = hi[r][c] + coin[nr][nc]
            b = lo[r][c] + coin[nr][nc]
            hi[nr][nc] = a if hi[nr][nc] is None else max(hi[nr][nc], a)
            lo[nr][nc] = b if lo[nr][nc] is None else min(lo[nr][nc], b)

ends = [(r, c) for r in range(N) for c in range(N)
        if hi[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(hi[r][c] for r, c in ends), min(lo[r][c] for r, c in ends))
# 2167 718

Ответ: 2167 718

Решение:

Позицию обозначаем (x, y). За один ход общее количество камней растёт либо на 1 (добавили камень), либо на x, либо на y (удвоили соответствующую кучу). Значит одним ходом можно прибавить не больше чем $\max(x,\,y,\,1)$, и игрок заканчивает игру своим ходом тогда и только тогда, когда $x+y+\max(x,\,y,\,1) \ge 59$.

Нам нужен неудачный ход Пети, после которого Ваня заканчивает игру. Иначе говоря, из позиции (5, S) за два хода (сначала Петя, потом Ваня) должно набираться не менее 59 камней. Больше всего даёт двукратное удвоение большей кучи: (5, S) → (5, 2S) → (5, 4S), всего $5+4S$ камней; любая другая пара ходов даёт меньше — например, (5, S+1) → (5, 2S+2) даёт лишь $5+2S+2$, а (5+1, S) → (5+1, 2S) даёт $5+1+2S$.

Условие $5+4S \ge 59$ равносильно $S \ge \frac{59-5}{4} = 13{,}5$, поэтому минимальное подходящее значение $S = 14$.

Проверим его. Сам Петя выиграть не может: удвоив большую кучу, он получит $5+2\cdot14 = 33$ камней, а это меньше 59. Но если он удвоит вторую кучу, возникнет позиция (5, 28); тогда Ваня удваивает её ещё раз, получает (5, 56), то есть 61 камней — не меньше 59, и Ваня выигрывает своим первым ходом.

Проверка перебором:

N = 59
A = 5                            # камней в первой куче

def moves(p):
    x, y = p
    return [(x + 1, y), (2 * x, y), (x, y + 1), (x, 2 * y)]

def win1(p):                      # ходящий выигрывает первым же ходом
    return any(x + y >= N for x, y in moves(p))

for s in range(1, 54):
    p = (A, s)
    # сам Петя выиграть не может, но неудачным ходом дарит победу Ване
    if not win1(p) and any(win1(q) for q in moves(p)):
        print(s)                  # 14
        break

Ответ: 14

Решение:

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

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

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

• $(4,\ 69)$ — Петя удваивает вторую кучу: $4 + 138 = 142$;
• $(2,\ 71)$ — Петя удваивает вторую кучу: $2 + 142 = 144$;
• $(2,\ 138)$ — Петя добавляет два камня: $2 + 140 = 142$.

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

• $(6,\ 68)$ — Петя удваивает вторую кучу: $6 + 136 = 142$;
• $(8,\ 68)$ — Петя удваивает вторую кучу: $8 + 136 = 144$;
• $(4,\ 70)$ — Петя удваивает вторую кучу: $4 + 140 = 144$;
• $(4,\ 136)$ — Петя добавляет два камня: $4 + 138 = 142$.

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

N = 142

def moves(p):
    a, b = p
    return [(a + 2, b), (a, b + 2), (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, 139) if win2((2, s))][:2])   # два наименьших

Ответ: 67 68

Решение:

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

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

В1. Из позиции $(3,\ S)$ игру заканчивают ход «добавить два камня» ($S+5 \ge 122$) и удвоение большей кучи ($2S+3 \ge 122$). Второе условие слабее, поэтому В1 — это все $S \ge 60$.

П1 для начальной позиции — единственное значение $S = 59$; В2 — значения $S = 57$, $S = 58$.

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

При $S = 55$ четыре хода Пети дают позиции $(3,\ 57)$ (В2), $(5,\ 55)$ (В2), $(6,\ 55)$ (В2), $(3,\ 110)$ (В1). Все они для Вани выигрышны не позже второго хода, но три из них — только вторым ходом, поэтому гарантированно выиграть первым ходом Ваня не может. Полный перебор подтверждает, что меньших значений $S$ с таким свойством нет.

Перебор всех $S$ удобно сделать программой:

N = 122

def moves(p):
    a, b = p
    return [(a + 2, b), (a, b + 2), (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))

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

print(min(s for s in range(1, 118) if lose2((3, s))))

Ответ: 55

Решение:

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

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

ID процесса	Время выполнения, мс	Зависит от	Момент завершения, мс
1	4	0	4
2	3	0	3
3	2	1; 2	6
4	3	3	9
5	$t$	0	9
6	5	4; 5	14
7	5	0	5
8	6	7	11
9	5	6; 8	19
10	12	0	12
11	2	10	14
12	2	11	16

Наибольшее значение равно 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

Решение:

Обе команды только уменьшают число на экране, поэтому траектория строго убывает и одно и то же число не может встретиться в ней дважды. Значит, каждая подходящая программа однозначно разбивается на две независимые части: сначала число $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

Решение:

Запрещена только одна конфигурация — две буквы 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

Решение:

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

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

from fnmatch import fnmatch

for k in range(1, 10 ** 10 // 12007 + 1):
    n = 12007 * k
    if fnmatch(str(n), '9*?001?1'):
        print(n, k)

Маска 9*?001?1: число начинается на 9, затем произвольный (возможно, пустой) кусок, затем одна любая цифра, затем 001, затем ещё одна любая цифра и 1 в конце. Программа находит 8 чисел.

Число	Частное от деления на 12007
9098100131	757733
9201000121	766303
9303900111	774873
9406800101	783443
9681400191	806313
9784300181	814883
9887200171	823453
9990100161	832023

Ответ: 9098100131 757733 9201000121 766303 9303900111 774873 9406800101 783443 9681400191 806313 9784300181 814883 9887200171 823453 9990100161 832023

Решение:

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

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

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

В прилагаемом файле $S = 99\,982$, $N = 9996$.

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)

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

3105 75

Ответ: 3105 75

Решение:

Сначала забудем про делимость и возьмём из каждой пары большее число. Полученная сумма $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