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

Решение:

Функция $F = x \land (y \rightarrow z) \land (\neg y \rightarrow (\neg z \equiv w))$ — это конъюнкция, поэтому разберём, когда она равна 1. Прежде всего обязательно $x = 1$. Дальше два случая:

• если $y = 1$, то из $y \rightarrow z$ следует $z = 1$, а третья скобка выполняется автоматически (её посылка $\neg y = 0$);
• если $y = 0$, то вторая скобка истинна, а третья требует $w = \neg z$, то есть $z$ и $w$ должны быть различны.

Значит, единица получается ровно в четырёх наборах $(x, y, z, w)$: $(1,1,1,0)$, $(1,1,1,1)$, $(1,0,0,1)$, $(1,0,1,0)$.

Шаг 1. Находим столбец x. В первых двух строках фрагмента $F = 1$, значит, в них $x = 1$. В первой строке нули стоят в столбцах 3 и 4 — там $x$ стоять не может. Во второй строке нули стоят в столбцах 2 и 3 — там $x$ тоже стоять не может. Остаётся единственный вариант: $x$ — первый столбец.

Шаг 2. Находим столбец y. В первой строке фрагмента среди $y, z, w$ уже видно два нуля (столбцы 3 и 4), во второй — тоже два (столбцы 2 и 3). Из четырёх «единичных» наборов два нуля среди $y, z, w$ есть только у $(1,0,0,1)$ и $(1,0,1,0)$. В первой строке фрагмента второй столбец равен 1, а во второй строке он равен 0, так что это разные наборы — то есть первая и вторая строки в каком-то порядке и есть эти два набора.

В обоих наборах $y = 0$, а $z$ и $w$ принимают в них разные значения. Столбец 3 равен нулю в обеих строках, поэтому $y$ — третий столбец.

Шаг 3. Различаем z и w. Они стоят во втором и четвёртом столбцах. Используем третью строку фрагмента: там первый столбец равен 1 ($x = 1$), третий равен 1 ($y = 1$), четвёртый равен 1, и при этом $F = 0$. Но при $x = 1$ и $y = 1$ функция равна нулю только если $z = 0$. Значит, в четвёртом столбце стоит не $z$, а $w$; тогда $z$ — второй столбец.

Итого порядок столбцов: $x$, $z$, $y$, $w$.

Тот же ответ даёт короткая программа, перебирающая все 24 расстановки переменных по столбцам:

from itertools import permutations, product

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

frag = [((None, None, 0, 0), 1),
        ((None, 0, 0, None), 1),
        ((1, None, 1, 1), 0)]

def fits(pat, row):
    return all(p is None or p == v for p, v in zip(pat, row))

for p in permutations('xyzw'):
    table = []
    for vals in product([0, 1], repeat=4):
        d = dict(zip(p, vals))
        table.append((vals, int(bool(F(d['x'], d['y'], d['z'], d['w'])))))
    for tri in permutations(table, 3):
        if all(fits(pat, row) and val == f
               for (pat, val), (row, f) in zip(frag, tri)):
            print(''.join(p))
            break

Ответ: xzyw

Решение:

Выручка — это деньги, полученные при продаже, поэтому в таблице «Движение лекарственных средств» нас интересуют только строки с типом операции «Продажа». Цена берётся из таблицы «Препараты» (связь по полю «Артикул»), а сеть аптеки — из таблицы «Аптека» (связь по полю «ID аптеки»).

Шаг 1. В таблице «Аптека» отбираем строки с сетью «Здоровое поколение» и выписываем ID этих аптек.

Шаг 2. В таблице «Препараты» находим пустырник. Важно: под этим названием в базе два разных артикула — упаковка по 20 таблеток за 60 рублей и упаковка по 30 таблеток за 95 рублей. Нужны оба.

Шаг 3. В таблице «Движение лекарственных средств» оставляем строки: тип операции «Продажа», ID аптеки — из шага 1, артикул — один из двух найденных. Вся таблица и так охватывает 1–14 июня, так что дополнительное ограничение по дате ничего не отсекает. Суммируем «Количество упаковок»: 96 упаковок первого артикула и 105 упаковок второго.

Шаг 4. Умножаем количество на цену соответствующего артикула и складываем: $96 \cdot 60 + 105 \cdot 95 = 5760 + 9975 = 15735$ рублей. В таблице это удобно сделать формулой СУММПРОИЗВ по столбцам «Количество упаковок» и подтянутой функцией ВПР цене.

Ответ: 15735

Решение:

Известно: А — 00, Б — 01, В — 100, Г — 1010, Д — 10110. Найдём свободные вершины дерева.

• Ветвь 0 занята целиком: 00 — А, 01 — Б.
• В ветви 10: слово 100 — это В, слово 1010 — это Г; в ветви 1011 слово 10110 — это Д, свободна вершина 10111.
• Ветвь 11 свободна целиком.

Свободные места: 11 (2 знака) и 10111 (5 знаков). Кодовые слова нужны буквам Е и Ж:

• занять оба свободных места: 11 и 10111 — сумма длин $2 + 5 = 7$;
• разбить вершину 11 на 110 и 111 — сумма длин $3 + 3 = 6$.

Второй способ короче, и меньше 6 знаков получить нельзя. Произведение длин при нём равно $3 \cdot 3 = 9$.

Ответ: 9

Решение:

Алгоритм просто удваивает каждый разряд двоичной записи $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

Решение:

Команда Направо 60 выполняется 18 раз, суммарный поворот равен $18\cdot 60^{\circ}=1080^{\circ}$ — это три полных оборота. Значит Черепаха трижды обводит один и тот же контур, а замыкается он уже за 6 команд: внешний угол $60^{\circ}$ — признак правильного шестиугольника со стороной 19.

Стартуя из $(0;0)$ головой вдоль оси $Oy$, получаем вершины $(0;0)$, $(0;19)$, $\left(\tfrac{19\sqrt{3}}{2};\,28{,}5\right)$, $(19\sqrt{3};\,19)$, $(19\sqrt{3};\,0)$, $\left(\tfrac{19\sqrt{3}}{2};\,-9{,}5\right)$.

Шестиугольник выпуклый и обходится по часовой стрелке, поэтому точка лежит строго внутри тогда и только тогда, когда для каждой стороны косое произведение $(x_2-x_1)(y-y_1)-(y_2-y_1)(x-x_1)$ отрицательно; равенство нулю означает, что точка лежит на самой линии, — такие точки не считаем.

from math import sin, cos, radians

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

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

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

for i in range(6):            # шестиугольник замыкается за 6 команд
    F(19); R(60)

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

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

Программа печатает 922. Для контроля: площадь шестиугольника равна $\tfrac{3\sqrt{3}}{2}\cdot 19^{2}\approx 937{,}9$, а на линии лежат 20 целых точек (весь отрезок $x=0$, $0\le y\le 19$).

Ответ: 922

Решение:

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

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

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

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

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

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

Ответ: 16

Решение:

Буквы в алфавитном порядке: А, М, О, Т. Слова четырёхбуквенные, поэтому с каждой фиксированной первой буквы начинается ровно $4^3 = 64$ слова.

Раньше слов на букву О идут все слова на А и на М — это $2 \cdot 64 = 128$ слов. Значит, первое слово на О (это ОААА) имеет номер $128 + 1 = 129$.

Тот же результат через четверичную систему (А=0, М=1, О=2, Т=3): ОААА → $2000_4 = 2 \cdot 4^3 = 128$, номер $128 + 1 = 129$.

from itertools import product

for n, w in enumerate(product('АМОТ', repeat=4), 1):
    if w[0] == 'О':
        print(n, ''.join(w))
        break

Ответ: 129

Решение:

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

В любую свободную ячейку (например, AA1) записываем одну формулу:

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

Функция МАКС находит наибольшую температуру за три месяца, СРЗНАЧ — среднее арифметическое всех значений. В англоязычной версии редактора формула выглядит как =MAX(B2:Y92)-AVERAGE(B2:Y92).

Максимум равен $38{,}0$, среднее — $23{,}7211\ldots$, их разность $38{,}0 - 23{,}7211\ldots = 14{,}2788\ldots$

Целая часть полученного числа равна 14.

Ответ: 14

Решение:

Маска 255.255.255.248 в двоичном виде — 11111111.11111111.11111111.11111000, в ней 29 единиц. Значит, старшие 29 битов у всех адресов сети одинаковы, а на адрес узла остаётся 3 бита, то есть в сети $2^3 = 8$ адресов. Адрес сети: 232 & 248 = 11101000 & 11111000 = 11101000, поэтому это адреса от 123.19.251.232 до 123.19.251.239.

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

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

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

from itertools import product

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

ip = to_bits('123.19.251.232')
mask = to_bits('255.255.255.248')
k = mask.count('1')
head = ip[:k]
addrs = [head + ''.join(t) for t in product('01', repeat=32 - k)]
print(sum(1 for a in addrs if '111' in a))

Ответ: 8

Решение:

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

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

Все 65 536 идентификаторов занимают $65536 \cdot 344 = 22544384$ байта, то есть $22544384 : 1024 = 22016$ Кбайт.

import math

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

Ответ: 22016

Решение:

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

Сначала в строке одни единицы, поэтому работает первая ветка: каждые четыре подряд идущие единицы превращаются в две двойки. Так как $70 = 4 \cdot 17 + 2$, после этого этапа строка состоит из 34 двоек и «хвоста» 11. Дальше замены начинают чередоваться (двойки сворачиваются в единицы, те снова в двойки), поэтому процесс удобнее просто досчитать программой.

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

s = "1" * 70
while "1111" in s or "2222" in s:
    if "1111" in s:
        s = zamenit(s, "1111", "22")
    else:
        s = zamenit(s, "2222", "11")
print(s)   # 22

Полезная проверка: если во входной строке $k$ единиц и $k \equiv 4 \pmod 6$ (то есть $k = 4,\ 10,\ 16,\ 22,\ \ldots$), результат всегда равен 22; здесь $70 = 4 + 6 \cdot 11$.

Ответ: 22

Решение:

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

Пусть $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(31, 12) * f(12, 2))

Получаем $f(31, 12) = 9$ и $f(12, 2) = 19$, то есть всего $9 \cdot 19 = 171$ программ.

Ответ: 171

Решение:

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

$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

Решение:

Раскроем импликации: формула равносильна

$\text{ДЕЛ}(x, A) \lor \neg\text{ДЕЛ}(x, 24) \lor \neg\text{ДЕЛ}(96, x)$.

Опасны только те $x$, которые одновременно делятся на 24 и сами являются делителями числа 96. Делители 96: 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96; из них кратны 24 числа $24,\ 48,\ 96$.

Для каждого из них должно выполняться $\text{ДЕЛ}(x, A)$, то есть $A$ делит и 24, и 48, и 96. Наибольшее такое $A$ — это $\text{НОД}(24, 48, 96) = 24$.

Ответ: 24

Решение:

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

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

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

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

from functools import lru_cache

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

print(F(23))   # 2214271

Ответ: 2214271

Решение:

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

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

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

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

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

print(count, best)   # 2439 998

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

Ответ: 2439 998

Решение:

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

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

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

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

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

Ходы: $s\to s+1$, $s\to s+4$ и $s\to 3s$. Игра заканчивается одним ходом, если $s+1\ge223$ ($s\ge222$), или $s+4\ge223$ ($s\ge219$), или $3s\ge223$ ($s\ge74\tfrac13$, для целого $s$ — $s\ge75$). Значит, из позиции $s\ge75$ ходящий выигрывает одним ходом.

Нужно $S\le74$ (Петя не выигрывает сразу) и одновременно $S+1\ge75$, $S+4\ge75$, $3S\ge75$, то есть $S\ge74$, $S\ge71$ и $S\ge25$. Единственное значение — $S=74$.

Проверка: из 74 Петя получает 75, 78 или 222 — все не меньше 75, поэтому Ваня выигрывает следующим ходом. Сам Петя выиграть сразу не мог: $75\lt223$, $78\lt223$, $222\lt223$.

def win1(s):
    return s + 1 >= 223 or s + 4 >= 223 or 3 * s >= 223

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

Ответ: 74

Решение:

Напомним условия игры: перед игроками две кучи камней, за ход можно добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в одной из куч вдвое; игра заканчивается, когда суммарное количество камней в кучах становится не менее $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

Решение:

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

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

В1. Игру заканчивает ход $S+1 \ge 223$, $S+4 \ge 223$ или $3S \ge 223$; самое слабое условие — $3S \ge 223$, поэтому В1 — это все $S \ge 75$.

П1. Нужно $S \lt 75$, но чтобы каждый ход попадал в В1. Самое сильное требование даёт ход «добавить один камень»: $S+1 \ge 75$, то есть $S \ge 74$. Значит, единственная позиция П1 — это $S = 74$.

В2. Это позиции, из которых есть ход ровно в $74$: $S = 70$, $S = 73$.

Теперь про Ваню. Ваня выигрывает первым или вторым своим ходом при любой игре Пети, если каждый ход Пети приводит в позицию из В1 или В2 (и не заканчивает игру). Гарантированной победы первым ходом у Вани нет, если хотя бы один ход Пети ведёт не в В1, а в В2. Значит, нужно минимальное $S$, у которого все ходы попадают в $\text{В1} \cup \text{В2}$, но не все — в В1.

При $S = 69$ ходы Пети дают $70$ (В2), $73$ (В2), $207$ (В1) — условие выполнено. Меньших значений нет: наименьшая позиция из $\text{В1} \cup \text{В2}$ — это $70$, а ход «добавить один камень» переводит $S$ в $S+1$, поэтому обязательно $S \ge 69$.

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

N = 223

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

def win1(s):                 # В1: выигрыш своим первым ходом
    return any(t >= N for t in moves(s))

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

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

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

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

Ответ: 69

Решение:

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

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

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

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

finish = {}
for i in sorted(data):
    dur, deps = data[i]
    finish[i] = max([finish[d] for d in deps], default=0) + dur

print(max(finish.values()))

Наибольшее значение в последнем столбце равно 14 мс (его даёт процесс 12) — это и есть минимальное время выполнения всей совокупности процессов.

Ответ: 14

Решение.

В файле 1090 рёбер. Рёбра ведут только из вершины с меньшим номером в вершину с большим, поэтому граф ациклический, а порядок 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]))

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

Ответ: 1628.

Цифры 14-ричной системы – это символы 0–9, A, B, C, D; чётные цифры – 0, 2, 4, 6, 8, A, C. Разбиваем файл на максимальные цепочки из допустимых символов; чем длиннее запись, тем больше число, поэтому ищем самую длинную подстроку, начинающуюся с ненулевой цифры и заканчивающуюся чётной цифрой.

Самая длинная цепочка допустимых символов расположена в начале файла и имеет длину 2600. Она начинается с нуля (значащие цифры начинаются со второго символа), а последняя чётная цифра стоит на позиции 2599. Значит запись числа содержит 2598 значащих цифр.

Ответ: 2598.

Решение:

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

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

Граница перебора — $10^{10}$, поэтому среди ответов встречаются как девятизначные, так и десятизначные числа; в таблицу они записываются в порядке возрастания.

import re

pattern = '1.2139.*4'
d = 2023
k = d
while k <= 10 ** 10:
    if re.fullmatch(pattern, str(k)):
        print(k, k // d)
    k += d

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

162139404 80148
1321399324 653188
1421396214 702618
1521393104 752048

Ответ: 162139404 80148 1321399324 653188 1421396214 702618 1521393104 752048

Решение:

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

Шаг 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$ — наибольшая из всех возможных, поэтому если она не делится на 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