Вариант 1 · Сентябрь 2026

Решение:

Конъюнкция равна единице, значит $(y \equiv w) \lor z = 0$, откуда сразу $z=0$ и $y \ne w$, и одновременно $w \lor x = 1$.

Подходящих наборов ровно три: $(w,x,y,z)$ равно $(0,1,1,0)$, $(1,0,0,0)$ или $(1,1,0,0)$.

Так как $z=0$ во всех строках, в столбце $z$ не может быть единиц. Единицы есть в первом, втором и четвёртом столбцах, значит $z$ — третий столбец.

Столбцы $w$ и $y$ всюду различаются, а в первой строке первый и четвёртый столбцы оба равны 1, во второй строке оба равны 1 второй и четвёртый столбцы. Значит $w$ и $y$ стоят в первом и втором столбцах, а $x$ — в четвёртом.

Пусть первый столбец — это $y$. Тогда в первой строке $y=1$, $w=0$ и $x=1$ — набор $(0,1,1,0)$. Но в третьей строке второй столбец даёт $w=0$, откуда $y=1$, $z=0$, а из $w \lor x$ следует $x=1$ — снова набор $(0,1,1,0)$. Строки совпали бы, поэтому первый столбец — $w$, а второй — $y$.

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

from itertools import permutations, product

def F(w, x, y, z):
    return not ((y == w) or z) and (w 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, 1],
        [0, 1, None, 1],
        [None, 0, 0, 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

Ответ: wyzx

Решение:

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

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

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

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

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

Ответ: 154332

Решение:

Известно: Н — 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=2$ (то есть $N=2,3$) дают четырёхразрядное $R\le 1111_2=15\lt 32$ — мало. Значит, нужно $m\ge 3$, и запись $R$ содержит не менее шести разрядов.

Наименьшее шестиразрядное $R$ получается из наименьшего трёхразрядного $N=4=100_2$:

$100_2\to 110000_2=48$.

Действительно, $48\gt 32$, а остальные трёхразрядные $N$ дают больше: $N=5\to 110011_2=51$, $N=6\to 111100_2=60$, $N=7\to 111111_2=63$.

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

Ответ: 48

Решение:

Проследим направления. Черепаха рисует шесть отрезков длиной 7, 7, 6, 7, 7 и 20. Второй, третий и четвёртый отрезки идут в одном и том же направлении: перед Вперёд 6 суммарный поворот равен $60^\circ+300^\circ=360^\circ$, то есть направление не меняется, а во втором цикле шаг делается до поворота. Поэтому они склеиваются в одну сторону длины $7+6+7=20$. Между оставшимися четырьмя сторонами повороты по $90^\circ$, и последний отрезок длины 20 приводит Черепаху точно в начало координат.

Получился прямоугольник со сторонами 7 и 20 с вершинами $(0;0)$, $\left(-3{,}5;\,-\tfrac{7\sqrt3}{2}\right)$, $\left(-3{,}5-10\sqrt3;\,10-\tfrac{7\sqrt3}{2}\right)$, $(-10\sqrt3;\,10)$ — приближённо $(0;0)$, $(-3{,}5;\,-6{,}06)$, $(-20{,}82;\,3{,}94)$, $(-17{,}32;\,10)$.

Его площадь $7\cdot 20=140$. Всего целых точек в прямоугольнике вместе с границей 142, но две из них — $(0;0)$ и $(-14;0)$ — лежат на сторонах и по условию не считаются. Остаётся $142-2=140$.

from math import cos, sin, radians

x = y = 0.0
h = 90.0
P = [(0.0, 0.0)]

def R(a):
    global h
    h -= a

def F(n):
    global x, y
    x += n * cos(radians(h))
    y += n * sin(radians(h))
    P.append((x, y))

R(180)
for _ in range(2):
    R(30); F(7); R(60)
R(300); F(6)
for _ in range(2):
    F(7); R(90)
F(20)

poly = [P[0], P[1], P[4], P[5]]      # вершины прямоугольника 7 x 20

def inside(px, py):
    d = []
    for i in range(4):
        ax, ay = poly[i]
        bx, by = poly[(i + 1) % 4]
        d.append((bx - ax) * (py - ay) - (by - ay) * (px - ax))
    return all(t > 1e-9 for t in d) or all(t < -1e-9 for t in d)

print(sum(inside(a, b) for a in range(-25, 10) for b in range(-15, 15)))

Программа подтверждает: 140. Ответ: 140

Решение:

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

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

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

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

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

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

Ответ: 1024

Решение:

В четверичной системе счисления цифры 0, 1, 2, 3. Невозрастающая запись однозначно восстанавливается по набору цифр (с повторами), поэтому число записей равно числу сочетаний с повторениями из 4 цифр по 3: $$\bar{C}_4^3 = C_{4+3-1}^{3} = C_6^3 = 20.$$

Из этих 20 наборов один — 000 — начинается с нуля и трёхзначного числа не даёт. Все остальные годятся, ведь при невозрастающем порядке старшая цифра наибольшая, и она равна нулю только у набора 000.

Итого $20 - 1 = 19$.

from itertools import product

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

Ответ: 19

Решение:

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

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

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

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

import csv

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

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

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

Решение:

Маска 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

Решение:

Пароль набирается из 52-символьного набора строчных и прописных латинских букв, значит мощность алфавита составляет $52$ символа. На один символ нужно минимальное целое $i$, при котором $2^i \ge 52$. Так как $2^{5} = 32 \lt 52 \lt 64 = 2^{6}$, получаем $i = 6$ бит.

Один пароль из 7 символов занимает $7 \cdot 6 = 42$ бита. Число байт должно быть целым и минимальным: $42 = 8 \cdot 5 + 2$, поэтому под него отводится 6 байт.

На всех пользователей отведено одинаковое число байт, поэтому на одного пользователя приходится $500 : 20 = 25$ байт.

Из них 6 байт занимает пароль, значит на дополнительные сведения остаётся $25 - 6 = 19$ байт.

import math

N = 52                        # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(7 * i / 8)      # байт на пароль
print(500 // 20 - b)          # доп. сведения, байт

Ответ: 19

Решение:

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

Прогоним программу на коротких строках «22 + $k$ единиц». Начиная с $k=8$ результаты повторяются с периодом 8: $k=8$ — 1212, $k=9$ — 12121, $k=10$ — 121211, $k=11$ — 11221, $k=12$ — 112211, $k=13$ — 11212, $k=14$ — 112121, $k=15$ — 1121211, $k=16$ — снова 1212.

Остаток $2023$ при делении на 8 равен 7 ($2023 = 8 \cdot 252 + 7$), то есть тот же случай, что и $k=15$. Значит получится строка 1121211; прямой прогон программы это подтверждает.

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

s = "22" + "1" * 2023
while "2111" in s or "1112" in s:
    s = zamenit(s, "111", "1")
    if "21" in s:
        s = zamenit(s, "21", "12")
    else:
        s = zamenit(s, "12", "1")
print(s)   # 1121211

Ответ: 1121211

Решение:

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

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(50, 20) * f(20, 1))

Получаем $f(50, 20) = 12$ и $f(20, 1) = 195$, то есть всего $12 \cdot 195 = 2340$ программ. Ответ: 2340

Решение:

Приведём всё к степеням числа 11: $1331^{650} = \left(11^{3}\right)^{650} = 11^{1950}$, $55\cdot 121^{610} = 5\cdot 11\cdot 11^{1220} = 5\cdot 11^{1221}$, $77\cdot 11^{510} = 7\cdot 11^{511}$, $221 = 191_{11}$. Тогда

$$N = 11^{1950} - 5\cdot 11^{1221} + 7\cdot 11^{511} - 3\cdot 11^{100} - 191_{11}.$$

Разберём заёмы. $11^{1950} - 5\cdot 11^{1221}$ даёт цифру A (то есть 10) в разрядах с 1949-го по 1222-й — это 728 цифр A, — и цифру $11-5=6$ в разряде 1221.

Далее в разряде 511 стоит 7; вычитание $3\cdot 11^{100}$ берёт у неё заём: она становится 6, разряды с 510-го по 101-й превращаются в A (это 410 цифр), а в разряде 100 получается $11-3 = 8$.

Наконец, вычитание $191_{11}$ снова требует заёма: разряд 100 становится 7, разряды с 99-го по 3-й превращаются в A (это 97 цифр), а три младшие цифры равны $1000_{11} - 191_{11}$, то есть $1331 - 221 = 1110 = 91A_{11}$.

Итого запись: 728 цифр A, 6, 709 нулей, 6, 410 цифр A, 7, 97 цифр A, 9, 1, A. Количество цифр A: $728 + 410 + 97 + 1 = 1236$.

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

n = 1331**650 - 55 * 121**610 + 77 * 11**510 - 3 * 11**100 - 221
print(to_base(n, 11).count('A'))    # 1236

Ответ: 1236

Решение:

Обозначим $d = (x \in D)$, $c = (x \in C)$, $a = (x \in A)$. Выражение имеет вид $d \rightarrow ((\neg c \land \neg a) \rightarrow \neg d)$.

Если $d = 0$, внешняя импликация истинна автоматически. Значит всё решается только на точках отрезка $D$.

Пусть $d = 1$. Тогда $\neg d = 0$, и внутренняя импликация $(\neg c \land \neg a) \rightarrow 0$ истинна лишь при ложной посылке: $\neg c \land \neg a = 0$, то есть $c \lor a = 1$.

Итог: каждая точка отрезка $D$ должна лежать в $C$ или в $A$.

Для $D = [17; 58]$ и $C = [29; 80]$ отрезок $C$ накрывает часть $D$ от 29 до 58, а непокрытой остаётся часть $17 \le x \lt 29$. Именно её и должен взять на себя отрезок $A$.

Отрезок, содержащий точку 17 и точки, сколь угодно близкие к 29, обязан содержать весь промежуток $[17; 29]$. Наименьшая длина равна $29 - 17 = 12$.

def ok(a, b, step=0.5):
    for i in range(0, 250):
        x = i * step
        D = 17 <= x <= 58
        C = 29 <= x <= 80
        A = a <= x <= b
        if D and not (C or A):
            return False
    return True

print(ok(17, 29))     # True
print(ok(17.5, 29))   # False

Ответ: 12

Решение:

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

Решение:

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

Решение:

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

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

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

import openpyxl

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

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

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

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

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

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

Ответ: 2167 718

Решение:

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

Нам нужен неудачный ход Пети, после которого Ваня заканчивает игру. Иначе говоря, из позиции (7, S) за два хода (сначала Петя, потом Ваня) должно набираться не менее 77 камней. Больше всего даёт двукратное удвоение большей кучи: (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 77$ равносильно $S \ge \frac{77-7}{4} = 17{,}5$, поэтому минимальное подходящее значение $S = 18$.

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

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

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

Ответ: 18

Решение:

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

Так как $2S \ge S+1$, игрок выигрывает одним ходом тогда и только тогда, когда $2S \ge 161$, то есть при $S \ge 81$.

Найдём проигрышную позицию — такую кучу, из которой ходящий сам выиграть не может, но любой его ход отдаёт победу сопернику. Оба хода должны попадать в зону $\ge 81$; слабее ход «+1», он требует $S+1 \ge 81$, то есть $S \ge 80$. Вместе с $S \le 80$ (иначе игрок выиграл бы сам) получаем единственную такую кучу: 80 камней. Действительно, из 80 камней получаются 81 и 160 камней — до 161 не хватает; зато из 81 камней соперник удваивает и получает 162, а из 160 камней добавляет камень и получает 161.

Значит Петя должен своим первым ходом получить ровно 80 камней:

• ходом «+1»: $S+1 = 80$, то есть $S = 79$;
• ходом «×2»: $2S = 80$, то есть $S = 40$.

Оба значения меньше 81, так что за один ход Петя действительно не выигрывает, а после его хода в позицию «80 камней» Ваня вынужден отдать победу: как бы он ни сходил, Петя следующим ходом добирает кучу до 161. Меньших подходящих значений нет: из кучи, где меньше 40 камней, позицию «80 камней» одним ходом не получить.

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

N = 161

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

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

def lose1(s):                     # ходящий проигрывает: любой его ход даёт сопернику победу
    return not win1(s) and all(win1(t) for t in moves(s))

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

print([s for s in range(1, N) if win2(s)][:2])   # [40, 79]

Ответ: 40 79

Решение:

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

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

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

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

def over(s):
    return s >= N

def win1(p):                  # ходящий выигрывает своим первым ходом
    return any(over(q) for q in moves(p))

def lose1(p):                 # соперник выигрывает своим первым ходом
    return not win1(p) and all(win1(q) for q in moves(p))

def win2(p):                  # ходящий выигрывает своим вторым ходом
    return not win1(p) and any(lose1(q) for q in moves(p))

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

for s in range(1, 205):
    if lose2(s) and not lose1(s):
        print(s)
        break

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

• $46$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $51$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $52$ — в $208$; из $56$ — в $224$; из $204$ — в $205$);
• $50$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $51$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $52$ — в $208$; из $56$ — в $224$; из $204$ — в $205$);
• $180$ — Ваня выигрывает сразу: одним ходом он получает $720$, а это уже не меньше 205.

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

Ответ: 45

Решение:

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

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

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

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

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

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

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

Ответ: 9

Решение.

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

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

Решение:

Нужен самый длинный участок, в котором символ Z встречается не более одного раза. Разрежем файл символами Z на куски, состоящие только из X и Y: s.split('Z'). Тогда искомый участок — это либо один такой кусок (ноль символов Z), либо два соседних куска вместе с разделяющим их символом Z, то есть len(parts[i]) + 1 + len(parts[i+1]).

Остаётся перебрать все пары соседних кусков и взять максимум.

s = open('44250_24.txt').read().strip()
parts = s.split('Z')

ans = max(len(p) for p in parts)
for i in range(len(parts) - 1):
    ans = max(ans, len(parts[i]) + 1 + len(parts[i + 1]))

print(ans)

Можно и одним проходом «методом двух указателей»: двигаем правую границу окна, а при появлении в окне второго Z сдвигаем левую границу за первый Z.

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

mx = 0
left = 0
zpos = []
for i, c in enumerate(s):
    if c == 'Z':
        zpos.append(i)
        if len(zpos) > 1:
            left = zpos.pop(0) + 1
    if i - left + 1 > mx:
        mx = i - left + 1

print(mx)

Обе программы выводят 43. Ответ: 43

Решение:

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

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

import re

pattern = '32.*21.4'
d = 2049
k = d
while k <= 10 ** 9:
    if re.fullmatch(pattern, str(k)):
        print(k, k // d)
    k += d

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

321992154 157146
324082134 158166
326172114 159186
329102184 160616

Ответ: 321992154 157146 324082134 158166 326172114 159186 329102184 160616

Решение:

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

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

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

Файл A: сумма больших чисел равна $650905$; она даёт остаток $13$ при делении на 33, то есть уже не делится на 33 — уменьшать ничего не нужно, ответ $650905$.Файл B: сумма больших чисел равна $666122358$ и делится на 33. Наименьшая ненулевая разность внутри пары, не кратная 33, равна $1622$, поэтому ответ $666122358 - 1622 = 666120736$.Ответ: 650905 666120736