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

Решение:

Конъюнкция равна единице, только если истинны все множители: $z=1$, $w=0$ и $y \rightarrow x = 1$ (то есть сочетания $y=1$, $x=0$ быть не может).

Таких наборов ровно три: $(w,x,y,z)$ равно $(0,0,0,1)$, $(0,1,0,1)$ или $(0,1,1,1)$. Это и есть три строки фрагмента в каком-то порядке.

Во всех строках $w=0$, поэтому в столбце $w$ не должно быть единиц. В первом, втором и третьем столбцах единицы есть, значит $w$ — четвёртый столбец (он и оставлен полностью пустым).

Во второй и третьей строках второй столбец равен 1. Если бы это была переменная $y$, то в обеих строках $y=1$, а тогда из $y \rightarrow x$ следует $x=1$; вместе с $z=1$ и $w=0$ обе строки оказались бы одним и тем же набором $(0,1,1,1)$, чего быть не может. Переменной $z$ второй столбец тоже не соответствует: в первой строке там 0, а $z=1$ всегда. Значит второй столбец — $x$.

Остались $y$ и $z$ в первом и третьем столбцах. В первой строке первый столбец равен 1, а второй равен 0, то есть $x=0$. Если бы первый столбец был переменной $y$, получилось бы $y=1$ при $x=0$ — нарушение условия $y \rightarrow x$. Значит первый столбец — $z$, а третий — $y$.

Тот же результат даёт перебор всех 24 расстановок переменных по столбцам:

from itertools import permutations, product

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

rows = [t for t in product([0, 1], repeat=4) if F(*t)]   # наборы (w, x, y, z) с F = 1

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

for cols in permutations('wxyz'):        # cols[i] — переменная в i-м столбце
    for order in permutations(rows, 3):  # какой набор какой строке фрагмента
        val = [dict(zip('wxyz', t)) for t in order]
        if all(frag[r][i] is None or frag[r][i] == val[r][cols[i]]
               for r in range(3) for i in range(4)):
            print(''.join(cols))
            break

Ответ: zxyw

Решение:

В условии заданы ограничения сразу на модель (женские прямые брюки) и на ткань (белая джинса или белая льняная ткань), поэтому фильтруем оба справочника, а затем — таблицу «Готовый товар».

Шаг 1. В таблице «Продукция» отбираем строки с наименованием «брюки прямые» и категорией потребителей «женщины». Такая модель одна — запоминаем её ID товара.

Шаг 2. В таблице «Ткани» отбираем белые ткани, у которых название «джинса» либо сырьё «лён». Подходят ровно две: белая джинса и белый лён.

Шаг 3. В таблице «Готовый товар» оставляем строки, у которых «ID товара» совпадает с найденным на шаге 1, а «ID ткани» — с одним из двух найденных на шаге 2. Остаётся всего две записи: 89 штук по 730 рублей и 91 штука по 982 рубля.

Шаг 4. Считаем общую стоимость: $89 \cdot 730 + 91 \cdot 982 = 64970 + 89362 = 154332$ рубля.

Ответ: 154332

Решение:

Условие Фано означает, что ни одно кодовое слово не является началом другого. Удобно представлять коды как вершины двоичного дерева: выбор кодового слова «закрывает» всю ветку, которая из него растёт, и все его начала.

Буква В кодируется словом 1, поэтому никакой другой код не может начинаться с 1: коды букв Е, Н и Р начинаются с 0. Буква М кодируется словом 001, поэтому оставшиеся коды не могут быть словами 0 и 00 (они были бы началом кода 001) и не могут начинаться с 001. Свободными остаются ветка 01 и ветка 000 со всеми их продолжениями.

В слове ВЕРМЕЕР буква Е встречается 3 раза, Р — 2 раза, В и М — по одному разу, а буква Н не встречается ни разу. Значит самый короткий свободный код надо отдать самой частой букве Е, а букве Н можно дать сколь угодно длинный код.

Кратчайший свободный код — 01 (длина 2), отдаём его букве Е. Тогда для Р и Н остаётся только ветка 000. Само слово 000 занять нельзя: тогда второй букве не осталось бы кода. Берём его продолжения: Р — 0000, Н — 0001 (по 4 знака). Набор кодов 1, 001, 01, 0000, 0001 условию Фано удовлетворяет.

Считаем длину сообщения: В даёт $1 \cdot 1 = 1$ знак, Е — $3 \cdot 2 = 6$ знаков, Р — $2 \cdot 4 = 8$ знаков, М — $1 \cdot 3 = 3$ знака. Всего $1 + 6 + 8 + 3 = 18$.

Меньше получить нельзя. Код буквы Е не может состоять из одного знака: единственный вариант 0 является началом кода 001. Если длина кода Е равна 2, то это обязательно 01, и тогда для Р и Н остаётся одна ветка 000, из которой два разных кода короче четырёх знаков не получить, — это разобранный случай с ответом 18. Если же длина кода Е равна 3, то и код Р не короче 3 знаков, и общая длина будет не меньше $1 + 9 + 6 + 3 = 19$.

Ответ: 18

Решение:

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

• $r=1$: $4N+2\lt 369\Rightarrow N\le 91$. Наибольшее число вида $4k+1$, не превосходящее 91, — это $N=89$, для него $R=358$.
• $r=2$: $16N+4\lt 369\Rightarrow N\le 22$. Подходит $N=22$, $R=356$.
• $r=3$: $16N+6\lt 369\Rightarrow N\le 22$. Наибольшее число вида $4k+3$ — это $N=19$, $R=310$.
• $r=0$: $16N\lt 369\Rightarrow N\le 23$. Подходит $N=20$, $R=16\cdot 20+4=324$.

Наибольшее из чисел 89, 22, 19, 20 — это 89.

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(max(n for n in range(1, 1000) if alg(n) < 369))

Ответ: 89

Решение:

Повтори 2 [Вперёд 10 Направо 90 Вперёд 20 Направо 90]: $(0;0)\to(0;10)\to(20;10)\to(20;0)\to(0;0)$. Первый прямоугольник — $0\le x\le 20$, $0\le y\le 10$; голова после цикла снова направлена вдоль оси $Oy$.

С поднятым хвостом: Вперёд 3 даёт $(0;3)$; Направо 90 — голова вдоль $Ox$; Вперёд 5 даёт $(5;3)$; Налево 90 возвращает голову вдоль $Oy$.

Повтори 2 [Вперёд 70 Направо 90 Вперёд 80 Направо 90] из точки $(5;3)$ рисует второй прямоугольник: $5\le x\le 85$, $3\le y\le 73$.

Пересечение прямоугольников — это $5\le x\le 20$ и $3\le y\le 10$, то есть $20-5+1=16$ значений $x$ и $10-3+1=8$ значений $y$ (границы включаются).

$16\cdot 8=128$.

Ответ: 128

Решение:

В изображении $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. Тогда пятибуквенное слово превращается в пятизначное число в пятеричной системе счисления, а номер слова в списке на единицу больше значения этого числа (первому слову ААААА соответствует число 0).

Слову УСССС отвечает набор цифр 4, 3, 3, 3, 3:

$$4 \cdot 5^4 + 3 \cdot 5^3 + 3 \cdot 5^2 + 3 \cdot 5 + 3 = 2500 + 375 + 75 + 15 + 3 = 2968.$$

Значит, слово УСССС стоит под номером $2968 + 1 = 2969$.

from itertools import product

alpha = 'АПРСУ'          # буквы уже в алфавитном порядке
answer = 0
for i, w in enumerate(product(alpha, repeat=5), 1):
    s = ''.join(w)
    if s.count('У') <= 1 and 'АА' not in s:
        answer = i        # запоминаем последнее подходящее слово
print(answer)   # 2969

Ответ: 2969

Решение:

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

Решение:

Открываем прилагаемый файл в текстовом редакторе и пользуемся поиском (Ctrl+F).

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

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

Кроме того, по условию не учитываются сноски (примечания), поэтому считаем только по основному тексту.

«Найти все» даёт единственное совпадение — строка «Цензуре долг свой заплачу».

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

import re

text = open('onegin.txt', encoding='utf-8').read()
print(len(re.findall(r'\bдолг\b', text)) + len(re.findall(r'\bДолг\b', text)))

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

Решение:

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

Один идентификатор из 108 символов занимает $108 \cdot 7 = 756$ бит. Число байт должно быть целым и минимальным: $756 = 8 \cdot 94 + 4$, поэтому под него отводится 95 байт.

Все 25 600 идентификаторов занимают $25600 \cdot 95 = 2432000$ байт, то есть $2432000 : 1024 = 2375$ Кбайт.

import math

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

Ответ: 2375

Решение:

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

Посмотрим, как меняется количество единиц. Замена (11111, 15) убирает пять единиц и добавляет одну, то есть уменьшает число единиц ровно на 4, а замена (15, 1) число единиц не меняет (она лишь убирает пятёрку). Значит остаток количества единиц при делении на 4 сохраняется в течение всей работы программы.

Каждая пятёрка появляется только в паре «15», и после неё всегда стоит единица, поэтому в конце работы (когда не найдено ни 11111, ни 15) пятёрок в строке не остаётся вовсе, а единиц остаётся от 1 до 4. Так как $65 = 4 \cdot 16 + 1$, останется ровно одна единица.

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

s = "1" * 65
while "11111" in s or "15" in s:
    if "11111" in s:
        s = zamenit(s, "11111", "15")
    else:
        s = zamenit(s, "15", "1")
print(s)   # 1

Ответ: 1

Решение:

Маска 255.255.248.0 содержит $8+8+5=21$ единицу, поэтому первые 21 бит адреса фиксированы сетью, а последние 11 битов можно выбирать произвольно. Двоичная запись адреса сети: 10100010 00000001 00011000 00000000, её фиксированная часть — 101000100000000100011, и в ней стоит 6 единиц.

Единицы в фиксированной части изменить нельзя, поэтому сумма единиц будет наибольшей, когда все 11 свободных битов равны единице. Получаем $6+11=17$.

net = 162 * 256**3 + 1 * 256**2 + 24 * 256
host = 32 - 21
print(max(bin(net + k)[2:].zfill(32).count('1')
          for k in range(2 ** host)))   # 17

Ответ: 17

Решение:

Приведём всё к степеням пятёрки: $25^{600} = 5^{1200}$, $125 = 5^{3}$. Тогда

$$N = 5^{2019} + 5^{1200} - 5^{1019} - 5^{3}.$$

Сначала $5^{1200} - 5^{1019} = 5^{1019}\left(5^{181}-1\right)$: разряды с 1199-го по 1020-й становятся четвёрками (180 цифр), а в разряде 1019 получается $5-1 = 4$.

Затем вычитаем $5^{3}$: заём берётся у этой четвёрки, она становится тройкой, разряды с 1018-го по 4-й превращаются в четвёрки, а в разряде 3 получается $5-1=4$. Значит, четвёрки занимают разряды с 1018-го по 3-й — это 1016 цифр, а разряды 2, 1, 0 нулевые.

Итого запись: 1, 819 нулей, 180 четвёрок, 3, 1016 четвёрок, 3 нуля. Четвёрок: $180 + 1016 = 1196$.

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

n = 5**2019 - 5**1019 + 25**600 - 125
print(to_base(n, 5).count('4'))     # 1196

Ответ: 1196

Решение:

Конъюнкция $(x \lt A) \land (y \lt A) \land (x \cdot y \gt 1200)$ истинна, только когда истинны все три множителя. Тождественная ложность означает, что не существует целых положительных $x, y$, для которых одновременно

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

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

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

Так как $34^{2} = 1156 \le 1200$, а $35^{2} = 1225 \gt 1200$, получаем $A - 1 \le 34$, то есть $A \le 35$. При $A = 35$ максимум произведения равен $34 \cdot 34 = 1156$, условие $x \cdot y \gt 1200$ невыполнимо и конъюнкция тождественно ложна; при $A = 36$ пара $x = y = 35$ даёт $1225 \gt 1200$ и делает выражение истинным.

best = 0
for A in range(0, 100):
    if not any(x < A and y < A and x * y > 1200
               for x in range(1, A + 1) for y in range(1, A + 1)):
        best = A
print(best)   # 35

Ответ: 35

Решение:

Выражение сворачивается, если аккуратно раскрыть значения по рекуррентному правилу $F(n) = n(n-1) + F(n-1) + F(n-2)$.

При $n = 2023$: $F(2023) = 2023 \cdot 2022 + F(2022) + F(2021)$, поэтому $F(2023) - F(2021) = 2023 \cdot 2022 + F(2022)$.

При $n = 2022$: $F(2022) = 2022 \cdot 2021 + F(2021) + F(2020)$, а при $n = 2021$: $F(2021) = 2021 \cdot 2020 + F(2020) + F(2019)$. Подставив второе в первое, получаем $F(2022) = 2022 \cdot 2021 + 2021 \cdot 2020 + 2F(2020) + F(2019)$.

Тогда все неизвестные значения сокращаются:

$$F(2023) - F(2021) - 2F(2020) - F(2019) = 2023 \cdot 2022 + 2022 \cdot 2021 + 2021 \cdot 2020 = 4090506 + 4086462 + 4082420 = 12259388.$$

Проверка программой (значения растут очень быстро, но в Python целые числа длинные, поэтому переполнения не будет):

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

print(F[2023] - F[2021] - 2 * F[2020] - F[2019])   # 12259388

Ответ: 12259388

Решение:

Загружаем числа из файла в список и перебираем все пары соседних элементов.

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

Условие пары: обе последние цифры нечётные и разные. Считаем количество таких пар и минимальное произведение модулей их элементов.

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

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

print(count, best)   # 864 4683

Подходящих пар 864, наименьшее произведение модулей равно 4683.Ответ: 864 4683

Решение:

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

Пусть $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$; стены обозначены утолщёнными линиями. Внутренних стен две:

• вертикальная — между 6-м и 7-м столбцами, в строках с 4-й по 15-ю (из этих клеток 6-го столбца нельзя пойти вправо);
• горизонтальная — между 17-й и 18-й строками, в столбцах с 12-го по 17-й (из этих клеток 17-й строки нельзя пойти вниз).

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

# стена справа от клетки (i, j)
def wall_right(i, j):
    return j == 5 and 3 <= i <= 14

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

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

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

Решение:

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

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

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

Проверим его. Сам Петя выиграть не может: удвоив большую кучу, он получит $7+2\cdot24 = 55$ камней, а это меньше 101. Но если он удвоит вторую кучу, возникнет позиция (7, 48); тогда Ваня удваивает её ещё раз, получает (7, 96), то есть 103 камней — не меньше 101, и Ваня выигрывает своим первым ходом.

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

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

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, 94):
    p = (A, s)
    # сам Петя выиграть не может, но неудачным ходом дарит победу Ване
    if not win1(p) and any(win1(q) for q in moves(p)):
        print(s)                  # 24
        break

Ответ: 24

Решение:

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

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

В1. Из кучи в $S$ камней игру заканчивают ходы $S+1 \ge 29$ или $2S \ge 29$. Второе условие слабее, поэтому В1 — это все $S \ge 15$.

П1. Нужно, чтобы $S \lt 15$, но оба хода попадали в В1: $S+1 \ge 15$ и $2S \ge 15$. Первое неравенство даёт $S \ge 14$, поэтому единственная позиция П1 — это $S = 14$ (проверка: $2 \cdot 14 = 28 \lt 29$, игра ещё не окончена).

В2. Петя не выигрывает сразу, но обязан перевести кучу ровно в $14$ камней. Это возможно двумя способами: $S+1 = 14$, откуда $S = 13$, и $2S = 14$, откуда $S = 7$. Оба значения меньше $15$, то есть за один ход Петя действительно не выигрывает.

После хода Пети в позицию $14$ Ваня любым ходом получает $15$ или $28$ камней — в обоих случаях игра ещё не окончена, но Петя следующим ходом доводит кучу до $29$ и более ($15 \cdot 2 = 30 \ge 29$ и $28 + 1 = 29 \ge 29$). Это и есть выигрыш вторым ходом.

Тот же ответ даёт короткая программа:

N = 29

def moves(s):
    return [s + 1, 2 * 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))

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

Ответ: 7 13

Решение:

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

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

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

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

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

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

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

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

N = 202

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

Ответ: 62

Решение:

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

Решение:

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

Решение:

В файле записана одна длинная строка из букв 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

Решение:

Переведём маску 1?2157*4 в условие на строку десятичной записи числа: первая цифра равна 1; вторая цифра любая (символ «?»); далее подряд идут цифры 2157; затем произвольная, возможно пустая, последовательность цифр (символ «*»); последняя цифра равна 4. Отсюда сразу видно, что в числе не менее семи цифр.

Перебирать все числа до $10^{10}$ незачем: достаточно пройти только по кратным 2024, тогда делимость выполняется автоматически, а проверять останется лишь совпадение с маской. Таких кратных около пяти миллионов, программа отрабатывает за секунды.

for n in range(2024, 10**10 + 1, 2024):
    s = str(n)
    if len(s) >= 7 and s[0] == '1' and s[2:6] == '2157' and s[-1] == '4':
        print(n, n // 2024)

Условие len(s) >= 7 гарантирует, что блок 2157 и завершающая цифра 4 не накладываются друг на друга, то есть «*» действительно может быть пустой последовательностью. Программа находит 11 чисел; выводим их по возрастанию вместе с частными:

Ответ: 142157664 70236 1021575544 504731 1121571264 554136 1221577104 603546 1321572824 652951 1421578664 702361 1521574384 751766 1621570104 801171 1721575944 850581 1821571664 899986 1921577504 949396

Решение:

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

Первую величину — наибольшее число мероприятий — даёт стандартный приём: отсортировать заявки по времени окончания. Но нам нужен ещё и максимальный перерыв между двумя последними мероприятиями, поэтому удобнее не жадный проход, а динамическое программирование по отсортированному списку: пусть dp[i] — наибольшее количество мероприятий в расписании, последним в котором стоит мероприятие i. Тогда dp[i] на единицу больше лучшего dp[j] среди заявок j, которые заканчиваются не позже начала i. Максимум по всем dp[i] и есть искомое количество $K$.

Теперь перерыв. Два последних мероприятия — это пара (j, i), в которой i завершает расписание длины $K$ (то есть dp[i] = K), а j предшествует ему в расписании длины $K-1$ (то есть dp[j] = K-1) и заканчивается не позже начала i. Перерыв равен разности «начало i минус конец j»; перебираем все такие пары и берём наибольшую разность.

f = open('26.txt')
n = int(f.readline())
a = []
for i in range(n):
    start, end = map(int, f.readline().split())
    a.append((end, start))      # сортировать будем по времени окончания
a.sort()

dp = [1] * n
for i in range(n):
    for j in range(i):
        if a[j][0] <= a[i][1] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1

k = max(dp)

gap = 0
for i in range(n):
    if dp[i] != k:
        continue
    for j in range(n):
        if dp[j] == k - 1 and a[j][0] <= a[i][1]:
            gap = max(gap, a[i][1] - a[j][0])

print(k, gap)

Проверим программу на типовом примере из условия: она выдаёт 3 и 20 — ровно то, что написано в задании. На данных из прилагаемого файла (990 заявок) получаем 32 мероприятия и перерыв 15 минут. Квадратичный перебор здесь допустим: при $N \le 1000$ это около миллиона проверок. Ответ: 32 15

Решение:

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