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

Решение:

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

Оба слагаемых выражения $\neg ( x \lor ( w \rightarrow y ) ) \lor ( z \rightarrow x )$ равны нулю. Из $( z \rightarrow x ) = 0$ сразу получаем $z = 1$ и $x = 0$. Тогда $\neg ( x \lor ( w \rightarrow y ) ) = 0$ означает $x \lor ( w \rightarrow y ) = 1$, а поскольку $x = 0$, необходимо $w \rightarrow y = 1$, что запрещает лишь пару $w = 1,\ y = 0$. Итого:

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

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

from itertools import product


def impl(a, b):
    return (not a) or b


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


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

Ответ: xwyz

Решение:

Итог собирается по таблице «Готовый товар», к строкам которой надо добавить сведения о ткани (по полю «ID ткани») и о модели (по полю «ID товара»).

Шаг 1. В таблице «Ткани» ставим фильтр: Цвет = «синий», Сырьё = «шёлк», Плотность $\le 200$ г/м². Подходят две ткани — крепдешин (196 г/м²) и муслин (140 г/м²). Обратите внимание: синий атлас и другие шёлковые ткани с плотностью 240 г/м² в отбор не попадают.

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

Шаг 3. В таблице «Готовый товар» функцией ВПР подтягиваем характеристики ткани и наименование модели, оставляем строки, удовлетворяющие обоим условиям. Их 9.

Шаг 4. Для каждой такой строки считаем произведение количества на складе и отпускной цены и суммируем результаты (формула СУММПРОИЗВ). Получается 429795 рублей.

Ответ: 429795

Решение:

Известно: О — 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$ нечётно, запись не меняется и $R=N$. Если чётно — в середину вставляется 1.

Ищем наименьшее $N$, при котором $R\ge 26$.

Числа $N\le 7$ записываются не более чем тремя разрядами, поэтому $R$ содержит не более трёх разрядов и $R\le 7$ — мало. Числа от 8 до 15 записываются четырьмя разрядами, вставка даёт пятиразрядную запись:

• $N=8=1000_2\to 10100_2=20$;
• $N=9=1001_2\to 10101_2=21$;
• $N=10=1010_2\to 10110_2=22$;
• $N=11=1011_2\to 10111_2=23$;
• $N=12=1100_2\to 11100_2=28\ge 26$ — подходит.

Все меньшие числа дают $R\lt 26$, поэтому искомое наименьшее $N$ равно 12.

def alg(n):
    b = bin(n)[2:]
    if len(b) % 2 == 0:
        b = b[:len(b) // 2] + '1' + b[len(b) // 2:]
    return int(b, 2)

print(min(n for n in range(1, 1000) if alg(n) >= 26))

Ответ: 12

Решение:

Первая команда «Повтори 2» чертит прямоугольник со сторонами 10 (вверх) и 18 (вправо): вершины $(0;0)$, $(0;10)$, $(18;10)$, $(18;0)$, периметр $2\cdot(18+10)=56$.

С поднятым хвостом Черепаха переходит на 5 вверх и на 7 вправо, в точку $(7;5)$, и снова смотрит вверх. Поэтому второй прямоугольник — это $(7;5)$, $(7;15)$, $(14;15)$, $(14;5)$: ширина 7, высота 10.

По горизонтали он целиком помещается внутри первого ($0\lt7$ и $14\lt18$), а вверх выходит за сторону $y=10$ на 5. Значит, объединение — большой прямоугольник с «башенкой» $7\times5$ сверху: из его периметра выпадает участок верхней стороны длиной 7, зато добавляются три стороны башенки $5+7+5=17$. Периметр объединения равен $56-7+17=66$.

print(2 * (18 + 10) - 7 + (5 + 7 + 5))   # 66

Ответ: 66

Решение:

Объём несжатой звукозаписи: $V = k \cdot f \cdot b \cdot t$, где $k = 4$ (квадро — четыре канала), $f = 96$ кГц $= 96000$ отсчётов в секунду, $b = 24$ бита на отсчёт, $t = 7$ с.

$V = 4 \cdot 96000 \cdot 24 \cdot 7 = 64512000$ бит.

Скорость модема уже дана в битах в секунду, переводить ничего не нужно: $\frac{64512000}{14400} = 4480$ с.

k, f, b, t = 4, 96000, 24, 7   # каналы, частота, разрешение, длительность
bits = k * f * b * t           # объём записи в битах
print(bits, bits // 14400)     # 64512000 4480

Ответ: 4480

Решение:

Буквы в алфавитном порядке: А, В, И, К, Л. Первое (то есть наименьшее) подходящее слово строим жадно — слева направо ставим самую маленькую букву, при которой оставшиеся условия ещё можно выполнить.

Условия: букв А не более двух, букв В ровно две, буквы И нет совсем.

• 1-я и 2-я буквы — А (это минимальная буква, а две А разрешены);
• 3-я и 4-я — В: букв А больше ставить нельзя, следующая по алфавиту буква В, и обе нужные В выгодно поставить как можно левее;
• 5-я и 6-я — К: А исчерпаны, В уже ровно две, И запрещена, значит минимальная доступная буква — К.

Получилось слово ААВВКК. Чтобы найти его номер, заменим буквы цифрами пятеричной системы (А=0, В=1, И=2, К=3, Л=4): ААВВКК → $001133_5$. Его значение $$1 \cdot 5^3 + 1 \cdot 5^2 + 3 \cdot 5 + 3 = 125 + 25 + 15 + 3 = 168.$$ Нумерация начинается с единицы (слову АААААА соответствует число 0), поэтому номер равен $168 + 1 = 169$.

from itertools import product

for n, w in enumerate(product('АВИКЛ', repeat=6), 1):
    s = ''.join(w)
    if s.count('А') <= 2 and s.count('В') == 2 and 'И' not in s:
        print(n, s)
        break

Ответ: 169

Решение:

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

Решение:

Считать нужно не по всему роману, а только по главе II, поэтому сначала выделим её текст: от заголовка «II» до заголовка «III» (в Word — поставить курсор в начало главы II и, удерживая Shift, щёлкнуть перед заголовком «III»).

Затем нажимаем Ctrl+F, вводим меня, включаем «Только слово целиком» (чтобы не посчитать «изменять», «уменьшать» и подобные слова, содержащие это буквосочетание) и не включаем «Учитывать регистр» — нужны и «меня», и «Меня». По кнопке «Найти все» поиск идёт по выделенному фрагменту и редактор показывает количество найденного.

В главе II слово встречается 12 раз.

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

import re

text = open('text.txt', encoding='utf-8').read()
start = text.index('\nII\n')
end = text.index('\nIII\n')
chapter = text[start:end]

matches = re.findall(r'(?<![А-Яа-яЁё])[Мм]еня(?![А-Яа-яЁё])', chapter)
print(len(matches))   # 12

Ответ: 12

Решение:

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

Один идентификатор из 310 символов занимает $310 \cdot 10 = 3100$ бит. Число байт должно быть целым и минимальным: $3100 = 8 \cdot 387 + 4$, поэтому под него отводится 388 байт.

Все 8960 идентификаторов занимают $8960 \cdot 388 = 3476480$ байт, то есть $3476480 : 1024 = 3395$ Кбайт.

import math

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

Ответ: 3395

Решение:

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

Приоритет у замены (2222, 11): она выполняется, пока в строке есть четыре подряд идущие двойки, и только если их нет — работает замена (1111, 22). Вначале двоек нет, поэтому четвёрки единиц превращаются в пары двоек, дальше замены чередуются, и результат проще получить моделированием.

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

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

Проверка на коротких строках: начиная с $k=8$ единиц результат периодичен с периодом 6, и при $k = 13,\ 19,\ 25,\ \ldots$ получается 22111. Здесь $91 = 13 + 6 \cdot 13$, что согласуется с ответом программы. Ответ: 22111

Решение:

В маске сначала идут $k$ единиц, потом $32-k$ нулей, поэтому нулей в ней $32-k$, и чтобы нулей было как можно больше, надо взять наименьшее допустимое $k$. Адрес сети получается из адреса узла обнулением всех битов правее $k$-го.

Двоичные записи:
адрес узла 185.128.219.219 — 10111001.10000000.11011011.11011011,
адрес сети 185.128.219.192 — 10111001.10000000.11011011.11000000.

Последняя единица адреса сети стоит на 26-й позиции (второй бит последнего байта: 192 = 11000000). Она обязана оказаться в сетевой части, иначе маска обнулила бы её, поэтому $k \ge 26$. С другой стороны, последние байты 11011011 и 11000000 совпадают только в первых трёх разрядах, значит различающийся бит должен попасть в узловую часть и $k \le 27$.

Наименьшее подходящее значение $k = 26$ (маска 255.255.255.192), и нулей в ней $32 - 26 = 6$.

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

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

ip = to_bits('185.128.219.219')
net = to_bits('185.128.219.192')
ok = [k for k in range(33) if ip[:k] + '0' * (32 - k) == net]
print(ok, max(32 - k for k in ok))

Ответ: 6

Решение:

Приведём всё к степеням тройки: $9^{111}=3^{222}$, $8 = 22_3$. Тогда

$$N = 3^{333} - 3^{222} + \left(3^{22} - 8\right).$$

$3^{333}-3^{222} = 3^{222}\left(3^{111}-1\right)$ — это 111 двоек в разрядах с 332-го по 222-й, ниже нули.

Далее $3^{22}-8 = \left(3^{22}-3^{2}\right)+1$. Разность $3^{22}-3^{2} = 3^{2}\left(3^{20}-1\right)$ даёт 20 двоек в разрядах с 21-го по 2-й, а прибавленная единица становится младшей цифрой. Получаем 20 двоек, затем 0, затем 1.

Итого запись: 111 двоек, 200 нулей, 20 двоек, 0, 1 (всего 333 цифры). Количество двоек: $111 + 20 = 131$.

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

n = 3**333 + 3**22 - 9**111 - 8
print(to_base(n, 3).count('2'))     # 131

Ответ: 131

Решение:

Формула $\neg \text{ДЕЛ}(x, A) \rightarrow (\text{ДЕЛ}(x, 6) \rightarrow \neg \text{ДЕЛ}(x, 9))$ обращается в 0 только тогда, когда посылка истинна, а следствие ложно, то есть когда $x$ не делится на $A$, но делится и на 6, и на 9.

Следовательно, тождественная истинность равносильна условию: любое число, кратное одновременно 6 и 9, делится на $A$.

Такие числа — это в точности кратные $\text{НОК}(6, 9)$. Так как $6 = 2 \cdot 3$ и $9 = 3^{2}$, получаем $\text{НОК}(6, 9) = 2 \cdot 3^{2} = 18$.

Подставив $x = 18$, видим, что $A$ обязано быть делителем 18. Наибольший делитель — 18, и он подходит: все кратные 18 делятся на 18.

best = 0
for A in range(1, 200):
    if all(x % A == 0 for x in range(18, 100000, 18)):
        best = A
print(best)   # 18

Ответ: 18

Решение:

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

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

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

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

Ответ: 41518080

Решение:

Считаем файл в список целых чисел и просмотрим все пары соседних элементов $(a_i,\ a_{i+1})$ — их на единицу меньше, чем самих чисел.

Последняя цифра числа — это остаток от деления его модуля на 10. Модуль здесь принципиален: в Python для отрицательных чисел остаток считается по-другому, например $-3119 \bmod 10 = 1$, хотя число оканчивается на 9.

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

a = [int(s) for s in open('44118_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)   # 1020 17197

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

Решение:

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

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

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

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

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

Горизонтальные стены (нельзя идти вниз) стоят между 4-й и 5-й строками в столбцах 16–19, между 11-й и 12-й строками в столбцах 10–12, между 16-й и 17-й строками в столбцах 2–4, между 18-й и 19-й строками в столбцах 13–17 и между 19-й и 20-й строками в столбцах 5–7.

Скопируем содержимое таблицы в текстовый файл 18.txt (числа разделены пробелами или знаками табуляции) и обработаем его программой.

f = open('18.txt')
a = [[int(x) for x in s.split()] for s in f]
N = len(a)

# стена снизу от клетки (i, j); строки и столбцы нумеруются с нуля
def wall_down(i, j):
    return ((i == 3 and 15 <= j <= 18) or (i == 10 and 9 <= j <= 11) or
            (i == 15 and 1 <= j <= 3) or (i == 17 and 12 <= j <= 16) or
            (i == 18 and 4 <= j <= 6))

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

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

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

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

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

Ответ: 2255 820

Решение:

Позицию обозначаем (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

Решение:

Напомним условия игры: перед игроками две кучи камней, за ход можно добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в одной из куч вдвое; игра заканчивается, когда произведение количеств камней в кучах становится не менее $144$. Начальная позиция — $(2,\ S)$, первым ходит Петя.

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

$S = 17$. Сразу Петя выиграть не может: лучший ход даёт произведение $4 \cdot 17 = 68 \lt 144$. Петя удваивает первую кучу — получается позиция $(4,\ 17)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(5,\ 17)$ — Петя удваивает вторую кучу: $5 \cdot 34 = 170$;
• $(4,\ 18)$ — Петя удваивает первую кучу: $8 \cdot 18 = 144$;
• $(8,\ 17)$ — Петя удваивает вторую кучу: $8 \cdot 34 = 272$;
• $(4,\ 34)$ — Петя удваивает первую кучу: $8 \cdot 34 = 272$.

$S = 23$. Сразу Петя выиграть не может: лучший ход даёт произведение $4 \cdot 23 = 92 \lt 144$. Петя добавляет камень в первую кучу — получается позиция $(3,\ 23)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(4,\ 23)$ — Петя удваивает вторую кучу: $4 \cdot 46 = 184$;
• $(3,\ 24)$ — Петя удваивает первую кучу: $6 \cdot 24 = 144$;
• $(6,\ 23)$ — Петя удваивает первую кучу: $12 \cdot 23 = 276$;
• $(3,\ 46)$ — Петя удваивает первую кучу: $6 \cdot 46 = 276$.

Полный перебор удобнее доверить программе:

N = 144

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

def over(p):                 # игра закончена
    return p[0] * p[1] >= N

def win1(p):                 # В1: выигрыш своим первым ходом
    return any(over(q) for q in moves(p))

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

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

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

Ответ: 17 23

Решение:

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

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

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

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

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

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

При $S = 112$ ходы Пети дают $113$ (В2), $224$ (В1) — условие выполнено. Меньших значений нет: при $S \lt 112$ ход «добавить камень» должен попасть в $\text{В1} \cup \text{В2} = \{57;\ 113\} \cup [115;\ 228]$, что оставляет только $S = 56$; но тогда второй ход даёт $2S = 112$ — позицию, которая не принадлежит ни В1, ни В2.

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

N = 229

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

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

Ответ: 112

Решение:

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

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

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

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

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

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

Решение:

Обозначим через $R(x)$ количество программ, переводящих число $x$ в заданное конечное число. Из $x$ исполнитель может перейти либо в $x+1$ (команда 1), либо в $2x$ (команда 2), поэтому $$R(x)=R(x+1)+R(2x),$$ причём $R(\text{конечного числа})=1$ (пустая программа), а если $x$ уже больше конечного числа, то $R(x)=0$ — числа только растут.

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

1) Из 1 в 10. Считаем $R$ от 10 вниз к 1 (удвоение из $x\ge 6$ сразу перескакивает через 10, поэтому там остаётся только «прибавить 1»):

Например, $R(5)=R(6)+R(10)=1+1=2$, $R(2)=R(3)+R(4)=4+3=7$, $R(1)=R(2)+R(2)=14$. Итого 14 программ.

2) Из 10 в 20. Для любого $x\ge 11$ удвоение даёт больше 20, значит $R(x)=R(x+1)=1$ для всех $x=11,\dots,20$. А из 10 можно и прибавлять единицы, и сразу удвоить: $R(10)=R(11)+R(20)=1+1=2$.

Итого $14\cdot 2=28$.

from functools import lru_cache

def count(start, finish):
    @lru_cache(None)
    def R(x):
        if x > finish:
            return 0
        if x == finish:
            return 1
        return R(x + 1) + R(2 * x)
    return R(start)

print(count(1, 10) * count(10, 20))

Ответ: 28

Решение:

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

Решение:

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

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

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

Первая строка прилагаемого файла содержит $S$ и $N$, далее идут $N$ объёмов посылок.

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)

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

629 50

Ответ: 629 50

Решение:

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

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

Файл A: сумма больших чисел равна $127341$ и делится на 3. Наименьшая ненулевая разность внутри пары, не кратная 3, равна $214$, поэтому ответ $127341 - 214 = 127127$.Файл B: сумма больших чисел равна $399762096$ и делится на 3. Наименьшая ненулевая разность внутри пары, не кратная 3, равна $16$, поэтому ответ $399762096 - 16 = 399762080$.Ответ: 127127 399762080