Вариант 4 · Октябрь 2026

Решение:

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

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

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

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

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

from itertools import product, permutations

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

# фрагмент таблицы: '.' — незаполненная клетка, второе число — значение F
frag = [('100.', 0),
        ('....', 0),
        ('11..', 0),
        ('.01.', 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

Программа печатает единственную расстановку — wyxz.

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

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

Ответ: wyxz

В таблице «Товар» крахмалу картофельному соответствует артикул 42; единица измерения – килограмм, количество в упаковке – 0,5.

В таблице «Магазин» к Октябрьскому району относятся магазины M1, M5, M6, M10 и M15.

В таблице «Движение товаров» оставляем строки с артикулом 42, типом операции «Поступление», магазином из Октябрьского района и датой с 1 по 8 июня. Таких строк пять: 180, 180, 180, 180 и 170 упаковок, всего 890 упаковок.

Общий вес: 890 × 0,5 = 445 кг.

Ответ: 445.

Решение:

Известно: Н — 1111, З — 110. Найдём свободные вершины двоичного дерева, то есть слова, которые можно добавить без нарушения условия Фано.

• Оба известных слова начинаются с 1, поэтому вся ветвь 0 свободна: можно взять слово 0 (1 знак).
• В ветви 1 свободна вершина 10 (2 знака).
• В ветви 11: слово 110 занято буквой З; в ветви 111 слово 1111 занято буквой Н, свободна вершина 1110 (4 знака).

Получилось ровно три свободных места — 0, 10 и 1110 — как раз для трёх неизвестных букв А, К, Ч.

В слове КАЗАЧКА буква А встречается 3 раза, К — 2 раза, З — 1 раз, Ч — 1 раз. Самое короткое слово отдаём самой частой букве:

Суммарно $3 + 4 + 3 + 4 = 14$ двоичных знаков.

Ответ: 14

Решение:

Алгоритм просто удваивает каждый разряд двоичной записи $N$. Если запись $N$ содержит $m$ разрядов, то запись $R$ содержит ровно $2m$ разрядов, причём она составлена из пар 11 и 00.

Чем короче запись $R$, тем меньше само число, поэтому сначала подбираем минимально возможную длину, а затем — минимальное число такой длины.

При $m=3$ (то есть $N$ от 4 до 7) запись $R$ шестиразрядная, и самое большое такое значение — $N=7\to 111111_2=63$. Оно не больше 63, поэтому шести разрядов не хватает.

Значит, нужно $m\ge 4$. Наименьшее восьмиразрядное $R$ получается из наименьшего четырёхразрядного $N=8=1000_2$:

$1000_2\to 11000000_2=192$.

def alg(n):
    return int(''.join(c * 2 for c in bin(n)[2:]), 2)

print(min(r for r in {alg(n) for n in range(1, 100)} if r > 63))

Ответ: 192

Решение:

За один проход тела цикла Черепаха поворачивает на $150^\circ + 30^\circ = 180^\circ$, поэтому линия замыкается уже за два прохода, а остальные повторения обводят ту же фигуру. Стороны идут в порядке 7, 15, 7, 15, значит нарисован параллелограмм со сторонами 7 и 15 и углами $30^\circ$ и $150^\circ$.

Проследим за движением. После «Направо 30» и «Направо 150» голова смотрит вниз, отрезок длины 7 ведёт из $(0;0)$ в $(0;-7)$. Поворот на $30^\circ$ и отрезок длины 15 дают вершину $\left(-7{,}5;\ -7 - \frac{15\sqrt3}{2}\right)$, затем сторона длины 7 поднимает Черепаху в $\left(-7{,}5;\ -\frac{15\sqrt3}{2}\right)$, и последняя сторона возвращает её в начало координат.

Значит, две стороны параллелограмма вертикальны и имеют длину 7 — они лежат на прямых $x = 0$ и $x = -7{,}5$, а две наклонные стороны лежат на прямых $y = \sqrt3\,x$ и $y = \sqrt3\,x - 7$.

Точки на линиях не учитываем, поэтому $-7{,}5 \lt x \lt 0$, то есть $x$ принимает 7 целых значений: от $-7$ до $-1$. При каждом таком $x$ нужно $\sqrt3\,x - 7 \lt y \lt \sqrt3\,x$. Это интервал длины ровно 7 с иррациональными концами, поэтому целых точек в нём всегда ровно 7. Итого $7 \cdot 7 = 49$ точек. Контроль: площадь параллелограмма равна $7 \cdot 15 \cdot \sin 30^\circ = 52{,}5$.

from math import sqrt

total = 0
for x in range(-7, 0):
    lo, hi = sqrt(3) * x - 7, sqrt(3) * x
    total += len([y for y in range(-30, 5) if lo < y < hi])
print(total)   # 49

Ответ: 49

Решение:

В изображении $480 \cdot 270 = 129600$ пикселей, цвет каждого кодируется 4 байтами, то есть $4 \cdot 8 = 32$ битами.

Объём файла: $129600 \cdot 32 = 4147200$ бит.

Время передачи — это объём, делённый на скорость канала: $\frac{4147200}{14400} = 288$ с.

W, H = 480, 270
bits = W * H * 4 * 8        # объём изображения в битах
print(bits, bits // 14400)  # 4147200 288

Ответ: 288

Решение:

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

Строго убывающая запись состоит из попарно различных цифр, и наоборот — любые три различные цифры выстраиваются по убыванию единственным способом. Поэтому подходящих записей ровно столько, сколько трёхэлементных подмножеств у множества из пяти цифр: $$C_5^3 = \frac{5!}{3!\,2!} = 10.$$

Старшая цифра — наибольшая из трёх, значит она не ноль, и все 10 наборов задают трёхзначные числа.

from itertools import product

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

Ответ: 10

Читаем 16 000 строк по пять чисел. Для каждой строки проверяем, что все пять чисел различны, сортируем их и сравниваем сумму двух наибольших с суммой трёх остальных.

Условиям удовлетворяют 1922 строки.

Ответ: 1922.

Решение:

Маска 255.255.255.252 содержит 30 единиц и 2 нуля, поэтому свободны только два младших бита адреса, а в сети всего $2^2 = 4$ адреса. Адрес сети находим поразрядной конъюнкцией: 188 = 10111100 и 252 = 11111100 дают 10111100, то есть сеть 192.47.41.188.

Нули фиксированных 30 битов останутся при любом узле, поэтому минимум нулей получится, когда оба свободных бита равны единице. Считаем нули фиксированной части: 192 = 11000000 — 6 нулей, 47 = 00101111 — 3 нуля, 41 = 00101001 — 5 нулей, а от байта 188 = 10111100 берутся первые 6 битов 101111 — ещё 1 ноль. Итого $6 + 3 + 5 + 1 = 15$ нулей; они и составляют ответ (адрес 192.47.41.191).

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

base = ip(192, 47, 41, 188)      # 188 = 10111100 уже совпадает с адресом сети
print(min(format(base + i, '032b').count('0') for i in range(2 ** 2)))   # 15

Ответ: 15

Решение:

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

Один идентификатор из 285 символов занимает $285 \cdot 11 = 3135$ бит. Число байт должно быть целым и минимальным: $3135 = 8 \cdot 391 + 7$, поэтому под него отводится 392 байта.

Все 1152 идентификаторов занимают $1152 \cdot 392 = 451584$ байта, то есть $451584 : 1024 = 441$ Кбайт.

import math

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

Ответ: 441

Решение:

На вход подаётся строка вида «5», за которой идут $n$ двоек. Команды применяются строго в указанном порядке, каждая — к первому слева вхождению, и всё тело цикла повторяется, пока в строке есть хотя бы одна из цепочек 52, 2222, 1122. Правило $2222 \to 5$ «сворачивает» четвёрки двоек, а правила $52 \to 11$ и $1122 \to 25$ перемешивают результат, поэтому проследить процесс вручную тяжело — надёжнее в точности повторить его программой и перебрать $n$.

Полезное наблюдение: сумма цифр результата растёт с ростом $n$ — на каждые пять дополнительных двоек она увеличивается примерно на 2. Поэтому перебирать все значения до 10 000 не нужно: все подходящие $n$ заведомо меньше 200.

def run(s):
    while '52' in s or '2222' in s or '1122' in s:
        if '52' in s:
            s = s.replace('52', '11', 1)
        if '2222' in s:
            s = s.replace('2222', '5', 1)
        if '1122' in s:
            s = s.replace('1122', '25', 1)
    return s

for n in range(4, 1000):
    s = run('5' + '2' * n)
    if sum(int(c) for c in s) == 64:
        print(n)

Программа выводит 152, 154 и 156; при больших $n$ сумма цифр уже превышает 64 и к этому значению не возвращается. При $n = 156$ от исходной строки остаются ровно 64 единицы, сумма цифр которых и равна 64. Наибольшее подходящее значение — $n = 156$.

Ответ: 156

Решение:

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

from functools import lru_cache

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

print(f(30, 10) * f(10, 1))

Получаем $f(30, 10) = 12$ и $f(10, 1) = 30$, то есть всего $12 \cdot 30 = 360$ программ.

Ответ: 360

Решение:

Переведём все слагаемые в степени восьмёрки: $4^{2022}=2^{4044}=8^{1348}$, $6\cdot 4^{522}=6\cdot 2^{1044}=6\cdot 8^{348}$, $5\cdot 64^{510}=5\cdot 8^{1020}$, $3\cdot 2^{330}=3\cdot 8^{110}$, $100 = 144_8$. Тогда

$$N = 8^{1348} + 5\cdot 8^{1020} - 6\cdot 8^{348} - 3\cdot 8^{110} - 144_8.$$

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

1, затем 327 нулей, затем 4, затем 671 семёрка, затем 1, затем 237 семёрок, затем 4, затем 107 семёрок, затем 6, 3, 4.

Количество семёрок: $671 + 237 + 107 = 1015$.

Тот же результат даёт программа:

def to_base(n, b):
    s = ''
    while n:
        s = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n % b] + s
        n //= b
    return s

n = 4**2022 - 6 * 4**522 + 5 * 64**510 - 3 * 2**330 - 100
print(to_base(n, 8).count('7'))     # 1015

Ответ: 1015

Решение:

Дизъюнкция ложна, только если ложны все четыре части, то есть одновременно

$x \geq 4$, $x \lt 20$, $y \lt 3x + A$, $y \geq 100$.

Значит формула тождественно истинна тогда и только тогда, когда при всех целых $4 \leq x \leq 19$ и всех $y \geq 100$ выполняется $y \geq 3x + A$.

Самый жёсткий случай — наименьшее $y = 100$ и наибольшее $x = 19$:

$100 \geq 3 \cdot 19 + A = 57 + A \Rightarrow A \leq 43$.

При $A = 43$ для всех $x \leq 19$ имеем $3x + 43 \leq 100 \leq y$, то есть формула истинна. Наибольшее целое $A = 43$.

Ответ: 43

Решение:

Здесь рекурсия опирается только на меньшие аргументы, поэтому значения удобно считать подряд, от $n = 0$ до $n = 39$, складывая их в массив. База: $F(0) = F(1) = F(2) = 1$. Для нечётного $n \gt 2$ берём разность двух предыдущих значений, а для чётного — сумму всех значений от $F(1)$ до $F(n-1)$, то есть накопленную сумму уже посчитанной части массива.

Первые значения: $F(3) = F(2) - F(1) = 0$, $F(4) = F(1) + F(2) + F(3) = 2$, $F(5) = F(4) - F(3) = 2$, $F(6) = 1 + 1 + 0 + 2 + 2 = 6$, $F(7) = 6 - 2 = 4$, $F(8) = 16$. Видно, что напрямую «в лоб» рекурсию писать не стоит: чётная ветвь заново пересчитывает всю историю, поэтому либо заполняем массив снизу вверх, либо кэшируем результаты.

Продолжая таблицу до $n = 39$, получаем $F(39) = 41518080$.

F = [0] * 40
F[0] = F[1] = F[2] = 1
for n in range(3, 40):
    if n % 2 == 1:
        F[n] = F[n - 1] - F[n - 2]
    else:
        F[n] = sum(F[1:n])
print(F[39])   # 41518080

Ответ: 41518080

Решение:

Задача решается одним проходом по файлу, но сначала нужно вычислить «планку» — максимальный элемент последовательности, оканчивающийся на 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}$.

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

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

• между 4-м и 5-м столбцами — в строках 12–16;
• между 7-м и 8-м столбцами — в строках 4–19;
• между 12-м и 13-м столбцами — в строках 2–11;
• между 17-м и 18-м столбцами — в строках 11–18;
• между 19-м и 20-м столбцами — в строках 5–10.

Горизонтальные стены (нельзя идти вниз) стоят между 4-й и 5-й строками в столбцах 16–19, между 11-й и 12-й строками в столбцах 10–12, между 16-й и 17-й строками в столбцах 2–4, между 18-й и 19-й строками в столбцах 13–17 и между 19-й и 20-й строками в столбцах 5–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 == 3 and 15 <= j <= 18) or (i == 10 and 9 <= j <= 11) or
            (i == 15 and 1 <= j <= 3) or (i == 17 and 12 <= j <= 16) or
            (i == 18 and 4 <= j <= 6))

# стена справа от клетки (i, j)
def wall_right(i, j):
    return ((j == 11 and 1 <= i <= 10) or (j == 6 and 3 <= i <= 18) or
            (j == 18 and 4 <= i <= 9) or (j == 16 and 10 <= i <= 17) or
            (j == 3 and 11 <= i <= 15))

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]

best_max = 0
best_min = 10 ** 9
for i in range(N):
    for j in range(N):
        # клетка конечная, если справа и снизу от неё стена (или край поля)
        if (j == N - 1 or wall_right(i, j)) and (i == N - 1 or wall_down(i, j)):
            best_max = max(best_max, MX[i][j])
            best_min = min(best_min, MN[i][j])
print(best_max, best_min)

Конечных клеток оказывается пять; накопленные в них суммы такие:

Наибольшая из всех итоговых сумм — 2255 (правая нижняя клетка), наименьшая — 820 (клетка в 16-й строке и 4-м столбце).

Ответ: 2255 820

Решение:

Позиция игры описывается одним числом $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

Решение:

Сначала опишем позиции, из которых игра заканчивается одним ходом. Из кучи в $n$ камней ($n \le 128$) ходящий выигрывает сразу, если $n + 1 \ge 129$ или $2n \ge 129$, то есть при $n \ge 65$. Значит, при $n$ от 65 до 128 ходящий побеждает немедленно.

Теперь найдём позицию, в которую Пете выгодно попасть после первого хода. Из кучи в 64 камня возможны только 65 и 128 — обе позиции выигрышны для соперника, поэтому 64 проигрышна для того, кто из неё ходит. Более того, 64 — единственная такая позиция: чтобы все ходы вели в диапазон 65–128, нужно $n + 1 \ge 65$, то есть $n \ge 64$, и одновременно $n \le 64$, иначе ходящий выиграл бы сам.

Итак, стратегия Пети — первым ходом получить ровно 64 камня, после чего Ваня вынужденно отдаёт позицию 65 или 128, и Петя добивает вторым ходом (из 65 удвоением до 130, из 128 добавлением камня до 129). Попасть в 64 можно из $S = 63$ (добавить камень) и из $S = 32$ (удвоить). Оба значения не превосходят 64, поэтому первым ходом Петя выиграть не может — второе условие задачи тоже выполнено.

Записываем найденные значения в порядке возрастания: 32 и 63.

def win_now(s):
    return s + 1 >= 129 or 2 * s >= 129

res = []
for s in range(1, 129):
    if win_now(s):                       # Петя выигрывает сразу — не подходит
        continue
    for m in (s + 1, 2 * s):             # ход Пети
        if not win_now(m) and all(win_now(k) for k in (m + 1, 2 * m)):
            res.append(s)
            break
print(res[:2])                           # [32, 63]

Ответ: 32 63

Решение:

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

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

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

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

def over(p):
    return p[0] + p[1] >= 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, 54):
    p = (5, s)
    if over(p):
        break
    if lose2(p) and not lose1(p):
        print(s)
        break

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

• $(6;\ 23)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(12;\ 23)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(13;\ 23)$ — в $(13;\ 46)$; из $(24;\ 23)$ — в $(48;\ 23)$; из $(12;\ 24)$ — в $(12;\ 48)$; из $(12;\ 46)$ — в $(13;\ 46)$);
• $(10;\ 23)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(10;\ 24)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(11;\ 24)$ — в $(11;\ 48)$; из $(20;\ 24)$ — в $(40;\ 24)$; из $(10;\ 25)$ — в $(10;\ 50)$; из $(10;\ 48)$ — в $(11;\ 48)$);
• $(5;\ 24)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(10;\ 24)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(11;\ 24)$ — в $(11;\ 48)$; из $(20;\ 24)$ — в $(40;\ 24)$; из $(10;\ 25)$ — в $(10;\ 50)$; из $(10;\ 48)$ — в $(11;\ 48)$);
• $(5;\ 46)$ — Ваня выигрывает сразу: одним ходом он получает $(5;\ 92)$, а это уже не меньше 59.

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

Ответ: 23

Решение:

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

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

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

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

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

Ответ: 2

Решение.

В файле 1097 рёбер. Рёбра ведут только из вершины с меньшим номером в вершину с большим, поэтому граф ациклический, а порядок 1, 2, …, 100 — топологический: любой путь проходит вершины по возрастанию номеров.

Значит, кратчайшие расстояния считаются одним проходом по вершинам в порядке возрастания номера. Заведём массив d, положим d[1] = 0, остальные — «бесконечность», и для каждой вершины по очереди пробуем улучшить расстояния до её соседей.

edges = []
for line in open('23.txt'):
    a, b, w = line.split()
    edges.append((int(a), int(b), float(w)))

INF = float('inf')
d = [INF] * 101
d[1] = 0
for v in range(1, 101):
    if d[v] == INF:
        continue
    for a, b, w in edges:
        if a == v and d[v] + w < d[b]:
            d[b] = d[v] + w

print(int(d[100]))

Программа печатает 2460. Задание просит целую часть длины, поэтому дробная часть отбрасывается.

Ответ: 2460.

Решение:

В файле записана одна длинная строка из букв T, U, V, W, X, Y, Z (десять миллионов символов). Нужен самый длинный непрерывный кусок этой строки, в котором буква T встречается ровно 100 раз.

Ключевая идея: любой такой кусок содержит ровно сто подряд идущих (по порядку следования в строке) букв T, а между ними и по краям стоят произвольные другие буквы. Значит, достаточно перебрать все окна из 100 подряд идущих букв T и для каждого окна раздвинуть границы максимально широко — влево до предыдущей буквы T (не захватывая её) и вправо до следующей буквы T (тоже не захватывая её). Если слева или справа буквы T больше нет, границей служит начало или конец строки. Из всех полученных длин берём наибольшую.

Для этого сначала выпишем в список номера позиций всех букв T, а затем пройдёмся по нему окном ширины 100.

s = open('24.txt').read().strip()
p = [i for i in range(len(s)) if s[i] == 'T']

best = 0
for k in range(len(p) - 99):
    # окно из ста букв T: p[k] … p[k+99]
    left = p[k - 1] + 1 if k > 0 else 0
    right = p[k + 100] - 1 if k + 100 < len(p) else len(s) - 1
    best = max(best, right - left + 1)

print(best)

Программа работает за один проход по списку позиций, то есть за $O(N)$, и выводит 133. Это означает, что в найденном фрагменте кроме ста букв T стоят ещё 33 буквы других видов.

Ответ: 133

Решение:

Перебирать все числа до $10^{10}$ не нужно: подходящие числа делятся на 1917, поэтому достаточно пройти по кратным — $1917, 2\cdot1917, 3\cdot1917, \ldots$ Их примерно в 1917 раз меньше.

Проверку маски удобно свести к регулярному выражению: символ «?» — это ровно один любой символ, то есть ., а символ «*» — любая (в том числе пустая) последовательность, то есть .*. Маска 3?12?14*5 превращается в шаблон 3.12.14.*5, и число подходит, если запись числа целиком совпадает с шаблоном.

Маска содержит два символа «?» (по одной произвольной цифре каждый) и одну «звёздочку», которая может раскрыться и в пустую строку — поэтому подходят числа разной длины, вплоть до $10^{10}$.

import re

pattern = '3.12.14.*5'
d = 1917
k = d
while k <= 10 ** 10:
    if re.fullmatch(pattern, str(k)):
        print(k, k // d)
    k += d

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

351261495 183235
3212614035 1675855
3412614645 1780185
3712414275 1936575
3912414885 2040905

Ответ: 351261495 183235 3212614035 1675855 3412614645 1780185 3712414275 1936575 3912414885 2040905

Решение:

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

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

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

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

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)

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

3084 61

Ответ: 3084 61

Решение:

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

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

Файл A: сумма больших чисел равна $665848$; она даёт остаток $8$ при делении на 35, то есть уже не делится на 35 — уменьшать ничего не нужно, ответ $665848$.

Файл B: сумма больших чисел равна $665535990$ и делится на 35. Наименьшая ненулевая разность внутри пары, не кратная 35, равна $1653$, поэтому ответ $665535990 - 1653 = 665534337$.

Ответ: 665848 665534337