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

Решение:

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

Здесь функция равна единице, значит истинны оба сомножителя выражения $\neg ( y \rightarrow ( z \equiv w ) ) \land ( x \rightarrow z )$. Из $\neg ( y \rightarrow ( z \equiv w ) ) = 1$ следует, что импликация ложна, то есть $y = 1$ и $z \ne w$. Условие $x \rightarrow z = 1$ запрещает пару $x = 1,\ z = 0$. При $z = 1,\ w = 0$ переменная $x$ любая, при $z = 0,\ w = 1$ обязательно $x = 0$. Наборы:

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

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

from itertools import product


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


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


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

Ответ: wzyx

Решение:

Спрашивается масса полученного товара, поэтому нужны только операции с типом «Поступление», а количество упаковок надо перевести в массу через поле «Количество в упаковке» таблицы «Товар».

Шаг 1. В таблице «Магазин» отбираем магазины, у которых в адресе указан проспект Мира. Таких магазинов два — обратите внимание, что они находятся в разных домах, но район в условии не важен.

Шаг 2. В таблице «Товар» находим все виды зефира: зефир в шоколаде (250 г в упаковке), зефир ванильный (800 г), зефир воздушный (500 г) и зефир лимонный (1000 г). Выписываем их артикулы.

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

Шаг 4. Переводим в граммы и складываем: $1000 \cdot 250 + 1000 \cdot 800 + 1000 \cdot 500 + 1200 \cdot 1000 = 2750000$ г. Переводим в килограммы: $2750000 : 1000 = 2750$ кг.

Ответ: 2750

Решение:

Условие Фано нарушается, если новое кодовое слово оказывается началом какого-нибудь из уже используемых слов или, наоборот, одно из используемых слов является началом нового. Именно такое слово нам и нужно подобрать.

Заняты слова: А — 00, Б — 01, В — 100, Г — 110.

Слова из одного символа брать нельзя: по условию в записи слова для буквы Д должно использоваться более одного символа. Переходим к словам длины 2. Слова 00 и 01 уже используются, значит остаются 10 и 11:

• 10 является началом слова 100 (буква В) — условие Фано нарушается;
• 11 является началом слова 110 (буква Г) — условие Фано нарушается.

Подходят оба слова, поэтому берём то, у которого меньше числовое значение: $10 \lt 11$.

Ответ: 10

Решение:

Обозначим $M=N-(N\bmod 4)$ — результат первого шага. Это ближайшее снизу число, кратное 4, и при переборе всех $N$ величина $M$ пробегает в точности все кратные четырём числа.

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

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

Нужно наименьшее $R\gt 100$. Так как $p\le 1$, из $4M+2p\gt 100$ следует $4M\ge 99$, то есть $M\ge 25$; а $M$ кратно 4, поэтому $M\ge 28$. Величина $R=4M+2p$ растёт вместе с $M$, значит достаточно взять наименьшее допустимое $M=28$.

$M=28=11100_2$, единиц три, $p=1$: запись $11100$ превращается в $111001$, затем в $1110010$, то есть $R=1110010_2=114$.

Для сравнения, предыдущее кратное четырём $M=24=11000_2$ даёт $p=0$ и $R=96$ — это не больше 100.

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

print(min(r for r in {alg(n) for n in range(1, 1000)} if r > 100))

Ответ: 114

Решение:

После команды Направо 60 голова Черепахи повёрнута на $30^\circ$ к оси абсцисс, а дальше каждый шаг — отрезок длины 9 и поворот ровно на $60^\circ$ в одну и ту же сторону. Шесть таких шагов дают полный оборот $6\cdot 60^\circ=360^\circ$ и замыкают правильный шестиугольник со стороной 9; седьмой шаг просто повторяет первую сторону и новой линии не добавляет.

Вершины шестиугольника: $(0;0)$, $\left(\tfrac{9\sqrt3}{2};\,4{,}5\right)$, $(9\sqrt3;\,0)$, $(9\sqrt3;\,-9)$, $\left(\tfrac{9\sqrt3}{2};\,-13{,}5\right)$, $(0;\,-9)$. Его площадь равна $\tfrac{3\sqrt3}{2}\cdot 9^2\approx 210{,}4$, значит искомое число близко к 210. На границе лежат ровно 10 целых точек — весь левый вертикальный отрезок от $(0;-9)$ до $(0;0)$; по условию их учитывать не следует.

Точный подсчёт удобно доверить программе: воспроизводим ход Черепахи, берём первые шесть полученных вершин и для каждого узла решётки проверяем, что все векторные произведения сторон на векторы к этому узлу одного знака — это и означает «строго внутри выпуклого многоугольника».

from math import cos, sin, radians

x = y = 0.0
h = 90.0                 # голова смотрит вверх
P = [(0.0, 0.0)]

def R(a):                # Направо a
    global h
    h -= a

def F(n):                # Вперёд n
    global x, y
    x += n * cos(radians(h))
    y += n * sin(radians(h))
    P.append((x, y))

R(60)
for _ in range(7):
    F(9)
    R(60)

poly = P[:6]             # шесть вершин шестиугольника

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

print(sum(inside(a, b) for a in range(-20, 21) for b in range(-20, 21)))

Программа печатает 206. Ответ: 206

Решение:

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

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

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

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

size = 39          # Мбайт, первая запись
k = 0.5 * 2.5 * 4  # во сколько раз изменился объём
print(size * k)    # 195.0

Ответ: 195

Решение:

Пятизначное восьмеричное число — это набор из пяти цифр $0\ldots7$, у которого первая цифра не ноль. Нужно, чтобы цифра 4 встречалась ровно дважды и чтобы у каждой четвёрки оба соседа были чётными. Обратите внимание: сама цифра 4 чётная, поэтому две четвёрки рядом стоять могут.

Условие короче всего проверить полным перебором всех $8^5 = 32\,768$ наборов.

from itertools import product

count = 0
for d in product(range(8), repeat=5):
    if d[0] == 0:
        continue
    if d.count(4) != 2:
        continue
    ok = True
    for i in range(5):
        if d[i] == 4:
            if i > 0 and d[i - 1] % 2 == 1:
                ok = False
            if i < 4 and d[i + 1] % 2 == 1:
                ok = False
    if ok:
        count += 1
print(count)

Программа печатает 612. Ответ: 612

Решение:

В файле 6400 строк, в каждой шесть натуральных чисел. Строка подходит, если выполнены оба условия:

• ровно одно значение встречается в строке ровно два раза, а остальные четыре числа попарно различны — то есть среди шести чисел ровно одно «двойное» и ровно четыре «одиночных»;
• среднее арифметическое четырёх неповторяющихся чисел не превосходит суммы повторяющихся чисел; повторяющееся число $x$ стоит дважды, поэтому их сумма равна $2x$.

Проще всего перебрать строки программой, подсчитывая, сколько раз встречается каждое число (класс Counter):

import csv
from collections import Counter

count = 0
for row in csv.reader(open('data.csv'), delimiter=';'):
    nums = [int(x) for x in row]
    c = Counter(nums)
    twice = [v for v, k in c.items() if k == 2]   # значения, встречающиеся 2 раза
    once = [v for v, k in c.items() if k == 1]    # значения, встречающиеся 1 раз
    if len(twice) == 1 and len(once) == 4:
        if sum(once) / 4 <= 2 * twice[0]:
            count += 1
print(count)   # 2241

Условие len(twice) == 1 and len(once) == 4 как раз и означает «ровно одно число повторяется ровно два раза, остальные различны»: оно отбрасывает строки, где какое-то число встречается три и более раз или где повторяющихся пар несколько. Программа находит 2241 подходящую строку. Ответ: 2241

Решение:

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

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

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

import re

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

Ответ: 4

Решение:

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

Один идентификатор из 141 символ занимает $141 \cdot 12 = 1692$ бита. Число байт должно быть целым и минимальным: $1692 = 8 \cdot 211 + 4$, поэтому под него отводится 212 байт.

Все 2560 идентификаторов занимают $2560 \cdot 212 = 542720$ байт, то есть $542720 : 1024 = 530$ Кбайт.

import math

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

Ответ: 530

Решение:

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

• >0 → 1> — цифра 0 превращается в 1, вклад в сумму равен 1;
• >1 → 22> — цифра 1 превращается в две двойки, вклад в сумму равен 4;
• >2 → 2> — цифра 2 не меняется, вклад в сумму равен 2.

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

$$S(n) = 39\cdot 1 + n\cdot 4 + 39\cdot 2 = 117 + 4n.$$

Ищем наименьшее $n$, при котором $117+4n$ — простое число:

• $n=0:\ 117 = 9\cdot 13$ — составное;
• $n=1:\ 121 = 11^2$ — составное;
• $n=2:\ 125 = 5^3$ — составное;
• $n=3:\ 129 = 3\cdot 43$ — составное;
• $n=4:\ 133 = 7\cdot 19$ — составное;
• $n=5:\ 137$ — простое.

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

def run(s):
    while '>1' in s or '>2' in s or '>0' in s:
        if '>1' in s:
            s = s.replace('>1', '22>', 1)
        if '>2' in s:
            s = s.replace('>2', '2>', 1)
        if '>0' in s:
            s = s.replace('>0', '1>', 1)
    return s
def prime(k):
    return k > 1 and all(k % d for d in range(2, int(k ** 0.5) + 1))
for n in range(0, 100):
    s = run('>' + '0' * 39 + '1' * n + '2' * 39)
    if prime(sum(int(c) for c in s if c.isdigit())):
        print(n)      # 5
        break

Ответ: 5

Решение:

Маска 255.255.255.240 оставляет свободными только 4 младших бита последнего байта, все остальные разряды у адресов сети одинаковы.

Левые два байта: $142 = 10001110_2$ — 4 единицы, $108 = 01101100_2$ — 4 единицы, значит $L = 8$.

Правые два байта: третий байт $56 = 00111000_2$ даёт 3 единицы; четвёртый байт равен $118 \wedge 240 = 112 = 01110000_2$ плюс любые 4 младших бита, то есть даёт $3 + k$ единиц, где $k$ — число единиц среди свободных битов. Итого $R = 6 + k$.

Условие $L \lt R$ даёт $8 \lt 6 + k$, то есть $k \ge 3$. Количество четырёхбитовых наборов с тремя или четырьмя единицами равно $C_4^3 + C_4^4 = 4 + 1 = 5$.

ones = lambda x: bin(x).count('1')
count = 0
for b4 in range(112, 128):
    if ones(142) + ones(108) < ones(56) + ones(b4):
        count += 1
print(count)      # 5

Ответ: 5

Решение:

Основание системы счисления 23, а делитель $22 = 23-1$. Так как $23 \equiv 1 \pmod{22}$, любое число сравнимо по модулю 22 с суммой своих 23-ричных цифр (это тот же признак, что и признак делимости на 9 в десятичной системе). Значит, вся сумма делится на 22 тогда и только тогда, когда на 22 делится сумма всех цифр трёх слагаемых.

Считаем суммы цифр:

• $1x1x1x1x1_{23}$: $5 + 4x$;
• $20x24_{23}$: $2+0+x+2+4 = 8 + x$;
• $1x235_{23}$: $1+x+2+3+5 = 11 + x$.

Всего $24 + 6x$. Требуем $24 + 6x \equiv 0 \pmod{22}$, то есть $6x \equiv 20 \pmod{22}$, или $3x \equiv 10 \pmod{11}$, откуда $x \equiv 7 \pmod{11}$. В алфавите 23-ричной системы подходят $x = 7$ и $x = 18$; наименьшее — $x = 7$.

Подставляем $x=7$ и делим сумму на 22:

b = 23

def num(ds):
    n = 0
    for d in ds:
        n = n * b + d
    return n

for x in range(b):                       # ищем наименьшее x
    s = (num([1, x, 1, x, 1, x, 1, x, 1])
         + num([2, 0, x, 2, 4])
         + num([1, x, 2, 3, 5]))
    if s % 22 == 0:
        print(x, s // 22)                # 7 4651779499
        break

Ответ: 4651779499

Решение:

Выражение $\neg\big(P \rightarrow Q\big)$ ложно при всех $x$ тогда и только тогда, когда импликация $P \rightarrow Q$ истинна при всех $x$, где $P = (x \in B) \lor (x \in C)$, а $Q = (x \in A)$.

Это означает, что любая точка объединения

$B \cup C = [30;\ 41] \cup [50;\ 56]$

должна попадать в отрезок $A$. Отрезок — связное множество, поэтому вместе с концами 30 и 56 он содержит и всё между ними. Наименьший подходящий отрезок — $[30;\ 56]$.

Его длина $56 - 30 = 26$.

Ответ: 26

Решение:

Применим правило $F(n) = n \cdot (n-1) \cdot F(n-1)$ три раза подряд:

$$F(123) = 123 \cdot 122 \cdot F(122) = 123 \cdot 122 \cdot 122 \cdot 121 \cdot F(121) = 123 \cdot 122 \cdot 122 \cdot 121 \cdot 121 \cdot 120 \cdot F(120).$$

Значит частное не зависит от самого $F(120)$:

$$\frac{F(123)}{F(120)} = 123 \cdot 122^{2} \cdot 121^{2} \cdot 120 = 15006 \cdot 14762 \cdot 14520 = 3216449665440.$$

print(123 * 122 * 122 * 121 * 121 * 120)   # 3216449665440

Ответ: 3216449665440

Решение:

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

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

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

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

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

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

print(count, best)   # 959 97471

Ответ: 959 97471

Решение:

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

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

В этом варианте внутренних стен нет: Робот ограничен только границами квадрата. Поле в приложенном файле имеет размер $10\times10$, поэтому пересчёт идёт по обычным формулам, без дополнительных проверок.

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

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

# внутренних стен нет
def wall_down(i, j):
    return False

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

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

Решение:

Из кучи в $S$ камней ход «добавить камень» даёт $S+1$, ход «удвоить» даёт $2S$. Так как $2S \ge S+1$ при любом $S \ge 1$, выиграть одним ходом можно тогда и только тогда, когда $2S \ge 153$, то есть при $S \ge 77$.

Поэтому условие «Петя не может выиграть за один ход» означает $S \le 76$.

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

• после хода «+1» получается $S+1$, нужно $S+1 \ge 77$, то есть $S \ge 76$;
• после хода «×2» получается $2S$, нужно $2S \ge 77$, то есть $S \ge 39$.

Вместе с $S \le 76$ остаётся единственное значение $S = 76$.

Проверка: из кучи в 76 камней Петя получает 77 или 152 камней — до 153 не хватает ни в одном случае. Из 77 камней Ваня удваивает и получает 154 камней, из 152 камней Ваня добавляет один камень и получает 153 камней. И то и другое не меньше 153, значит Ваня выигрывает своим первым ходом при любом ходе Пети.

Тот же ответ даёт перебор:

N = 153

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

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

for s in range(1, N):
    # сам выиграть не может, но любой его ход отдаёт победу сопернику
    if not win1(s) and all(win1(t) for t in moves(s)):
        print(s)                  # 76

Ответ: 76

Решение:

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

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

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

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

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

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

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

N = 229

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

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

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

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

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

Ответ: 57 113

Решение:

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

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

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

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

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

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

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

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

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

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

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

• $(10;\ 51)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(20;\ 51)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(21;\ 51)$ — в $(21;\ 102)$; из $(40;\ 51)$ — в $(80;\ 51)$; из $(20;\ 52)$ — в $(20;\ 104)$; из $(20;\ 102)$ — в $(21;\ 102)$);
• $(18;\ 51)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(18;\ 52)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(19;\ 52)$ — в $(19;\ 104)$; из $(36;\ 52)$ — в $(72;\ 52)$; из $(18;\ 53)$ — в $(18;\ 106)$; из $(18;\ 104)$ — в $(19;\ 104)$);
• $(9;\ 52)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(18;\ 52)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(19;\ 52)$ — в $(19;\ 104)$; из $(36;\ 52)$ — в $(72;\ 52)$; из $(18;\ 53)$ — в $(18;\ 106)$; из $(18;\ 104)$ — в $(19;\ 104)$);
• $(9;\ 102)$ — Ваня выигрывает сразу: одним ходом он получает $(9;\ 204)$, а это уже не меньше 123.

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

Ответ: 51

Решение:

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

Решение:

Из числа $x$ исполнитель попадает в $x+1$ (A), $x+2$ (B) или $2x$ (C). Пусть $R(x)$ — количество программ, переводящих $x$ в заданное конечное число. Тогда $$R(x)=R(x+1)+R(x+2)+R(2x),$$ $R(\text{конечного числа})=1$, а $R(x)=0$, если $x$ больше конечного числа (числа только растут, поэтому «перепрыгнув» цель, вернуться нельзя).

Траектория обязана содержать и 11, и 13, а $4\lt 11\lt 13\lt 15$, значит программа распадается на три независимые части: $4\to 11$, $11\to 13$, $13\to 15$. Ответ — произведение.

1) Из 4 в 11. Удвоение полезно только из $x=5$ (даёт 10):

Например, $R(9)=R(10)+R(11)+R(18)=1+1+0=2$, $R(5)=R(6)+R(7)+R(10)=8+5+1=14$, $R(4)=R(5)+R(6)+R(8)=14+8+3=25$.

2) Из 11 в 13. Удвоение даёт 22 — перелёт, поэтому $R(12)=R(13)=1$ и $R(11)=R(12)+R(13)=1+1=2$ (это программы AA и B).

3) Из 13 в 15. Аналогично $R(13)=2$ (программы AA и B).

Итого $25\cdot 2\cdot 2=100$.

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(x + 2) + R(2 * x)
    return R(start)

print(count(4, 11) * count(11, 13) * count(13, 15))

Ответ: 100

Решение:

Запрещена только одна конфигурация — две буквы 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^9$ не нужно: искомое число обязано делиться на 2079, поэтому переберём сразу кратные $n=2079k$ — их всего $\lfloor 10^9/2079\rfloor=481000$, это мгновенно.

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

from fnmatch import fnmatch

for k in range(1, 10 ** 9 // 2079 + 1):
    n = 2079 * k
    if fnmatch(str(n), '33*21?7'):
        print(n, k)

Маска 33*21?7: число начинается на 33, затем произвольный (возможно, пустой) кусок, затем 21, любая цифра и 7 в конце. Программа находит 5 чисел; обратите внимание, что все они идут с шагом $380\cdot 2079=790020$.

Ответ: 336222117 161723 337012137 162103 337802157 162483 338592177 162863 339382197 163243

Решение:

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

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

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

В прилагаемом файле $S = 8200$, $N = 970$.

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)

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

568 50

Ответ: 568 50

Решение:

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

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

Файл A: сумма больших чисел равна $639036$; она даёт остаток $9$ при делении на 37, то есть уже не делится на 37 — уменьшать ничего не нужно, ответ $639036$.Файл B: сумма больших чисел равна $664021240$ и делится на 37. Наименьшая ненулевая разность внутри пары, не кратная 37, равна $6692$, поэтому ответ $664021240 - 6692 = 664014548$.Ответ: 639036 664014548