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

Решение:

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

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

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

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

from itertools import product


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


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

Ответ: yxzw

Решение:

Выручка — это деньги, полученные при продаже, поэтому в таблице «Движение лекарственных средств» нас интересуют только строки с типом операции «Продажа». Цена берётся из таблицы «Препараты» (связь по полю «Артикул»), а сеть аптеки — из таблицы «Аптека» (связь по полю «ID аптеки»).

Шаг 1. В таблице «Аптека» отбираем строки с сетью «Здоровое поколение» и выписываем ID этих аптек.

Шаг 2. В таблице «Препараты» находим пустырник. Важно: под этим названием в базе два разных артикула — упаковка по 20 таблеток за 60 рублей и упаковка по 30 таблеток за 95 рублей. Нужны оба.

Шаг 3. В таблице «Движение лекарственных средств» оставляем строки: тип операции «Продажа», ID аптеки — из шага 1, артикул — один из двух найденных. Вся таблица и так охватывает 1–14 июня, так что дополнительное ограничение по дате ничего не отсекает. Суммируем «Количество упаковок»: 96 упаковок первого артикула и 105 упаковок второго.

Шаг 4. Умножаем количество на цену соответствующего артикула и складываем: $96 \cdot 60 + 105 \cdot 95 = 5760 + 9975 = 15735$ рублей. В таблице это удобно сделать формулой СУММПРОИЗВ по столбцам «Количество упаковок» и подтянутой функцией ВПР цене.

Ответ: 15735

Решение:

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

Ищем самое короткое слово, поэтому начинаем с длины 2. Всего таких слов четыре: 00, 01, 10 и 11. Слова 01, 10 и 11 уже используются для букв А, Б и В, поэтому остаётся только слово 00.

Проверяем: слово 00 является началом кода 000 буквы Г, значит условие Фано нарушается — как и требуется. Слово состоит из двух знаков и ни с одним из имеющихся кодов не совпадает, поэтому оно и есть ответ.

Ответ: 00

Решение:

Автомат выводит две суммы квадратов цифр, записанные подряд в порядке невозрастания. Каждая такая сумма имеет вид $a^2+b^2$, где $a$ и $b$ — цифры, поэтому она не превосходит $9^2+9^2=162$, то есть содержит не больше трёх цифр.

Значит, число 7434 нужно разбить на два куска $A$ и $B$, причём $A\ge B$ и оба не больше 162. Разбиение 7 и 434 не подходит: $7\lt 434$. Разбиение 743 и 4 не подходит: $743\gt 162$. Остаётся единственный вариант: $A=74$, $B=34$.

Пусть исходное число — $\overline{d_1d_2d_3}$. Тогда $d_1^2+d_2^2=74$ и $d_2^2+d_3^2=34$.

Квадраты цифр — это 0, 1, 4, 9, 16, 25, 36, 49, 64, 81. Перебирая пары, получаем:

• 74 представляется единственным способом: $25+49$, то есть цифрами 5 и 7;
• 34 представляется единственным способом: $9+25$, то есть цифрами 3 и 5.

Цифра $d_2$ входит в обе пары, поэтому $d_2=5$. Отсюда $d_1=7$ и $d_3=3$: число определяется однозначно.

def f(n):
    d = [int(c) for c in str(n)]
    a = d[0] ** 2 + d[1] ** 2
    b = d[1] ** 2 + d[2] ** 2
    return int(str(max(a, b)) + str(min(a, b)))

print(max(n for n in range(100, 1000) if f(n) == 7434))

Ответ: 753

Решение:

Хвост поднят, поэтому Вперёд 100 Направо 90 Вперёд 100 только переводит Черепаху в точку $(100;100)$. После Направо 45 голова смотрит под углом $-45^{\circ}$ к оси $Ox$, и хвост опускается.

Цикл замыкается за два повтора: рисуется прямоугольник $20\times 30$, повёрнутый на $45^{\circ}$, с вершинами $(100;100)$, $(100+10\sqrt{2};\,100-10\sqrt{2})$, $(100-5\sqrt{2};\,100-25\sqrt{2})$, $(100-15\sqrt{2};\,100-15\sqrt{2})$.

Все стороны имеют угловые коэффициенты $\pm 1$, поэтому в переменных $s=x+y$ и $d=x-y$ условие «строго внутри» становится совсем простым:

$$200-30\sqrt{2}\lt s\lt 200,\qquad 0\lt d\lt 20\sqrt{2}.$$

Так как $30\sqrt{2}\approx 42{,}43$ и $20\sqrt{2}\approx 28{,}28$, подходят целые $s=158,159,\dots,199$ (42 значения) и $d=1,2,\dots,28$ (28 значений).

Пара $(s;d)$ отвечает целой точке $x=\dfrac{s+d}{2}$, $y=\dfrac{s-d}{2}$ тогда и только тогда, когда $s$ и $d$ одной чётности. Среди значений $s$ — 21 чётное и 21 нечётное, среди значений $d$ — 14 чётных и 14 нечётных.

Итого $21\cdot 14+21\cdot 14=588$. Проверим программой:

from math import sin, cos, radians

P = [(0.0, 0.0)]
x = y = 0.0
a = 90.0                      # голова смотрит вдоль оси Oy

def F(n):                     # Вперёд n
    global x, y
    x = round(x + n * cos(radians(a)), 9)   # round убирает шум float
    y = round(y + n * sin(radians(a)), 9)
    P.append((x, y))

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

F(100); R(90); F(100); R(45)  # хвост поднят - это не рисуется
P = [(x, y)]                  # опустили хвост
for i in range(2):            # прямоугольник замыкается за 2 повторения
    F(20); R(90); F(30); R(90)

def inside(px, py):           # фигура выпуклая, обход по часовой стрелке
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        if (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1) >= -1e-9:
            return False      # точка на линии или снаружи
    return True

xs = [p[0] for p in P]; ys = [p[1] for p in P]
print(sum(inside(px, py)
          for px in range(int(min(xs)) - 1, int(max(xs)) + 2)
          for py in range(int(min(ys)) - 1, int(max(ys)) + 2)))

Ответ: 588

Решение:

Коды пикселей записаны в файле оригинального (несжатого) изображения, поэтому сначала найдём его размер. Он на 35% больше сжатого:

$75 \cdot 1{,}35 = 101{,}25$ Кбайт $= 101{,}25 \cdot 1024 \cdot 8 = 829440$ бит.

Пикселей в изображении: $1024 \cdot 100 = 102400$. Если на пиксель отводится $i$ бит, то

$102400 \cdot i \le 829440$, откуда $i \le \frac{829440}{102400} = 8{,}1$.

Число бит целое, поэтому $i = 8$, и в изображении может быть $2^8 = 256$ цветов.

W, H = 1024, 100
V = 75 * 1024 * 8 * 135 // 100   # исходный файл на 35% больше сжатого, в битах
i = V // (W * H)                 # максимальное целое число бит на пиксель
print(V, i, 2 ** i)              # 829440 8 256

Ответ: 256

Решение:

Буквы в алфавитном порядке: К, Н, О, Р, С, Я. Наименьшее подходящее слово строим жадно, слева направо ставя минимальную букву, при которой условия ещё можно выполнить.

Условия: букв К не более трёх, букв Я ровно две.

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

Получилось слово КККНЯЯ. Заменим буквы цифрами шестеричной системы (К=0, Н=1, О=2, Р=3, С=4, Я=5): КККНЯЯ → $000155_6$, значение $$1 \cdot 6^2 + 5 \cdot 6 + 5 = 36 + 30 + 5 = 71.$$ Номер слова равен $71 + 1 = 72$.

from itertools import product

for n, w in enumerate(product('КНОРСЯ', repeat=6), 1):
    s = ''.join(w)
    if s.count('К') <= 3 and s.count('Я') == 2:
        print(n, s)
        break

Ответ: 72

Решение:

В файле 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

Решение:

Текст дан сразу в пяти форматах (DOC, DOCX, ODT, RTF, TXT) — это один и тот же текст, достаточно открыть любой файл в текстовом редакторе (MS Word, LibreOffice Writer, «Блокнот»).

Открываем поиск (Ctrl+F) и настраиваем параметры:

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

Кнопка «Найти все» показывает 45 совпадений.

Проверка программой по текстовому файлу:

import re

text = open('59122_10.txt', encoding='cp1251').read()
print(len(re.findall(r'\bтеперь\b', text)))

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

Решение:

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

Один идентификатор из 404 символа занимает $404 \cdot 9 = 3636$ бит. Число байт должно быть целым и минимальным: $3636 = 8 \cdot 454 + 4$, поэтому под него отводится 455 байт.

Все 3072 идентификаторов занимают $3072 \cdot 455 = 1397760$ байт, то есть $1397760 : 1024 = 1365$ Кбайт.

import math

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

Ответ: 1365

Решение:

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

Разберём, что делает замена (15, 5551): единица «перепрыгивает» через одну стоящую справа от неё пятёрку, и при этом добавляются две новые пятёрки. Изначально справа от единицы 25 пятёрок, поэтому такая замена выполнится ровно 25 раз, после чего единица окажется в конце строки, а пятёрок станет $25 + 2 \cdot 25 = 75$.

Теперь цепочка 15 не находится, но единица в строке есть, поэтому срабатывает ветка ИНАЧЕ: замена (1, 5) превращает последнюю единицу в пятёрку. Пятёрок становится 76, единиц больше нет, и цикл завершается.

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

s = "1" + "5" * 25
while "15" in s or "1" in s:
    if "15" in s:
        s = zamenit(s, "15", "5551")
    elif "1" in s:
        s = zamenit(s, "1", "5")
print(s.count("5"))   # 76

Ответ: 76

Решение:

Маска 255.255.224.0 в двоичном виде — 11111111.11111111.11100000.00000000, в ней 19 единиц. Значит, старшие 19 битов — это адрес сети, они одинаковы у всех её узлов, а младшие $32 - 19 = 13$ битов узловые: сеть содержит $2^{13} = 8192$ адреса. Адрес сети равен исходному: 0 & 224 = 0, то есть 113.216.0.0.

Ключевая идея: сумма единиц всего адреса — это сумма единиц фиксированной части плюс сумма единиц узловой части, поэтому чётность суммы зависит только от чётности числа единиц в 13 свободных битах (если фиксированная часть даёт чётный вклад). Фиксированные биты — 01110001.11011000.000: в 113 четыре единицы, в 216 тоже четыре, в трёх старших нулях — ни одной, всего 8 — число чётное.

Остаётся посчитать, у скольких 13-битных наборов число единиц чётно. Их ровно половина: смена последнего бита на противоположный превращает каждый «чётный» набор в «нечётный» и обратно, то есть задаёт взаимно однозначное соответствие между этими двумя группами. Поэтому подходящих адресов $8192 : 2 = 4096$.

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

from itertools import product

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

ip = to_bits('113.216.0.0')
mask = to_bits('255.255.224.0')
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 a.count('1') % 2 == 0))

Ответ: 4096

Решение:

Переведём все слагаемые в степени восьмёрки: $4^{2022}=2^{4044}=8^{1348}$, $6\cdot 4^{522}=6\cdot 2^{1044}=6\cdot 8^{348}$, $5\cdot 64^{510}=5\cdot 8^{1020}$, $3\cdot 2^{330}=3\cdot 8^{110}$, $100 = 144_8$. Тогда

$$N = 8^{1348} + 5\cdot 8^{1020} - 6\cdot 8^{348} - 3\cdot 8^{110} - 144_8.$$

Каждое вычитание берёт заём у ближайшей слева ненулевой цифры и превращает промежуточные нули в максимальные цифры 7. Раскрыв все заёмы, получаем восьмеричную запись из 1349 цифр:

1, затем 327 нулей, затем 4, затем 671 семёрка, затем 1, затем 237 семёрок, затем 4, затем 107 семёрок, затем 6, 3, 4.

Количество семёрок: $671 + 237 + 107 = 1015$.

Тот же результат даёт программа:

def to_base(n, b):
    s = ''
    while n:
        s = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n % b] + s
        n //= b
    return s

n = 4**2022 - 6 * 4**522 + 5 * 64**510 - 3 * 2**330 - 100
print(to_base(n, 8).count('7'))     # 1015

Ответ: 1015

Решение:

Обозначим $P = \text{ТРЕУГ}(x, 11, 18)$, $Q = \neg(\text{МАКС}(x, 5) \gt 15)$, $R = \text{ТРЕУГ}(x, A, 5)$. Формула имеет вид $\neg((P \equiv Q) \land R)$ и тождественно истинна тогда и только тогда, когда при каждом натуральном $x$, для которого $P$ и $Q$ совпадают, значение $R$ ложно.

Находим $P$. Невырожденный треугольник со сторонами $x$, 11 и 18 существует, когда $x + 11 \gt 18$ и $11 + 18 \gt x$, то есть при $7 \lt x \lt 29$. Значит $P = 1$ при $8 \le x \le 28$.

Находим $Q$. При $x \le 5$ имеем $\text{МАКС}(x, 5) = 5$, иначе $\text{МАКС}(x, 5) = x$. Поэтому условие $\text{МАКС}(x, 5) \gt 15$ равносильно $x \gt 15$, и $Q = 1$ при $x \le 15$.

Сравним $P$ и $Q$ по участкам:

Итак, $R = \text{ТРЕУГ}(x, A, 5)$ должно быть ложно при всех $x$ из отрезка $[8; 15]$ и при всех $x \ge 29$.

Треугольник со сторонами $x$, $A$ и 5 существует, когда $x + 5 \gt A$ и $A + 5 \gt x$, то есть при $A - 5 \lt x \lt A + 5$.

Условие «$R$ ложно при всех $x \ge 29$» требует $A + 5 \le 29$, откуда $A \le 24$.

Проверим $A = 24$: треугольник существует лишь при $19 \lt x \lt 29$, а точки $8 \le x \le 15$ и $x \ge 29$ в этот промежуток не попадают. Значит $A = 24$ подходит и является наибольшим.

def treug(a, b, c):
    a, b, c = sorted((a, b, c))
    return a + b > c

best = 0
for A in range(1, 100):
    if all(not ((treug(x, 11, 18) == (not (max(x, 5) > 15))) and treug(x, A, 5))
           for x in range(1, 1000)):
        best = A
print(best)   # 24

Ответ: 24

Решение:

Рекурсия здесь «раскручивается» вверх: пока аргумент не превосходит 2024, функция домножает его на значение для следующего числа, а на аргументе больше 2024 вычисления обрываются и функция просто возвращает своё $n$. Поэтому нужные значения выписываются в пару строк.

Так как $2025 \gt 2024$, то $F(2025) = 2025$, а значит $F(2024) = 2024 \cdot F(2025) = 2024 \cdot 2025$. Дальше по той же формуле $F(2023) = 2023 \cdot F(2024)$ и $F(2022) = 2022 \cdot F(2023) = 2022 \cdot 2023 \cdot F(2024)$.

Огромный общий множитель $F(2024)$ сокращается, и считать его не нужно: $\dfrac{F(2022)}{F(2024)} = 2022 \cdot 2023 = 4090506$.

import sys
sys.setrecursionlimit(10000)

def F(n):
    if n > 2024:
        return n
    return n * F(n + 1)

print(F(2022) // F(2024))   # 4090506

Ответ: 4090506

Решение:

Читаем файл в список и перебираем пары соседних элементов $(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+1$, ход «удвоить» даёт $2S$. Так как $2S \ge S+1$ при любом $S \ge 1$, выиграть одним ходом можно тогда и только тогда, когда $2S \ge 177$, то есть при $S \ge 89$.

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

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

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

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

Проверка: из кучи в 88 камней Петя получает 89 или 176 камней — до 177 не хватает ни в одном случае. Из 89 камней Ваня удваивает и получает 178 камней, из 176 камней Ваня добавляет один камень и получает 177 камней. И то и другое не меньше 177, значит Ваня выигрывает своим первым ходом при любом ходе Пети.

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

N = 177

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

Ответ: 88

Решение:

Сначала опишем позиции, из которых игра заканчивается одним ходом. Из кучи в $n$ камней ($n \le 128$) ходящий выигрывает сразу, если $n + 1 \ge 129$ или $2n \ge 129$, то есть при $n \ge 65$. Значит, при $n$ от 65 до 128 ходящий побеждает немедленно.

Теперь найдём позицию, в которую Пете выгодно попасть после первого хода. Из кучи в 64 камня возможны только 65 и 128 — обе позиции выигрышны для соперника, поэтому 64 проигрышна для того, кто из неё ходит. Более того, 64 — единственная такая позиция: чтобы все ходы вели в диапазон 65–128, нужно $n + 1 \ge 65$, то есть $n \ge 64$, и одновременно $n \le 64$, иначе ходящий выиграл бы сам.

Итак, стратегия Пети — первым ходом получить ровно 64 камня, после чего Ваня вынужденно отдаёт позицию 65 или 128, и Петя добивает вторым ходом (из 65 удвоением до 130, из 128 добавлением камня до 129). Попасть в 64 можно из $S = 63$ (добавить камень) и из $S = 32$ (удвоить). Оба значения не превосходят 64, поэтому первым ходом Петя выиграть не может — второе условие задачи тоже выполнено.

Записываем найденные значения в порядке возрастания: 32 и 63.

def win_now(s):
    return s + 1 >= 129 or 2 * s >= 129

res = []
for s in range(1, 129):
    if win_now(s):                       # Петя выигрывает сразу — не подходит
        continue
    for m in (s + 1, 2 * s):             # ход Пети
        if not win_now(m) and all(win_now(k) for k in (m + 1, 2 * m)):
            res.append(s)
            break
print(res[:2])                           # [32, 63]

Ответ: 32 63

Решение:

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

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

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

def moves(s):
    return [s + 1, s + 5, 4 * 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, 105):
    if lose2(s) and not lose1(s):
        print(s)
        break

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

• $21$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $26$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $27$ — в $108$; из $31$ — в $124$; из $104$ — в $105$);
• $25$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $26$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $27$ — в $108$; из $31$ — в $124$; из $104$ — в $105$);
• $80$ — Ваня выигрывает сразу: одним ходом он получает $320$, а это уже не меньше 105.

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

Ответ: 20

Решение:

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

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

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

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

finish = {}
for i in sorted(data):
    dur, deps = data[i]
    finish[i] = max([finish[d] for d in deps], default=0) + dur

print(max(finish.values()))

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

Решение:

Команда А увеличивает число на $2$, команда В — на $10$; порядок команд на итоговое число не влияет, важно лишь, сколько раз использована каждая. Всего надо прибавить $71 - 5 = 66$. Если команда А использована $n$ раз, а команда В — $k$ раз, то

$$2 n + 10 k = 66.$$

Отсюда подходят только $k = 0, 1, 2, 3, 4, 5, 6$ (при остальных $k$ остаток $66 - 10k$ не делится на $2$ нацело или отрицателен).

Программа — это последовательность команд, поэтому при фиксированных $n$ и $k$ количество программ равно числу способов расставить $k$ команд В среди всех $n + k$ команд, то есть $C_{n+k}^{\,k}$.

Складываем: $1 + 29 + 300 + 1330 + 2380 + 1287 + 84 = 5411$.

Тот же результат даёт короткая программа:

from functools import lru_cache

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

print(f(5, 71))

Ответ: 5411

Решение:

В файле записана одна длинная строка из букв T, U, V, W, X, Y, Z (десять миллионов символов). Нужен самый длинный непрерывный кусок этой строки, в котором буква T встречается ровно 100 раз.

Ключевая идея: любой такой кусок содержит ровно сто подряд идущих (по порядку следования в строке) букв T, а между ними и по краям стоят произвольные другие буквы. Значит, достаточно перебрать все окна из 100 подряд идущих букв T и для каждого окна раздвинуть границы максимально широко — влево до предыдущей буквы T (не захватывая её) и вправо до следующей буквы T (тоже не захватывая её). Если слева или справа буквы T больше нет, границей служит начало или конец строки. Из всех полученных длин берём наибольшую.

Для этого сначала выпишем в список номера позиций всех букв T, а затем пройдёмся по нему окном ширины 100.

s = open('24.txt').read().strip()
p = [i for i in range(len(s)) if s[i] == 'T']

best = 0
for k in range(len(p) - 99):
    # окно из ста букв T: p[k] … p[k+99]
    left = p[k - 1] + 1 if k > 0 else 0
    right = p[k + 100] - 1 if k + 100 < len(p) else len(s) - 1
    best = max(best, right - left + 1)

print(best)

Программа работает за один проход по списку позиций, то есть за $O(N)$, и выводит 133. Это означает, что в найденном фрагменте кроме ста букв T стоят ещё 33 буквы других видов. Ответ: 133

Решение:

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

Числа перебираются по убыванию, начиная с 799999. Кратность 17 проверяется как m % 17 == 0, причём нулевое значение по условию кратным не считается, поэтому добавляем проверку $M \ne 0$. Найденные числа выводятся в порядке убывания.

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

n = 800000
found = 0
while found < 5:
    n -= 1
    m = M(n)
    if m != 0 and m % 17 == 0:
        print(n, m)
        found += 1

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

799995 266662
799990 399993
799967 114274
799956 399976
799922 399959

Ответ: 799995 266662 799990 399993 799967 114274 799956 399976 799922 399959

Решение:

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

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

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

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

f = open('26.txt')
s, n = map(int, f.readline().split())
a = sorted(int(x) for x in f)

total = 0
k = 0
for x in a:
    if total + x <= s:
        total += x
        k += 1
    else:
        break

base = sum(a[:k - 1])                            # k-1 самых маленьких
big = max(x for x in a[k - 1:] if base + x <= s)  # самый большой, который ещё влезает
print(k, big)

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

629 50

Ответ: 629 50

Решение:

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

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

Файл A: сумма больших чисел равна $665848$; она даёт остаток $8$ при делении на 35, то есть уже не делится на 35 — уменьшать ничего не нужно, ответ $665848$.Файл B: сумма больших чисел равна $665535990$ и делится на 35. Наименьшая ненулевая разность внутри пары, не кратная 35, равна $1653$, поэтому ответ $665535990 - 1653 = 665534337$.Ответ: 665848 665534337