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

Решение:

Функция $F = \neg ( x \rightarrow y ) \lor ( x \equiv z ) \lor w$ зависит от четырёх переменных, поэтому её полная таблица истинности содержит $2^4 = 16$ строк, а расставить переменные w, x, y, z по четырём столбцам можно $4! = 24$ способами.

Найдём все наборы, на которых $F = 0$. Таких наборов всего три (значения записаны в «алфавитном» порядке $w,\ x,\ y,\ z$):

Значит, каждая строка фрагмента — это одна из этих трёх строк, только с переставленными столбцами. Но в каком порядке идут сами строки фрагмента, неизвестно, поэтому соответствие «столбец → переменная» надёжнее всего установить перебором всех 24 расстановок.

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

Всё это удобно поручить программе. В Python импликация $a \rightarrow b$ — это a <= b, а эквиваленция $a \equiv b$ — это a == b.

from itertools import product, permutations

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

# фрагмент таблицы: '.' — незаполненная клетка, второе число — значение F
frag = [('10.1', 0),
        ('..11', 0),
        ('..1.', 0)]

def fits(mask, vals):
    return all(m == '.' or int(m) == v for m, v in zip(mask, vals))

for p in permutations('wxyz'):
    # для каждой строки фрагмента — все её допустимые дополнения
    variants = []
    for mask, f in frag:
        variants.append([vals for vals in product((0, 1), repeat=4)
                         if fits(mask, vals) and F(**dict(zip(p, vals))) == f])
    # строки фрагмента должны быть попарно различны
    for lines in product(*variants):
        if len(set(lines)) == len(lines):
            print(''.join(p))
            break

Программа печатает единственную расстановку — xwzy. Проверим её вручную. Столбцы идут в порядке $x,\ w,\ z,\ y$; восстановим пустые клетки (восстановленные значения выделены курсивом):

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

Ответ: xwzy

Решение:

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

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

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

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

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

Ответ: 429795

Решение:

Известно: К — 00, Л — 01, М — 100, Н — 110. Кодовые слова нужны двум буквам — П и Р.

Ветвь 0 занята целиком (слова 00 и 01). В ветви 10 занято слово 100 — свободна вершина 101; в ветви 11 занято слово 110 — свободна вершина 111.

Свободных слов длины 1 и 2 нет: 0 является началом слова 00, 1 и 10 — началом слова 100, 11 — началом слова 110. Поэтому кратчайшая возможная длина равна 3.

Свободных вершин ровно две — 101 и 111, — и обе нужны: одна букве П, другая букве Р. Из них выбираем для П слово с наименьшим числовым значением.

Ответ: 101

Решение:

Пусть в двоичной записи $N$ ровно $k$ единиц и $p=k\bmod 2$. На шаге 2а справа приписывается $p$. После этого сумма цифр становится равной $k+p$ — она чётна при любом $k$, поэтому на шаге 2б приписывается 0.

Итак, к записи $N$ приписываются два разряда $p$ и 0, то есть $R=4N+2p$, где $p$ — чётность количества единиц в записи $N$.

Так как $p\le 1$, выполнено $R\le 4N+2$. Из $4N+2\gt 77$ получаем $N\ge 19$.

Проверяем $N=19=10011_2$: единиц три, $p=1$, запись $10011\to 100111\to 1001110$, то есть $R=1001110_2=78\gt 77$ — подходит.

(Для сравнения, $N=18=10010_2$ даёт $p=0$ и $R=72$.)

def alg(n):
    b = bin(n)[2:]
    b += str(sum(map(int, b)) % 2)
    b += str(sum(map(int, b)) % 2)
    return int(b, 2)

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

Ответ: 19

Решение:

Первая команда «Повтори 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

Решение:

В изображении $480 \cdot 270 = 129600$ пикселей, цвет каждого кодируется 4 байтами, то есть $4 \cdot 8 = 32$ битами.

Объём файла: $129600 \cdot 32 = 4147200$ бит.

Время передачи — это объём, делённый на скорость канала: $\frac{4147200}{14400} = 288$ с.

W, H = 480, 270
bits = W * H * 4 * 8        # объём изображения в битах
print(bits, bits // 14400)  # 4147200 288

Ответ: 288

Решение:

Пятизначное восьмеричное число имеет вид $d_1d_2d_3d_4d_5$, где старшая цифра $d_1 \in \{1,\dots,7\}$ (нулём число начинаться не может), а остальные цифры — любые из $\{0,\dots,7\}$.

Цифра 6 встречается ровно один раз, значит во всех остальных позициях шестёрки нет — там доступно по 7 цифр. Соседи шестёрки обязаны быть чётными; чётные восьмеричные цифры — это 0, 2, 4 и 6, но 6 запрещена условием, поэтому у соседа 3 варианта: 0, 2 или 4. Если соседом оказывается старший разряд, ноль тоже не подходит, и остаётся 2 варианта.

Разберём случаи по позиции шестёрки.

• 6 на 1-м месте: сосед $d_2 \in \{0,2,4\}$ — 3 варианта; $d_3, d_4, d_5$ — любые, кроме 6, по 7 вариантов. Итого $3 \cdot 7^3 = 1029$.
• 6 на 2-м месте: $d_1 \in \{2,4\}$ — 2 варианта; $d_3 \in \{0,2,4\}$ — 3; $d_4, d_5$ — по 7. Итого $2 \cdot 3 \cdot 7^2 = 294$.
• 6 на 3-м месте: $d_1$ — любая, кроме 0 и 6, то есть 6 вариантов; $d_2$ и $d_4$ — по 3; $d_5$ — 7. Итого $6 \cdot 3 \cdot 3 \cdot 7 = 378$.
• 6 на 4-м месте: $d_1$ — 6 вариантов; $d_2$ — 7; $d_3$ и $d_5$ — по 3. Итого $6 \cdot 7 \cdot 3 \cdot 3 = 378$.
• 6 на 5-м месте: $d_1$ — 6 вариантов; $d_2, d_3$ — по 7; $d_4 \in \{0,2,4\}$ — 3. Итого $6 \cdot 7 \cdot 7 \cdot 3 = 882$.

Складываем: $1029 + 294 + 378 + 378 + 882 = 2961$.

from itertools import product

count = 0
for d in product('01234567', repeat=5):
    if d[0] == '0' or d.count('6') != 1:
        continue
    i = d.index('6')
    ok = True
    for j in (i - 1, i + 1):
        if 0 <= j < 5 and int(d[j]) % 2 == 1:
            ok = False
    if ok:
        count += 1
print(count)   # 2961

Ответ: 2961

Решение:

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

Решение:

Откроем файл с текстом повести и воспользуемся поиском (Ctrl+F). Вводим шапка и включаем режим «Только слово целиком»: иначе будут посчитаны формы «шапках», «шапками», «шапкам» и т. п., которые по условию не учитываются. Флажок «Учитывать регистр» не ставим — годятся и «шапка», и «Шапка».

Редактор находит 4 вхождения именно словоформы «шапка»: «…и шапка в золоте…», «…и шапка заломлена набекрень…», «…у кого шапка…», «Разлетелась медная шапка…».

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

import re

text = open('text.txt', encoding='cp1251').read()
matches = re.findall(r'(?<![А-Яа-яЁё])[Шш]апка(?![А-Яа-яЁё])', text)
print(len(matches))   # 4

Ответ: 4

Решение:

В пароле встречаются только 26 строчных латинских букв и 20 знаков («=», «+» и др.), значит мощность алфавита составляет $26 + 20 = 46$ символов. На один символ нужно минимальное целое $i$, при котором $2^i \ge 46$. Так как $2^{5} = 32 \lt 46 \lt 64 = 2^{6}$, получаем $i = 6$ бит.

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

Кроме пароля на один пользователя отводится ещё 11 байт дополнительных сведений, поэтому одна запись занимает $8 + 11 = 19$ байт.

Для 40 пользователей потребуется $40 \cdot 19 = 760$ байт.

import math

N = 26 + 20                   # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(10 * i / 8)     # байт на пароль
print(40 * (b + 11))          # ответ в байтах

Ответ: 760

Решение:

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

Замена (12, 221) переставляет единицу на одну позицию вправо (за стоящую справа двойку) и добавляет ещё одну двойку. Справа от единицы вначале 70 двоек, поэтому эта замена выполнится ровно 70 раз: единица окажется в конце строки, а двоек станет $70 + 70 = 140$.

После этого цепочка 12 не находится, но единица есть, поэтому выполняется замена (1, 2): двоек становится 141, и программа останавливается.

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

s = "1" + "2" * 70
while "12" in s or "1" in s:
    if "12" in s:
        s = zamenit(s, "12", "221")
    elif "1" in s:
        s = zamenit(s, "1", "2")
print(s.count("2"))   # 141

Ответ: 141

Решение:

В маске 255.255.255.252 стоит $8+8+8+6=30$ единиц, значит свободны только 2 младших бита, а сеть состоит из четырёх адресов. Двоичная запись адреса сети: 10001001 10001111 01111110 01100100; её фиксированные 30 битов 100010011000111101111110011001 содержат 17 единиц.

Эти 17 единиц присутствуют в каждом адресе сети, а два свободных бита можно обнулить — так получается адрес 137.143.126.100 с наименьшей суммой единиц. Значит, минимум равен 17.

net = 137 * 256**3 + 143 * 256**2 + 126 * 256 + 100
host = 32 - 30
print(min(bin(net + k)[2:].zfill(32).count('1')
          for k in range(2 ** host)))   # 17

Ответ: 17

Решение:

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

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

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

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

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

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

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

Ответ: 1196

Решение:

Дизъюнкция ложна только тогда, когда ложны оба слагаемых. Значит формула нарушается ровно при тех $x$, для которых одновременно

• $\text{ДЕЛ}(x, 13)$ истинно и $\text{ДЕЛ}(x, 21)$ истинно (тогда импликация $\text{ДЕЛ}(x,13) \rightarrow \neg\text{ДЕЛ}(x,21)$ ложна);
• $x + A \lt 500$.

Числа, делящиеся и на 13, и на 21, — это кратные $\text{НОК}(13, 21) = 273$ (числа взаимно просты).

Чтобы формула была тождественно истинна, для каждого кратного 273 должно выполняться $x + A \geq 500$. Достаточно проверить наименьшее из них, $x = 273$: для больших кратных неравенство только усиливается.

Получаем $273 + A \geq 500$, то есть $A \geq 227$. Наименьшее натуральное значение — $A = 227$.

Ответ: 227

Решение:

Правило $F(n) = n \cdot F(n-1)$ при $F(1) = 1$ задаёт факториал: $F(n) = n!$. Но раскрывать факториалы не нужно — достаточно трижды применить рекуррентное правило к числителю:

$$F(446) = 446 \cdot F(445) = 446 \cdot 445 \cdot F(444) = 446 \cdot 445 \cdot 444 \cdot F(443).$$

Поэтому $\dfrac{F(446)}{F(443)} = 446 \cdot 445 \cdot 444 = 198470 \cdot 444 = 88120680$.

print(446 * 445 * 444)   # 88120680

Ответ: 88120680

Решение:

Читаем файл в список и перебираем пары соседних элементов $(a_i,\ a_{i+1})$.

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

Пара подходит, если у обоих чисел последние цифры совпадают и нечётны. Среди таких пар ищем максимальное произведение модулей.

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

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

print(count, best)   # 227 96784219

Получаем 227 пар, наибольшее произведение модулей — 96784219.Ответ: 227 96784219

Решение:

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

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

В приложенном файле поле имеет размер $20\times20$; стены обозначены утолщёнными линиями. Внутренних стен две:

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

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

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

# стена снизу от клетки (i, j); строки и столбцы нумеруются с нуля
def wall_down(i, j):
    return i == 16 and 11 <= j <= 16

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

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

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

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

Решение:

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

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

Из начальной позиции $(2,S)$ Петя может получить позиции $(4,S)$ (и прибавление 2, и удвоение первой кучи дают одно и то же), $(2,S+2)$ и $(2,2S)$. Самая опасная — $(2,2S)$: Ваня удваивает вторую кучу ещё раз и получает сумму $2+4S$. Условие $2+4S\ge142$ даёт $4S\ge140$, то есть $S\ge35$.

Другие ходы требуют большего $S$: из $(2,S+2)$ сумма после хода Вани равна $2S+6\ge142$, откуда $S\ge68$; из $(4,S)$ — $4+2S\ge142$, $S\ge69$.

Проверим $S=35$. Петя ходит $(2,35)\to(2,70)$: сумма 72, игра продолжается. Ваня удваивает: $(2,140)$, сумма $142\ge142$ — победа первым ходом. Сам Петя выиграть сразу не мог: $2+35+35=72\lt142$. При $S\lt35$ такая ситуация невозможна.

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 >= 142 for x, y in moves(p))

for S in range(1, 139):
    if any(x + y < 142 and win1((x, y)) for x, y in moves((2, S))):
        print(S)
        break

Ответ: 35

Решение:

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

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

$S = 31$. Сразу Петя выиграть не может ($7 + 2\cdot 31 = 69 \lt 77$). Петя удваивает первую кучу — получается позиция $(14,\ 31)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(15,\ 31)$ — Петя удваивает вторую кучу: $15 + 62 = 77$;
• $(14,\ 32)$ — Петя удваивает вторую кучу: $14 + 64 = 78$;
• $(28,\ 31)$ — Петя удваивает вторую кучу: $28 + 62 = 90$;
• $(14,\ 62)$ — Петя добавляет камень: $14 + 63 = 77$.

$S = 34$. Сразу Петя выиграть не может ($7 + 2\cdot 34 = 75 \lt 77$). Петя добавляет камень в первую кучу — получается позиция $(8,\ 34)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(9,\ 34)$ — Петя удваивает вторую кучу: $9 + 68 = 77$;
• $(8,\ 35)$ — Петя удваивает вторую кучу: $8 + 70 = 78$;
• $(16,\ 34)$ — Петя удваивает вторую кучу: $16 + 68 = 84$;
• $(8,\ 68)$ — Петя добавляет камень: $8 + 69 = 77$.

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

N = 77

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, 70) if win2((7, s))][:2])   # два наименьших

Ответ: 31 34

Решение:

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

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

В1. Из позиции $(3,\ S)$ игру заканчивают ход «добавить два камня» ($S+5 \ge 122$) и удвоение большей кучи ($2S+3 \ge 122$). Второе условие слабее, поэтому В1 — это все $S \ge 60$.

П1 для начальной позиции — единственное значение $S = 59$; В2 — значения $S = 57$, $S = 58$.

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

При $S = 55$ четыре хода Пети дают позиции $(3,\ 57)$ (В2), $(5,\ 55)$ (В2), $(6,\ 55)$ (В2), $(3,\ 110)$ (В1). Все они для Вани выигрышны не позже второго хода, но три из них — только вторым ходом, поэтому гарантированно выиграть первым ходом Ваня не может. Полный перебор подтверждает, что меньших значений $S$ с таким свойством нет.

Перебор всех $S$ удобно сделать программой:

N = 122

def moves(p):
    a, b = p
    return [(a + 2, b), (a, b + 2), (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))

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

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

Ответ: 55

Решение:

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

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

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

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

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

Ответ: 2

Решение:

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

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

Решение:

Запрещена только одна конфигурация — две буквы P подряд, то есть подстрока PP. Все остальные сочетания символов допустимы, поэтому серия обрывается ровно в тех местах, где встречается PP.

Идём по файлу и храним длину текущей допустимой серии cur. Если текущий и предыдущий символы оба равны P, старая серия закончилась, и новая начинается с текущего символа: cur = 1. Иначе cur += 1. Ответ — максимум cur.

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

mx = cur = 1
for i in range(1, len(s)):
    if s[i] == 'P' and s[i - 1] == 'P':
        cur = 1
    else:
        cur += 1
    if cur > mx:
        mx = cur

print(mx)

Важно, что при обрыве новая серия начинается именно со второй буквы P: она сама по себе запрещённой пары не образует и может стать началом следующего участка. Программа выводит 188. Ответ: 188

Решение:

Перебирать подряд все числа до $10^8$ не нужно: искомое число обязано делиться на 5171, поэтому переберём сразу кратные $n=5171k$ — их всего $\lfloor 10^8/5171\rfloor=19338$, это мгновенно.

Проверку маски удобно поручить модулю fnmatch: в его шаблонах ? означает ровно один символ, а * — любую, в том числе пустую, последовательность символов, то есть ровно то, что написано в условии. Число превращаем в строку и сравниваем с маской ?19*8?3.

from fnmatch import fnmatch

for k in range(1, 10 ** 8 // 5171 + 1):
    n = 5171 * k
    if fnmatch(str(n), '?19*8?3'):
        print(n, k)

Маска ?19*8?3: одна любая цифра, затем 19, затем произвольный (возможно, пустой) кусок, затем 8, любая цифра и 3 в конце. Программа находит 4 числа.

Ответ: 11908813 2303 71995833 13923 81975863 15853 91955893 17783

Решение:

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

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

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

В прилагаемом файле $S = 99\,992$, $N = 9994$.

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)

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

3098 80

Ответ: 3098 80

Решение:

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