Вариант 7 · Июль 2026

Решение:

Степени вершин схемы: А — 2, Б — 3, В — 1, Г — 4, Д — 4, Е — 4, И — 3, К — 3.

Число заполненных клеток в строках таблицы: 1 — 4, 2 — 4, 3 — 3, 4 — 3, 5 — 2, 6 — 3, 7 — 4, 8 — 1.

Единственная вершина степени 1 — это В, единственный тупиковый пункт — 8, значит, В = 8. Единственный сосед пункта 8 — это 4, а единственный сосед В на схеме — Б, поэтому Б = 4. Единственная вершина степени 2 — это А, единственный такой пункт — 5, значит, А = 5 (и действительно пункт 5 соседствует с 4, как А с Б).

Дальше:

• Соседи А — это Б и Г. Соседи пункта 5 — это 1 и 4, а 4 — это Б, поэтому Г = 1.
• Соседи Б — это А, В и Д. Соседи пункта 4 — это 2, 5, 8, значит, Д = 2.
• Соседи Г — это А, Д, Е и И. Соседи пункта 1 — это 2, 3, 5, 7; свободны 3 и 7. У Е степень 4, у И — степень 3, а у пункта 3 степень 3, у пункта 7 — степень 4. Значит, И = 3 и Е = 7.

Дорога Г—И — это клетка на пересечении строки 1 и столбца 3, она равна 8.

Ответ: 8

Решение:

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

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

w	x	y	z	F
0	0	1	0	0
1	0	1	0	0
1	1	1	0	0

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

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

from itertools import product


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


def F(w, x, y, z):
    return impl(y, not impl(x, w)) 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)

Ответ: xwyz

Решение:

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

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

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

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

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

Ответ: 429795

Решение:

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

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

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

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

Буква	Кодовое слово	Длина	Сколько раз	Всего знаков
Л	1	1	1	1
О	0000	4	2	8
Н	0001	4	2	8
К	0010	4	1	4
А	0011	4	1	4

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

Ответ: 25

Решение:

Пусть $r=N\bmod 4$ — последняя цифра четверичной записи $N$. Разберём, что приписывается справа в каждом случае.

• $r=0$: приписываются две последние четверичные цифры, то есть запись удлиняется на два разряда, а приписанное значение равно $N\bmod 16$. Значит $R=16N+(N\bmod 16)$.
• $r=1$: $2r=2=2_4$ — один разряд, поэтому $R=4N+2$.
• $r=2$: $2r=4=10_4$ — два разряда, поэтому $R=16N+4$.
• $r=3$: $2r=6=12_4$ — два разряда, поэтому $R=16N+6$.

Сверим с примерами из условия: $N=11$, $r=3$, $R=16\cdot 11+6=182$; $N=12$, $r=0$, $R=16\cdot 12+12=204$. Совпадает.

Ключевое наблюдение: только при $r=1$ число увеличивается в 4 раза, во всех остальных случаях — в 16 раз.

Нужно наименьшее $N$, при котором $R\ge 1025$. Рассмотрим все четыре случая.

• $r=1$: $4N+2\ge 1025\Rightarrow N\ge 256$. Наименьшее число вида $4k+1$ — это $N=257$.
• $r=2$: $16N+4\ge 1025\Rightarrow N\ge 64$. Наименьшее число вида $4k+2$ — это $N=66$, $R=16\cdot 66+4=1060$.
• $r=3$: $16N+6\ge 1025\Rightarrow N\ge 64$. Наименьшее число вида $4k+3$ — это $N=67$, $R=1078$.
• $r=0$: $N=64$ даёт $R=16\cdot 64+0=1024$ — ровно на единицу меньше нужного, не подходит. Следующее кратное четырём $N=68$ даёт $R=16\cdot 68+4=1092$.

Наименьшее из чисел 257, 66, 67, 68 — это 66.

def alg(n):
    q = ''
    m = n
    while m:
        q = str(m % 4) + q
        m //= 4
    if n % 4 == 0:
        q += q[-2:]
    else:
        t = (n % 4) * 2
        q += str(t) if t < 4 else str(t // 4) + str(t % 4)
    return int(q, 4)

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

Ответ: 66

Решение:

Поворот «Направо 270» равносилен повороту «Налево 90», поэтому первая команда «Повтори 2» чертит прямоугольник влево-вверх: вверх 19, влево 16, вниз 19, вправо 16. Его вершины — $(0;0)$, $(0;19)$, $(-16;19)$, $(-16;0)$.

С поднятым хвостом Черепаха поднимается в точку $(0;4)$, поворачивает направо и командой «Назад 8» смещается влево, в точку $(-8;4)$, после чего голова снова смотрит вверх. Второй прямоугольник — $(-8;4)$, $(-8;16)$, $(-1;16)$, $(-1;4)$; он целиком лежит внутри первого.

Значит, объединение фигур — это просто большой прямоугольник $-16\le x\le0$, $0\le y\le19$, и именно его контур служит границей области. Строго внутри лежат точки с $x\in\{-15,\dots,-1\}$ (15 значений) и $y\in\{1,\dots,18\}$ (18 значений), то есть $15\cdot18=270$ точек.

print((16 - 1) * (19 - 1))   # 270

Ответ: 270

Решение:

Пусть цвет одного пикселя кодируется $i$ битами. Всего в изображении $1000 \cdot 3300 = 3300000$ пикселей, значит файл (без заголовка) занимает $3300000 \cdot i$ бит.

Переведём отведённую память в биты: $1320 \cdot 1024 \cdot 8 = 10813440$ бит.

Файл должен поместиться в отведённую память: $3300000 \cdot i \le 10813440$, откуда $i \le \frac{10813440}{3300000} \approx 3{,}28$.

Число бит на пиксель — целое, поэтому наибольшее подходящее значение $i = 3$.

При $i$ битах на пиксель можно закодировать $2^i$ различных цветов, поэтому в палитре может быть $2^{3} = 8$ цветов.

W, H = 1000, 3300
V = 1320 * 1024 * 8  # отведённая память в битах
i = V // (W * H)     # максимальное целое число бит на пиксель
print(i, 2 ** i)     # 3 8

Ответ: 8

Решение:

Буквы в алфавитном порядке: А, М, О, Т. Слова четырёхбуквенные, поэтому с каждой фиксированной первой буквы начинается ровно $4^3 = 64$ слова.

Раньше слов на букву О идут все слова на А и на М — это $2 \cdot 64 = 128$ слов. Значит, первое слово на О (это ОААА) имеет номер $128 + 1 = 129$.

Тот же результат через четверичную систему (А=0, М=1, О=2, Т=3): ОААА → $2000_4 = 2 \cdot 4^3 = 128$, номер $128 + 1 = 129$.

from itertools import product

for n, w in enumerate(product('АМОТ', repeat=4), 1):
    if w[0] == 'О':
        print(n, ''.join(w))
        break

Ответ: 129

Решение:

В каждой строке таблицы семь чисел. Первое условие означает, что набор кратностей значений в строке равен $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).

Параметры поиска:

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

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

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

import re

text = open('text.txt', encoding='utf-8').read()
print(len(re.findall(r'\bПосле\b', text)))

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

Решение:

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

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

Все 13 312 идентификаторов занимают $13312 \cdot 135 = 1797120$ байт, то есть $1797120 : 1024 = 1755$ Кбайт.

import math

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

Ответ: 1755

Решение:

Посмотрим на роль символа «>». Замены >2 → >3 и >3 → >1 меняют цифру на месте, не сдвигая указатель, и только замена >1 → 1> пропускает цифру влево от указателя, после чего она уже не изменяется.

Значит любая цифра, стоящая за указателем, доводится до единицы: тройка становится единицей, двойка сначала становится тройкой, а потом единицей. В итоге вся строка состоит из единиц, и сумма цифр просто равна их количеству: $$16 + n + 16 = 32 + n.$$

Перебираем $n$: $33 = 3 \cdot 11$, $34$, $35 = 5 \cdot 7$, $36$ — составные, а $32 + 5 = 37$ — простое число. Наименьшее подходящее $n = 5$.

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

def prostoe(x):
    d = 2
    while d * d <= x:
        if x % d == 0:
            return False
        d += 1
    return x > 1

def rabota(s):
    while ">1" in s or ">2" in s or ">3" in s:
        if ">1" in s:
            s = zamenit(s, ">1", "1>")
        if ">2" in s:
            s = zamenit(s, ">2", ">3")
        if ">3" in s:
            s = zamenit(s, ">3", ">1")
    return s

n = 1
while True:
    s = rabota(">" + "1" * 16 + "2" * n + "3" * 16)
    summa = sum(int(c) for c in s if c != ">")
    if prostoe(summa):
        print(n, summa)   # 5 37
        break
    n += 1

Ответ: 5

Решение:

В маске 255.255.255.248 = 11111111.11111111.11111111.11111000 двадцать девять единиц, поэтому первые 29 битов адреса фиксированы, а последние 3 свободны: в сети $2^3 = 8$ адресов. Адрес сети: 48 & 248 = 00110000 & 11111000 = 00110000, то есть это адреса от 212.84.49.48 до 212.84.49.55.

Общее число нулей в адресе складывается из нулей неизменяемой части и нулей узловой части, поэтому достаточно посмотреть на чётности. Фиксированные биты — 11010100.01010100.00110001.00110: в 212 четыре нуля, в 84 — пять, в 49 — пять, в пяти старших битах последнего байта 00110 — три, всего $4+5+5+3 = 17$, то есть нечётное число.

Значит, общее количество нулей будет чётным ровно тогда, когда в трёх узловых битах нулей нечётное число — один или три. Наборов с одним нулём $C_3^1 = 3$ (это 011, 101, 110), с тремя нулями — $C_3^3 = 1$ (набор 000), итого $3 + 1 = 4$ адреса: 212.84.49.48, 212.84.49.51, 212.84.49.53 и 212.84.49.54.

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

from itertools import product

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

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

Ответ: 4

Решение:

Распишем операнды по степеням основания 26:

$13yx5_{26} = 1 \cdot 26^4 + 3 \cdot 26^3 + y \cdot 26^2 + x \cdot 26 + 5$,

$24y13_{26} = 2 \cdot 26^4 + 4 \cdot 26^3 + y \cdot 26^2 + 1 \cdot 26 + 3$.

Сумма: $S = 3 \cdot 26^4 + 7 \cdot 26^3 + 2y \cdot 26^2 + (x + 1) \cdot 26 + 8$.

По модулю 8: $26 \equiv 2$, $26^2 = 676 \equiv 4$, $26^3 \equiv 2 \cdot 4 = 8 \equiv 0$, $26^4 \equiv 0 \pmod 8$. Тогда

$S \equiv 2y \cdot 4 + (x + 1) \cdot 2 + 8 \equiv 8y + 2(x + 1) \equiv 2(x + 1) \pmod 8$.

Слагаемое с $y$ кратно 8, поэтому остаток от $y$ не зависит — условие «при любом значении $y$» выполнено автоматически.

Условие $2(x + 1) \equiv 0 \pmod 8$ равносильно $x + 1 \equiv 0 \pmod 4$, то есть $x \equiv 3 \pmod 4$. В алфавите 26-ричной системы (цифры $0 \ldots 25$) подходят $x \in \{3,\ 7,\ 11,\ 15,\ 19,\ 23\}$; наибольшее — $x = 23$.

При $x = 23$ и $y = 2$: $S = 3 \cdot 456976 + 7 \cdot 17576 + 4 \cdot 676 + 24 \cdot 26 + 8 = 1497296$, и $1497296 : 8 = 187162$.

def num(digits, base):
    v = 0
    for d in digits:
        v = v * base + d
    return v

good = [x for x in range(26)
        if all((num([1,3,y,x,5], 26) + num([2,4,y,1,3], 26)) % 8 == 0
               for y in range(26))]
x = max(good)
print(good, x, (num([1,3,2,x,5], 26) + num([2,4,2,1,3], 26)) // 8)

Ответ: 187162

Решение:

Дизъюнкция ложна только тогда, когда ложны все три её слагаемых. Значит, выражение тождественно истинно ровно тогда, когда не найдётся пары целых неотрицательных $x$ и $y$, для которой одновременно $y \le x$, $x \le 60$ и $x + 2y \ge A$.

Иначе говоря, на всём «опасном» множестве $0 \le y \le x \le 60$ обязано выполняться неравенство $x + 2y \lt A$. Осталось найти наибольшее значение суммы $x + 2y$ на этом множестве. Чем больше $x$, тем больше и допустимое $y$, поэтому максимум достигается в самой «дальней» точке $x = y = 60$ и равен $60 + 2 \cdot 60 = 180$.

Значит, нужно $A \gt 180$, и наименьшее целое такое число — $A = 181$. Проверим: при $A = 181$ в любой точке проверочного множества $x + 2y \le 180 \lt 181$, то есть истинно первое слагаемое; вне этого множества истинно второе ($y \gt x$) или третье ($x \gt 60$) слагаемое. При $A = 180$ выражение ломается на паре $x = y = 60$: там все три скобки ложны.

best = max(x + 2 * y
           for x in range(0, 61)
           for y in range(0, x + 1))
print(best + 1)   # 181

Ответ: 181

Решение:

Число 23 нечётное, поэтому $F(23) = 2 + 2 \cdot F(21)$. Нечётная ветка уменьшает аргумент сразу на 2, значит вся цепочка идёт только по нечётным числам, и формула для чётных $n$ не понадобится вовсе.

База: $F(1) = 1$. Далее каждый раз удваиваем предыдущее значение и прибавляем 2:

$n$	$F(n)$
1	1
3	4
5	10
7	22
9	46
11	94
13	190
15	382
17	766
19	1534
21	3070
23	6142

Здесь $F(3) = 2 + 2 \cdot 1 = 4$, $F(5) = 2 + 2 \cdot 4 = 10$ и так далее.

Можно заметить закономерность: величина $F(n) + 2$ на каждом шаге удваивается, поэтому $F(2k + 1) = 3 \cdot 2^{k} - 2$. При $k = 11$ получаем $3 \cdot 2048 - 2 = 6142$.

import sys
sys.setrecursionlimit(10000)

def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + 3 * F(n - 1)
    return 2 + 2 * F(n - 2)

print(F(23))   # 6142

Ответ: 6142

Решение:

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

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

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

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

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

print(count, best)   # 227 96784219

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

Решение:

Позиция игры описывается одним числом $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

Решение:

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

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

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

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

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

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

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

N = 2022

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])   # два наименьших

Ответ: 505 1009

Решение:

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

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

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

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, 143):
    p = (1, s)
    if over(p):
        break
    if lose2(p) and not lose1(p):
        print(s)
        break

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

• $(2;\ 69)$ — Ваня выигрывает сразу: одним ходом он получает $(3;\ 69)$, а это уже не меньше 144;
• $(1;\ 70)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(1;\ 71)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(2;\ 71)$ — в $(3;\ 71)$; из $(1;\ 72)$ — в $(2;\ 72)$; из $(1;\ 142)$ — в $(2;\ 142)$);
• $(1;\ 138)$ — Ваня выигрывает сразу: одним ходом он получает $(2;\ 138)$, а это уже не меньше 144.

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

Ответ: 69

Решение:

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

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

ID процесса	Время выполнения, мс	Зависит от	Момент завершения, мс
1	4	0	4
2	3	0	3
3	1	1; 2	5
4	7	3	12
5	6	3	11
6	3	5	14
7	1	4; 6	15
8	2	7	17
9	7	0	7
10	8	0	8
11	6	9	13
12	6	10	14

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

# данные из прилагаемого файла: 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

Решение:

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

from functools import lru_cache

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

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

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

Решение:

Алфавитный порядок для наших символов — это X, Y, Z. Значит «обратный алфавитный порядок» означает, что каждый следующий символ не идёт в алфавите позже предыдущего: $s_i\le s_{i-1}$ (нестрогое неравенство, потому что повторы разрешены). Для символов это обычное сравнение строк в Python.

Достаточно одного прохода по файлу: храним длину текущей подходящей серии cur. Если очередной символ не больше предыдущего, серия продолжается (cur += 1), иначе серия обрывается и новая начинается с текущего символа (cur = 1). Максимум из всех значений cur и есть ответ.

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

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

print(mx)

Программа выводит 19: в файле есть 19 подряд идущих символов, образующих невозрастающую цепочку (например, несколько Z, затем несколько Y, затем несколько X), а 20 таких подряд нет. Ответ: 19

Решение:

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

Нужны числа, у которых $F = n/p - p$ отлично от нуля и делится нацело на 13. Проверка $F \ne 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 % 13 == 0:
        print(n, f)
        found += 1

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

850022 425009
850048 425022
850053 283348
850074 425035
850099 7410
850100 425048

Ответ: 850022 425009 850048 425022 850053 283348 850074 425035 850099 7410 850100 425048

Решение:

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

Первую величину — наибольшее число мероприятий — даёт стандартный приём: отсортировать заявки по времени окончания. Но нам нужен ещё и максимальный перерыв между двумя последними мероприятиями, поэтому удобнее не жадный проход, а динамическое программирование по отсортированному списку: пусть dp[i] — наибольшее количество мероприятий в расписании, последним в котором стоит мероприятие i. Тогда dp[i] на единицу больше лучшего dp[j] среди заявок j, которые заканчиваются не позже начала i. Максимум по всем dp[i] и есть искомое количество $K$.

Теперь перерыв. Два последних мероприятия — это пара (j, i), в которой i завершает расписание длины $K$ (то есть dp[i] = K), а j предшествует ему в расписании длины $K-1$ (то есть dp[j] = K-1) и заканчивается не позже начала i. Перерыв равен разности «начало i минус конец j»; перебираем все такие пары и берём наибольшую разность.

f = open('26.txt')
n = int(f.readline())
a = []
for i in range(n):
    start, end = map(int, f.readline().split())
    a.append((end, start))      # сортировать будем по времени окончания
a.sort()

dp = [1] * n
for i in range(n):
    for j in range(i):
        if a[j][0] <= a[i][1] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1

k = max(dp)

gap = 0
for i in range(n):
    if dp[i] != k:
        continue
    for j in range(n):
        if dp[j] == k - 1 and a[j][0] <= a[i][1]:
            gap = max(gap, a[i][1] - a[j][0])

print(k, gap)

Проверим программу на типовом примере из условия: она выдаёт 3 и 20 — ровно то, что написано в задании. На данных из прилагаемого файла (990 заявок) получаем 32 мероприятия и перерыв 15 минут. Квадратичный перебор здесь допустим: при $N \le 1000$ это около миллиона проверок. Ответ: 32 15

Решение:

Из пункта с $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