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

Решение:

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

Дизъюнкция $( x \land \neg y ) \lor ( y \equiv z ) \lor \neg w$ равна нулю только тогда, когда нулём является каждое слагаемое. Из $\neg w = 0$ следует $w = 1$; из $(y \equiv z) = 0$ следует $y \ne z$; кроме того, $x \land \neg y = 0$. При $y = 0,\ z = 1$ имеем $\neg y = 1$, поэтому обязательно $x = 0$; при $y = 1,\ z = 0$ конъюнкция нулевая сама собой и $x$ произвольно. Подходящих наборов ровно три:

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

Те же три набора нетрудно получить и перебором:

from itertools import product


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


for w, x, y, z in product((0, 1), repeat=4):
    if not F(w, x, y, z):
        print(w, x, y, z)

Ответ: wzyx

Решение:

Количество упаковок в наличии растёт при поступлении и уменьшается при продаже, поэтому искомое увеличение равно разности суммарного поступления и суммарной продажи.

Шаг 1. В таблице «Магазин» отбираем магазины Заречного района и выписываем их ID магазина (их четыре).

Шаг 2. В таблице «Товар» находим строку «Яйцо диетическое» и запоминаем её артикул.

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

Шаг 4. Двумя формулами СУММЕСЛИМН считаем сумму столбца «Количество упаковок, шт.» отдельно по типу операции «Поступление» и по типу «Продажа»: 1420 и 454 упаковки. Увеличение: $1420 - 454 = 966$ упаковок.

Ответ: 966

Решение:

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

• В ветви 0: слово 01 — это А, свободна вершина 00 (2 знака).
• В ветви 1: слово 11 — это Б; в ветви 10 свободна вершина 100 (3 знака), а в ветви 101 слово 1010 — это В, свободна вершина 1011 (4 знака).

Свободных мест три — 00, 100 и 1011, — а кодовые слова нужны четырём буквам Г, Д, Е, Ж. Одну из вершин придётся разбить надвое, и выгоднее разбивать самую короткую: 00 превращается в 000 и 001.

Получаем набор 000, 001, 100, 1011 с суммарной длиной $3 + 3 + 3 + 4 = 13$.

Другие варианты хуже: разбиение вершины 100 даёт 00, 1000, 1001, 1011 — сумма $2 + 4 + 4 + 4 = 14$; разбиение вершины 1011 даёт 00, 100, 10110, 10111 — сумма $2 + 3 + 5 + 5 = 15$.

Ответ: 13

Решение:

Приписывание цифр справа — это умножение на степень четвёрки. Разберём, сколько цифр приписывается в каждом случае. Если $N$ делится на 4, приписываются сразу две цифры, и $R$ примерно в 16 раз больше $N$. Если остаток равен 2 или 3, то удвоенный остаток равен $4 = 10_4$ или $6 = 12_4$ — это тоже две цифры, и снова $R \approx 16N$. И только при остатке 1 удвоенный остаток равен $2 = 2_4$ — одна цифра, поэтому $R = 4N + 2$.

Нам нужно $R \lt 261$, то есть $R$ — маленькое, значит выгоден только случай с остатком 1. Из $4N + 2 \lt 261$ получаем $N \le 64$, а вместе с условием $N \bmod 4 = 1$ наибольшее такое $N$ равно 61.

Проверка: $61 = 331_4$, остаток $61 \bmod 4 = 1$, удвоенный остаток $2 = 2_4$, поэтому $R = 3312_4 = 3 \cdot 64 + 3 \cdot 16 + 1 \cdot 4 + 2 = 246 \lt 261$. Все числа $N \gt 61$ дают больший результат: 62, 63 и 64 удлиняют запись на две цифры (получается $R$ порядка тысячи), а следующий «дешёвый» кандидат $N = 65 = 1001_4$ даёт $10012_4 = 262$, что уже не меньше 261.

def to4(n):
    s = ''
    while n:
        s = str(n % 4) + s
        n //= 4
    return s or '0'

def R(N):
    q = to4(N)
    q += q[-2:] if N % 4 == 0 else to4(2 * (N % 4))
    return int(q, 4)

print(max(N for N in range(1, 1000) if R(N) < 261))   # 61

Ответ: 61

Решение:

Первый цикл рисует прямоугольник со сторонами 27 и 8: $(0;0)\to(0;27)\to(8;27)\to(8;0)\to(0;0)$, то есть область $0\le x\le 8$, $0\le y\le 27$. Целых точек в ней $9\cdot 28=252$.

С поднятым хвостом Черепаха проходит вверх на 4, поворачивает вправо, идёт вправо на 2 и поворачивает налево — она в точке $(2;4)$, голова снова смотрит вверх. Второй цикл рисует прямоугольник со сторонами 17 и 7 с вершинами $(2;4)$, $(2;21)$, $(9;21)$, $(9;4)$, то есть $2\le x\le 9$, $4\le y\le 21$; в нём $8\cdot 18=144$ целых точки.

Прямоугольники перекрываются: общая часть — это $2\le x\le 8$, $4\le y\le 21$, в ней $7\cdot 18=126$ точек. По формуле включений-исключений в объединении фигур $252+144-126=270$ целых точек.

Ответ: 270

Решение:

Объём несжатой звукозаписи равен $V = k \cdot f \cdot b \cdot t$, где $k$ — число каналов, $f$ — частота дискретизации, $b$ — разрешение (число бит на отсчёт), $t$ — длительность.

Фрагмент тот же, поэтому $t$ не изменилась, и достаточно посмотреть, во сколько раз изменился каждый из остальных множителей:

• был 1 канал (моно), стало 2 (стерео) — увеличение в 2 раза;
• разрешение (глубина кодирования) выросло в 3,5 раза;
• частота дискретизации уменьшилась в 2 раза.

Значит объём файла умножился на $2 \cdot 3{,}5 \cdot \frac{1}{2} = 3{,}5$, и новая запись занимает $28 \cdot 3{,}5 = 98$ Мбайт.

size = 28          # Мбайт, первая запись
k = 2 * 3.5 * 0.5  # во сколько раз изменился объём
print(size * k)    # 98.0

Ответ: 98

Решение:

Буквы в алфавитном порядке: А, М, О, Т. Слова четырёхбуквенные, поэтому с каждой фиксированной первой буквы начинается ровно $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 числа.

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

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

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

import csv

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

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

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

Решение:

Маска 255.255.252.0 оставляет свободными 2 младших бита третьего байта и весь четвёртый байт.

Левые два байта: $23 = 00010111_2$ — 4 единицы, $140 = 10001100_2$ — 3 единицы, значит $L = 7$.

Правые два байта: третий байт равен $159 \wedge 252 = 156 = 10011100_2$ (4 единицы) плюс два свободных бита, дающих $k_2$ единиц; четвёртый байт свободен целиком и даёт $k_8$ единиц. Итого $R = 4 + k_2 + k_8$.

Условие $L\ge R$ даёт $7 \ge 4 + k_2 + k_8$, то есть $k_2 + k_8 \le 3$. Перебираем $k_2$:

• $k_2 = 0$ ($C_2^0 = 1$ способ): $k_8\le 3$, это $1 + 8 + 28 + 56 = 93$ варианта, всего 93;
• $k_2 = 1$ ($C_2^1 = 2$ способа): $k_8\le 2$, это $1 + 8 + 28 = 37$, всего $2\cdot 37 = 74$;
• $k_2 = 2$ ($C_2^2 = 1$ способ): $k_8\le 1$, это $1 + 8 = 9$, всего 9.

Сумма: $93 + 74 + 9 = 176$.

ones = lambda x: bin(x).count('1')
count = 0
for b3 in range(156, 160):
    for b4 in range(0, 256):
        if ones(23) + ones(140) >= ones(b3) + ones(b4):
            count += 1
print(count)      # 176

Ответ: 176

Решение:

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

Один идентификатор из 317 символов занимает $317 \cdot 13 = 4121$ бит. Число байт должно быть целым и минимальным: $4121 = 8 \cdot 515 + 1$, поэтому под него отводится 516 байт.

Все 262 144 идентификаторов занимают $262144 \cdot 516 = 135266304$ байта, то есть $135266304 : 1024 : 1024 = 129$ Мбайт.

import math

N = 10 + 4090                  # мощность алфавита
i = math.ceil(math.log2(N))    # бит на один символ
b = math.ceil(317 * i / 8)     # байт на один идентификатор
print(262144 * b // 1048576)   # ответ в Мбайт

Ответ: 129

Решение:

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

Здесь на каждом шаге цикла сначала выполняется заменить(111, 1), а затем одна из замен 21 → 12 или 12 → 1. Прогон на коротких строках «22 + $k$ единиц + 22» показывает, что начиная с $k=8$ результаты повторяются с периодом 8: $k=8$ — 121222, $k=9$ — 1212122, $k=10$ — 12121122, $k=11$ — 1122122, $k=12$ — 11221122, $k=13$ — 1121222, $k=14$ — 11212122, $k=15$ — 112121122, $k=16$ — снова 121222.

Так как $2024 = 8 \cdot 253$, то есть $2024$ кратно 8, ответ такой же, как при $k=8$ и $k=16$, — строка 121222.

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

s = "22" + "1" * 2024 + "22"
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)   # 121222

Ответ: 121222

Решение:

Все команды только увеличивают число на экране, поэтому траектория строго возрастает и ни одно число не может встретиться в ней дважды.

Траектория обязана содержать число $6$, поэтому каждая подходящая программа однозначно распадается на две части: $1 \to 6$ и $6 \to 35$. По правилу умножения ответ равен произведению количеств программ для этих участков.

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$: $f(x, x) = 1$ (пустая программа), $f(x, y) = 0$ при $x \gt y$ (число уже «перескочило» цель, а уменьшать команды не умеют). В остальных случаях перебираем первую команду («прибавить 2», «прибавить 3» или «умножить на 5»):

$$f(x, y) = f(x + 2,\, y) + f(x + 3,\, y) + f(5x,\, y).$$

Число $21$ траектория содержать не должна, поэтому переход в него запрещаем — соответствующее слагаемое отбрасываем.

from functools import lru_cache

@lru_cache(None)
def f(x, y):          # сколько программ переводят число x в число y
    if x == y:
        return 1
    if x > y:
        return 0      # перескочили - назад команд нет
    s = 0
    for z in (x + 2, x + 3, x * 5):
        if z != 21:
            s += f(z, y)
    return s

print(f(1, 6) * f(6, 35))

Получаем $f(1, 6) = 2$ и $f(6, 35) = 846$, то есть всего $2 \cdot 846 = 1692$ программ. Ответ: 1692

Решение:

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

$123x5_{15} = 1 \cdot 15^4 + 2 \cdot 15^3 + 3 \cdot 15^2 + x \cdot 15 + 5$,

$1x233_{15} = 1 \cdot 15^4 + x \cdot 15^3 + 2 \cdot 15^2 + 3 \cdot 15 + 3$.

Сумма: $S = 2 \cdot 15^4 + (x + 2) \cdot 15^3 + 5 \cdot 15^2 + (x + 3) \cdot 15 + 8$.

Заметим, что $15 \equiv 1 \pmod{14}$, поэтому и все степени пятнадцати дают остаток 1. Тогда сумма сравнима с суммой своих коэффициентов:

$S \equiv 2 + (x + 2) + 5 + (x + 3) + 8 = 2x + 20 \pmod{14}$.

Условие $2x + 20 \equiv 0 \pmod{14}$ равносильно $x + 10 \equiv 0 \pmod 7$, то есть $x \equiv 4 \pmod 7$. В алфавите 15-ричной системы (цифры $0 \ldots 14$) подходят $x = 4$ и $x = 11$; наименьшее — $x = 4$.

При $x = 4$: $S = 2 \cdot 50625 + 6 \cdot 3375 + 5 \cdot 225 + 7 \cdot 15 + 8 = 122738$, и $122738 : 14 = 8767$.

for x in range(15):
    a = 15**4 + 2*15**3 + 3*15**2 + x*15 + 5
    b = 15**4 + x*15**3 + 2*15**2 + 3*15 + 3
    if (a + b) % 14 == 0:
        print(x, (a + b) // 14)

Ответ: 8767

Решение:

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

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

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

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

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

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

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

Ответ: 15

Решение:

Число 23 нечётное, поэтому $F(23) = 2 + 2 \cdot F(21)$. Нечётная ветка уменьшает аргумент сразу на 2, значит вся цепочка идёт только по нечётным числам, и формула для чётных $n$ не понадобится вовсе.

База: $F(1) = 1$. Далее каждый раз удваиваем предыдущее значение и прибавляем 2:

Здесь $F(3) = 2 + 2 \cdot 1 = 4$, $F(5) = 2 + 2 \cdot 4 = 10$ и так далее.

Можно заметить закономерность: величина $F(n) + 2$ на каждом шаге удваивается, поэтому $F(2k + 1) = 3 \cdot 2^{k} - 2$. При $k = 11$ получаем $3 \cdot 2048 - 2 = 6142$.

import sys
sys.setrecursionlimit(10000)

def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + 3 * F(n - 1)
    return 2 + 2 * F(n - 2)

print(F(23))   # 6142

Ответ: 6142

Решение:

Задача решается одним проходом по файлу, но сначала нужно вычислить «планку» — максимальный элемент последовательности, оканчивающийся на 13. Число оканчивается на 13 тогда и только тогда, когда остаток от его деления на 100 равен 13. Для данного файла эта планка равна 98413.

Дальше перебираем все тройки идущих подряд элементов (то есть окна вида $a_i, a_{i+1}, a_{i+2}$) и проверяем два условия: ровно два числа тройки трёхзначные, то есть лежат в диапазоне от 100 до 999, и сумма всех трёх чисел не превосходит найденной планки. Считаем такие тройки и параллельно запоминаем наибольшую из их сумм.

Подходящих троек оказывается 959, а наибольшая сумма среди них равна 97471.

a = [int(line) for line in open('17.txt')]

limit = max(x for x in a if x % 100 == 13)   # 98413

count = 0
best = 0
for i in range(len(a) - 2):
    t = a[i:i + 3]
    if sum(100 <= x <= 999 for x in t) == 2 and sum(t) <= limit:
        count += 1
        best = max(best, sum(t))

print(count, best)   # 959 97471

Ответ: 959 97471

Решение:

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

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

В приложенном файле поле имеет размер $16\times16$. Единственная внутренняя стена (утолщённая линия) — горизонтальная, между 6-й и 7-й строками в столбцах с 5-го по 10-й: в эти клетки 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 == 5 and 4 <= j <= 9

# стена справа от клетки (i, j) — вертикальных внутренних стен нет
def wall_right(i, j):
    return False

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(MN[N - 1][N - 1], MX[N - 1][N - 1])

Программа выводит 508 731: минимальная сумма равна 508, максимальная — 731. В ответе сначала записывается минимальная сумма, затем максимальная. Ответ: 508 731

Решение:

Позиция игры — пара чисел $(a,b)$. За один ход можно прибавить 2 камня к одной из куч или удвоить одну из куч. Игра заканчивается, когда суммарное количество камней достигает 122.

Из позиции $(a,b)$ ходящий заканчивает игру, если $a+b+2\ge122$, или $2a+b\ge122$, или $a+2b\ge122$, то есть если $(a+b)+\max(a,b,2)\ge122$: выгоднее всего удвоить бо́льшую кучу. Нужно наименьшее $S$, при котором у Пети есть ход, не заканчивающий игру, после которого Ваня выигрывает сразу.

Из начальной позиции $(3,S)$ Петя может получить позиции $(5,S)$, $(6,S)$, $(3,S+2)$ и $(3,2S)$. Самая опасная — $(3,2S)$: Ваня удваивает вторую кучу ещё раз и получает сумму $3+4S$. Условие $3+4S\ge122$ даёт $4S\ge119$, $S\ge29{,}75$, то есть $S\ge30$.

Другие ходы требуют большего $S$: из $(3,S+2)$ сумма после хода Вани равна $2S+7\ge122$, откуда $S\ge58$; из $(6,S)$ — $6+2S\ge122$, $S\ge58$; из $(5,S)$ — $5+2S\ge122$, $S\ge59$.

Проверим $S=30$. Петя ходит $(3,30)\to(3,60)$: сумма 63, игра продолжается. Ваня удваивает: $(3,120)$, сумма $123\ge122$ — победа первым ходом. Сам Петя выиграть сразу не мог: $3+30+30=63\lt122$. При $S\lt30$ такая ситуация невозможна.

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

def win1(p):
    return any(x + y >= 122 for x, y in moves(p))

for S in range(1, 118):
    if any(x + y < 122 and win1((x, y)) for x, y in moves((3, S))):
        print(S)
        break

Ответ: 30

Решение:

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

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

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

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

• ходом «+1»: $S+1 = 114$, то есть $S = 113$;
• ходом «×2»: $2S = 114$, то есть $S = 57$.

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

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

N = 229

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])   # [57, 113]

Ответ: 57 113

Решение:

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

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

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

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

def over(p):
    return p[0] * p[1] >= N

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

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

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

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

for s in range(1, 143):
    p = (1, s)
    if over(p):
        break
    if lose2(p) and not lose1(p):
        print(s)
        break

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

• $(2;\ 69)$ — Ваня выигрывает сразу: одним ходом он получает $(3;\ 69)$, а это уже не меньше 144;
• $(1;\ 70)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(1;\ 71)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(2;\ 71)$ — в $(3;\ 71)$; из $(1;\ 72)$ — в $(2;\ 72)$; из $(1;\ 142)$ — в $(2;\ 142)$);
• $(1;\ 138)$ — Ваня выигрывает сразу: одним ходом он получает $(2;\ 138)$, а это уже не меньше 144.

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

Ответ: 69

Решение:

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

Для данных из файла получается такое расписание (12 процессов):

Теперь идём по шкале времени по одной миллисекунде и считаем, сколько процессов активно в каждый момент. Четыре процесса одновременно работают на двух участках: с 0 до 3 мс это процессы 1, 2, 9 и 10, а с 9 до 13 мс — процессы 4, 5, 11 и 12. Больше четырёх процессов не работает никогда.

Складываем длины этих участков: $3 + 4 = 7$ мс.

rows = [(1, 4, []), (2, 3, []), (3, 5, [1, 2]), (4, 7, [3]),
        (5, 6, [3]), (6, 2, [5]), (7, 5, [4, 6]), (8, 2, [7]),
        (9, 7, []), (10, 8, []), (11, 6, [9]), (12, 6, [10])]

dur = {i: t for i, t, d in rows}
dep = {i: d for i, t, d in rows}
start, finish = {}, {}

def calc(i):
    if i not in finish:
        start[i] = max([calc(j) for j in dep[i]], default=0)
        finish[i] = start[i] + dur[i]
    return finish[i]

for i in dur:
    calc(i)

total = 0
for t in range(max(finish.values())):        # такты по 1 мс
    if sum(start[i] <= t < finish[i] for i in dur) == 4:
        total += 1
print(total)   # 7

Ответ: 7

Решение.

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

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

Решение:

Из букв A, C, D, F, O гласные — это A и O, согласные — C, D, F. Нас интересует самая длинная цепочка вида «согласная+гласная», «согласная+гласная», … — то есть участок чётной длины, разбитый на пары, каждая из которых состоит из согласной и следующей за ней гласной. В ответе нужно указать количество таких пар.

Идём по файлу с позиции $i$. Если s[i] — согласная, а s[i+1] — гласная, то это очередная пара цепочки: увеличиваем счётчик и перескакиваем через оба символа (i += 2). Иначе цепочка обрывается: обнуляем счётчик и сдвигаемся на один символ.

s = open('59133_24.txt').read().strip()
glas = 'AO'

mx = cur = 0
i = 0
while i < len(s) - 1:
    if s[i] not in glas and s[i + 1] in glas:
        cur += 1
        i += 2
    else:
        cur = 0
        i += 1
    if cur > mx:
        mx = cur

print(mx)

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

Решение:

Переведём маску 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

Решение:

Сортируем диаметры по убыванию и жадно строим башню, начиная с самого большого коржа: очередной корж кладём, если его диаметр хотя бы на 4 меньше диаметра последнего положенного. Обратите внимание: пример в условии разобран для порога 3, но в самом задании требуется разница не менее 4 единиц.

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

f = open('26.txt')
n = int(f.readline())
a = sorted((int(x) for x in f), reverse=True)

cnt = 0
last = None
for x in a:
    if last is None or x <= last - 4:
        cnt += 1
        last = x
print(cnt, last)

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

2172 50

Ответ: 2172 50

Решение:

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