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

Решение:

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

Все слагаемые дизъюнкции $\neg ( w \rightarrow x ) \lor ( y \equiv z ) \lor z$ должны обратиться в ноль. Сразу $z = 0$, тогда из $(y \equiv z) = 0$ следует $y = 1$. Наконец, $\neg ( w \rightarrow x ) = 0$ означает $w \rightarrow x = 1$, то есть запрещена пара $w = 1,\ x = 0$. Наборов три:

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

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

from itertools import product


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


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


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

Ответ: zxyw

Решение:

Нужно найти две суммы по таблице «Аренда» и взять модуль их разности. Для этого к строкам «Аренды» добавляем марку автомобиля (связь по полю «ID автомобиля») и фамилию клиента (связь по полю «ID клиента»).

Шаг 1. В таблице «Клиенты» находим ID Сачкова Х. Э. и ID Гудкова Н. Г.

Шаг 2. В таблице «Автомобили» отбираем машины марки Hyundai и выписываем их ID автомобиля.

Шаг 3. В таблице «Аренда» оставляем строки с этими автомобилями и датой аренды с 1 января по 30 июня включительно, а затем отдельно суммируем «Сумму аренды, руб.» по каждому из двух клиентов (формула СУММЕСЛИМН).

Шаг 4. У Сачкова Х. Э. одна поездка на 276 рублей. У Гудкова Н. Г. семь поездок: 178, 204, 205, 336, 183, 345 и 418 рублей, в сумме $178 + 204 + 205 + 336 + 183 + 345 + 418 = 1869$ рублей. Модуль разности: $|276 - 1869| = 1593$.

Ответ: 1593

Решение:

Известно: Л — 1, Я — 01.

Кодовое слово Л — 1 занимает целиком всю ветвь, начинающуюся с 1: никакое другое кодовое слово не может начинаться с единицы. Значит, все остальные буквы кодируются словами, начинающимися с 0. В этой ветви слово 01 занято буквой Я, поэтому свободна только вершина 00.

Четыре оставшиеся буквы А, К, Н и О должны получить кодовые слова, начинающиеся с 00. Чтобы из одной вершины получить четыре разных слова, нужно добавить ещё не менее двух разрядов: 0000, 0001, 0010, 0011 — все длины 4.

В слове КОЛОННА буква О встречается 2 раза, Н — 2 раза, К — 1 раз, А — 1 раз, Л — 1 раз (буква Я не встречается вовсе).

Суммарно $1 + 8 + 8 + 4 + 4 = 25$ двоичных знаков. Неравномерное разбиение той же вершины (например, О — 000, Н — 0010, К — 00110, А — 00111) даёт ровно столько же, меньше 25 получить нельзя.

Ответ: 25

Решение:

Пусть в двоичной записи $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 Направо 90 Вперёд 10 Направо 90] рисует квадрат $10\times 10$ и возвращает Черепаху в исходную точку с исходным направлением.

Затем с поднятым хвостом Вперёд 5 Направо 90 Вперёд 5 Налево 90 сдвигает её на $(+5;+5)$, причём голова снова направлена вдоль оси $Oy$.

Значит рисуются три квадрата со стороной 10 с левыми нижними углами $(0;0)$, $(5;5)$ и $(10;10)$.

Соседние квадраты перекрываются по квадрату $5\times 5$. У каждого из двух соседей внутрь объединения уходят два отрезка границы длиной 5, то есть пара соседей «съедает» $2\cdot(5+5)=20$. Первый и третий квадраты касаются лишь в точке $(10;10)$ и длину не отнимают.

Итого $3\cdot 40-20-20=80$.

Тот же ответ даёт прямой обход границы объединения: $(0;0)$, $(10;0)$, $(10;5)$, $(15;5)$, $(15;10)$, $(20;10)$, $(20;20)$, $(10;20)$, $(10;15)$, $(5;15)$, $(5;10)$, $(0;10)$ и назад в $(0;0)$; сумма длин звеньев $10+5+5+5+5+10+10+5+5+5+5+10=80$.

Ответ: 80

Решение:

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

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

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

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

size = 56          # Мбайт, первая запись
k = 2 * 4.5 * 1/3  # во сколько раз изменился объём
print(size * k)    # 168.0

Ответ: 168

Решение:

Сначала выпишем используемые буквы в алфавитном порядке: Е, Л, М, Р, У. Список слов упорядочен по алфавиту, значит сперва идут все слова, начинающиеся на Е, затем все слова на Л, потом на М и т. д.

Слов, начинающихся с буквы Е, ровно $5^3 = 125$: три оставшиеся позиции заполняются независимо друг от друга любой из пяти букв. Эти слова занимают номера с 1 по 125.

Следовательно, первое слово, начинающееся с буквы Л (это слово ЛЕЕЕ), стоит под номером $125 + 1 = 126$.

from itertools import product

words = sorted(''.join(w) for w in product('ЛЕМУР', repeat=4))
for i, w in enumerate(words, 1):
    if w[0] == 'Л':
        print(i, w)   # 126 ЛЕЕЕ
        break

Ответ: 126

Решение:

В каждой строке таблицы семь чисел. Первое условие означает, что набор кратностей значений в строке равен $2+2+1+1+1$: ровно два значения встречаются по два раза, а оставшиеся три числа попарно различны, то есть всего в строке ровно пять различных значений.

«Повторяющиеся числа» — это те четыре ячейки, которые образуют пары. Если пары составлены из чисел $a$ и $b$, то их среднее равно $\frac{a+a+b+b}{4}=\frac{a+b}{2}$, и его нужно сравнить со средним всех семи чисел строки.

Удобнее всего открыть csv-версию файла программой: для каждой строки построить счётчик значений, проверить кратности и сравнить два средних.

from collections import Counter

count = 0
for line in open('9.csv', encoding='utf-8'):
    row = [int(x) for x in line.split(';')]
    c = Counter(row)
    pairs = [v for v in c if c[v] == 2]
    if len(pairs) == 2 and len(c) == 5:
        rep = [x for x in row if c[x] == 2]
        if sum(rep) / len(rep) < sum(row) / len(row):
            count += 1

print(count)

Условие len(pairs) == 2 and len(c) == 5 как раз и означает «две пары плюс три различных числа». Программа просматривает все 16 000 строк и находит 83 подходящие.Ответ: 83

Решение:

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

Редактор находит два вхождения: «Сей умилённый взор…» и «…и гневен был взор его».

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

import re

text = open('text.txt', encoding='cp1251').read()
matches = re.findall(r'(?<![А-Яа-яЁё])[Вв]зор(?![А-Яа-яЁё])', text)
print(len(matches))   # 2

Ответ: 2

Решение:

Идентификатор набирается из 8-символьного набора А, В, C, D, Е, F, G, H, значит мощность алфавита составляет $8$ символов. Алфавит содержит ровно $2^{3} = 8$ символов, поэтому на один символ достаточно $i = 3$ бита.

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

Кроме идентификатора на один объект отводится ещё 24 байта дополнительных сведений, поэтому одна запись занимает $6 + 24 = 30$ байт.

Для 20 объектов потребуется $20 \cdot 30 = 600$ байт.

import math

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

Ответ: 600

Решение:

На вход подаётся строка вида «5», за которой идут $n$ двоек. Команды применяются строго в указанном порядке, каждая — к первому слева вхождению, и всё тело цикла повторяется, пока в строке есть хотя бы одна из цепочек 52, 2222, 1122. Правило $2222 \to 5$ «сворачивает» четвёрки двоек, а правила $52 \to 11$ и $1122 \to 25$ перемешивают результат, поэтому проследить процесс вручную тяжело — надёжнее в точности повторить его программой и перебрать $n$.

Полезное наблюдение: сумма цифр результата растёт с ростом $n$ — на каждые пять дополнительных двоек она увеличивается примерно на 2. Поэтому перебирать все значения до 10 000 не нужно: все подходящие $n$ заведомо меньше 200.

def run(s):
    while '52' in s or '2222' in s or '1122' in s:
        if '52' in s:
            s = s.replace('52', '11', 1)
        if '2222' in s:
            s = s.replace('2222', '5', 1)
        if '1122' in s:
            s = s.replace('1122', '25', 1)
    return s

for n in range(4, 1000):
    s = run('5' + '2' * n)
    if sum(int(c) for c in s) == 64:
        print(n)

Программа выводит 152, 154 и 156; при больших $n$ сумма цифр уже превышает 64 и к этому значению не возвращается. При $n = 156$ от исходной строки остаются ровно 64 единицы, сумма цифр которых и равна 64. Наибольшее подходящее значение — $n = 156$.Ответ: 156

Решение:

Маска 255.255.255.248 в двоичном виде — 11111111.11111111.11111111.11111000, в ней 29 единиц. Значит, старшие 29 битов у всех адресов сети одинаковы, а на адрес узла остаётся 3 бита, то есть в сети $2^3 = 8$ адресов. Адрес сети: 232 & 248 = 11101000 & 11111000 = 11101000, поэтому это адреса от 123.19.251.232 до 123.19.251.239.

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

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

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

from itertools import product

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

ip = to_bits('123.19.251.232')
mask = to_bits('255.255.255.248')
k = mask.count('1')
head = ip[:k]
addrs = [head + ''.join(t) for t in product('01', repeat=32 - k)]
print(sum(1 for a in addrs if '111' in a))

Ответ: 8

Решение:

Приведём выражение $49^7 + 7^{21} - 7$ к степеням семёрки: $49^7 = \left(7^2\right)^7 = 7^{14}$, поэтому $N = 7^{21} + 7^{14} - 7$.

Разберёмся с разностью: $7^{14} - 7 = 7\left(7^{13} - 1\right)$. Число $7^{13} - 1$ в семеричной системе — это 13 шестёрок, а умножение на 7 приписывает справа один ноль. Значит $7^{14} - 7$ записывается как 13 шестёрок и ноль.

Слагаемое $7^{21}$ ставит единицу в 21-м разряде и не задевает младшие разряды. Итоговая запись выглядит так:

$1\underbrace{0\ldots0}_{7}\underbrace{6\ldots6}_{13}0$

Шестёрок ровно 13.

n = 49**7 + 7**21 - 7
s = ''
while n:
    s = str(n % 7) + s
    n //= 7
print(s, s.count('6'))

Ответ: 13

Решение:

Дизъюнкция $(\text{ДЕЛ}(x, 2) \rightarrow \neg \text{ДЕЛ}(x, 3)) \lor (x + A \ge 100)$ ложна только тогда, когда ложны оба слагаемых.

Первая скобка — импликация; она ложна ровно тогда, когда $x$ делится на 2 и при этом не выполняется $\neg \text{ДЕЛ}(x, 3)$, то есть когда $x$ делится и на 2, и на 3 — иначе говоря, когда $x$ кратно 6.

Значит вторая скобка $x + A \ge 100$ обязана быть истинной для всех $x$, кратных 6 (при остальных $x$ формула истинна и без неё).

Условие $x + A \ge 100$ тем жёстче, чем меньше $x$. Наименьшее натуральное кратное шести — это $x = 6$, откуда $6 + A \ge 100$, то есть $A \ge 94$.

При $A = 94$ для любого кратного 6 числа $x \ge 6$ выполнено $x + 94 \ge 100$, значит наименьшее подходящее значение равно 94.

for A in range(1, 200):
    if all((x % 2 != 0 or x % 3 != 0) or x + A >= 100
           for x in range(1, 10000)):
        print(A)   # 94
        break

Ответ: 94

Решение:

Вычислять $F(2024)$ целиком не нужно — выражение сворачивается, потому что рекуррентное соотношение связывает три подряд идущих значения.

Запишем правило при $n = 2021$: $F(2021) = 2021 \cdot 2020 + F(2020) - F(2019)$, откуда $F(2020) - F(2019) = F(2021) - 2021 \cdot 2020$. Значит искомое выражение равно $F(2024) + F(2021) - 2021 \cdot 2020$.

Теперь раскроем $F(2024)$. При $n = 2024$: $F(2024) = 2024 \cdot 2023 + F(2023) - F(2022)$, а при $n = 2023$: $F(2023) = 2023 \cdot 2022 + F(2022) - F(2021)$, то есть $F(2023) - F(2022) = 2023 \cdot 2022 - F(2021)$. Поэтому $F(2024) = 2024 \cdot 2023 + 2023 \cdot 2022 - F(2021)$.

Слагаемые с $F(2021)$ взаимно уничтожаются:

$$F(2024) + F(2020) - F(2019) = 2024 \cdot 2023 + 2023 \cdot 2022 - 2021 \cdot 2020 = 4094552 + 4090506 - 4082420 = 4102638.$$

Тот же ответ даёт программа. Рекурсию «в лоб» здесь применять нельзя (каждый вызов порождает два новых, время растёт экспоненциально) — заполняем таблицу значений по возрастанию $n$:

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

print(F[2024] + F[2020] - F[2019])   # 4102638

Ответ: 4102638

Решение:

Читаем файл в список и перебираем пары соседних элементов $(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}$.

В приложенном файле поле имеет размер $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])

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

Решение:

Позиция игры описывается одним числом $s$ — количеством камней в куче. Игрок, который ходит из позиции $s$, выигрывает своим ходом, если хотя бы один его ход сразу даёт кучу в 161 камней или больше.

Ходы: $s\to s+1$ и $s\to 2s$. Одним ходом игра заканчивается, если $s+1\ge161$ ($s\ge160$) или $2s\ge161$ ($s\ge80{,}5$, для целого $s$ — $s\ge81$). Итак, выигрывает одним ходом тот, кто ходит из позиции $s\ge81$.

Требуется $S\le80$ (Петя не выигрывает сразу) и одновременно $S+1\ge81$, $2S\ge81$, то есть $S\ge80$ и $S\ge41$. Остаётся $S=80$.

Проверка: из 80 Петя получает 81 или 160. Из 81 Ваня удваивает: $162\ge161$; из 160 добавляет камень: $161\ge161$. Сам Петя выиграть не мог: $81\lt161$ и $160\lt161$.

def win1(s):
    return s + 1 >= 161 or 2 * s >= 161

for S in range(1, 161):
    if not win1(S) and win1(S + 1) and win1(2 * S):
        print(S)

Ответ: 80

Решение:

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

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

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

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

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

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

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

N = 29

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

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

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

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

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

Ответ: 7 13

Решение:

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

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

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

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

def over(s):
    return s >= N

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

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

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

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

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

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

• $13$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $14$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $15$ — в $30$; из $28$ — в $29$);
• $24$ — Ваня выигрывает сразу: одним ходом он получает $48$, а это уже не меньше 29.

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

Ответ: 12

Решение:

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

Решение:

Обе команды только уменьшают число на экране, поэтому траектория строго убывает и одно и то же число не может встретиться в ней дважды. Значит, каждая подходящая программа однозначно разбивается на две независимые части: сначала число $60$ превращается в $20$, затем $20$ превращается в $1$. По правилу умножения искомое количество равно произведению количеств программ для этих двух участков.

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$. Если $x = y$, подходит только пустая программа, то есть $f(x, x) = 1$; если $x \lt y$, то $f(x, y) = 0$ — увеличивать число команды не умеют. Иначе первая команда переводит $x$ либо в $x - 1$, либо в $\left\lfloor x/2 \right\rfloor$, поэтому

$$f(x, y) = f(x - 1,\, y) + f\big(\left\lfloor x/2 \right\rfloor,\, y\big).$$

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

from functools import lru_cache

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

print(f(60, 20) * f(20, 1))

Получаем $f(60, 20) = 22$ и $f(20, 1) = 80$, то есть всего $22 \cdot 80 = 1760$ программ. Ответ: 1760

Решение:

Запрещена только одна конфигурация — две буквы 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

Решение:

У целого числа $n$ наименьший делитель, отличный от единицы, — это его наименьший простой делитель $p$. Ему в пару идёт наибольший делитель, отличный от самого числа, равный $n/p$. Значит, оба «крайних» делителя находятся за один проход: достаточно перебрать $d$ от 2 до $\sqrt{n}$ и остановиться на первом, который делит $n$. Если такого $d$ нет, число простое, промежуточных делителей у него нет.

Нужны числа, у которых $F = n/p - p$ не равно нулю и делится на 7. Условие $F \ne 0$ отсекает простые числа (у них промежуточных делителей нет) и заодно числа вида $n = p^2$, для которых $F = 0$. Перебираем числа, начиная с 850001, по возрастанию, пока не наберём шесть подходящих.

def M(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d - d      # наибольший делитель минус наименьший
        d += 1
    return 0                       # n простое: делителей нет

n = 850000
found = 0
while found < 6:
    n += 1
    f = M(n)
    if f != 0 and f % 7 == 0:
        print(n, f)
        found += 1

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

850003 121422
850005 283332
850014 425005
850028 425012
850042 425019
850047 283346

Ответ: 850003 121422 850005 283332 850014 425005 850028 425012 850042 425019 850047 283346

Решение:

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

Шаг 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

Решение:

Из пункта с $t$ пробирками уезжает $w=\lceil t/36 \rceil$ контейнеров: контейнер вмещает не более 36 пробирок и вскрывается только в лаборатории, поэтому «недогруженный» контейнер всё равно нужен. В Python это удобно записать как -(-t // 36).

Если лабораторию открыть в пункте с номером $x_j$, то стоимость доставки равна $$C(j)=\sum_{i} w_i\,|x_i-x_j|.$$ Перебирать все пункты и для каждого считать сумму — это $O(N^2)$, для файла B слишком долго. Раскроем модуль: пункты слева от $j$ дают $x_j\sum_{i\lt j} w_i-\sum_{i\lt j} w_i x_i$, пункты справа дают $\sum_{i\gt j} w_i x_i-x_j\sum_{i\gt j} w_i$. Пункты в файле уже перечислены в порядке возрастания номера, поэтому, идя по ним слева направо и поддерживая четыре величины — $\sum w_i$ и $\sum w_i x_i$ слева и справа, — мы вычисляем $C(j)$ за $O(1)$ для каждого пункта, а весь ответ — за $O(N)$.

def solve(name, cap=36):
    f = open(name)
    n = int(f.readline())
    x = [0] * n          # номера пунктов (они же расстояния от нулевой отметки)
    w = [0] * n          # число контейнеров в пункте
    for i in range(n):
        a, b = map(int, f.readline().split())
        x[i] = a
        w[i] = -(-b // cap)          # округление вверх: ceil(b / cap)
    wt = sum(w)
    xwt = sum(w[i] * x[i] for i in range(n))
    wl = 0               # сумма весов слева от текущего пункта
    xwl = 0              # сумма w*x слева от текущего пункта
    best = None
    for i in range(n):
        wr = wt - wl - w[i]
        xwr = xwt - xwl - w[i] * x[i]
        cost = x[i] * wl - xwl + xwr - x[i] * wr
        if best is None or cost < best:
            best = cost
        wl += w[i]
        xwl += w[i] * x[i]
    return best

print(solve('A.txt'), solve('B.txt'))

Проверка на примере из условия (вместимость 96): числа контейнеров равны $2,3,1,1,1,2$, минимум достигается в пункте 2 и равен $2+0+3+5+6+16=32$ — совпадает с пояснением к заданию.Для файла A минимум равен $51\,063$ (лаборатория в пункте $563$), для файла B — $5\,634\,689\,219\,329$.Ответ: 51063 5634689219329