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

Решение:

Степени вершин схемы: A — 3, B — 2, C — 2, D — 5, E — 2, F — 2, G — 2.

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

Степень 5 только у D и только у пункта 7, степень 3 только у A и только у пункта 3. Значит, D = 7 и A = 3.

Соседи A на схеме — это C, D и G. Соседи пункта 3 — это 1, 4 и 7; пункт 7 — это D, поэтому вершинам C и G отвечают пункты 1 и 4.

Соседи D на схеме — это A, C, G, B и E. Соседи пункта 7 — это 1, 2, 3, 4 и 6. Пункт 3 — это A, пункты 1 и 4 — это C и G, значит, вершинам B и E отвечают оставшиеся пункты 2 и 6. (Заодно F — это пункт 5, единственный не соединённый с 7.)

Записываем номера в порядке возрастания.

Ответ: 26

Решение:

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

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

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

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

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

from itertools import product


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


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


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

Ответ: wyzx

Решение:

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

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

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

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

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

Ответ: 429795

Решение:

Известно: А — 11, Б — 010, В — 0110, Г — 0111. Найдём свободные вершины дерева.

• В ветви 1: слово 11 — это А, свободна вершина 10.
• В ветви 0: свободна вершина 00; ветвь 01 занята целиком, потому что 010 — это Б, а 0110 и 0111 — это В и Г.

Свободны только две вершины — 00 и 10, а кодовые слова нужны четырём буквам Д, Е, Ж, З. Значит, каждую из вершин надо разбить надвое: 000, 001, 100, 101 — четыре слова по 3 знака, суммарно $3 \cdot 4 = 12$.

Короче не получится. Если оставить одно слово длины 2 (например, 00), то оставшаяся вершина 10 должна дать сразу три кодовых слова: 100, 1010, 1011, и сумма будет $2 + 3 + 4 + 4 = 13$ — больше.

Ответ: 12

Решение:

После первого шага получается число $M = N - (N \bmod 4)$, кратное 4, поэтому его двоичная запись оканчивается двумя нулями. Любое кратное четырём число может получиться на этом шаге (достаточно взять $N = M$), так что дальше можно перебирать сразу значения M.

Разберёмся с двумя приписываемыми разрядами. Пусть в двоичной записи числа M ровно s единиц, тогда сумма её цифр равна s.

• Первым приписывается разряд $s \bmod 2$.
• После этого сумма цифр становится равной $s + (s \bmod 2)$ — а это число всегда чётно, поэтому второй приписанный разряд всегда 0.

Итак, если единиц в записи M чётное число, справа приписывается 00, если нечётное — 10. Приписывание двух разрядов умножает число на 4, поэтому $R = 4M$ или $R = 4M + 2$, причём M кратно 4, то есть R кратно 16 либо даёт при делении на 16 остаток 2.

Перебираем M, кратные четырём, и ищем первый результат, больший 56:

• $M = 12 = 1100_2$: единиц две, число чётное, приписываем 00, получаем $110000_2 = 48$ — не больше 56;
• $M = 16 = 10000_2$: единица одна, число нечётное, приписываем 10, получаем $1000010_2 = 66$ — больше 56.

Между 48 и 66 других результатов нет, потому что каждое следующее значение M кратно 4 и увеличивает R сразу на 16. Значит, минимальное $R \gt 56$ равно 66. Проверка программой:

res = set()
for n in range(4, 1000):
    m = n - n % 4
    s = bin(m)[2:]
    s += str(sum(map(int, s)) % 2)
    s += str(sum(map(int, s)) % 2)
    res.add(int(s, 2))

print(min(r for r in res if r > 56))

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

Решение:

Направо 180 Вперёд 2 переводит Цаплю из $(0;0)$ в $(0;-2)$. Направо 90 направляет клюв вдоль отрицательного направления оси $Ox$, Вперёд 80 даёт $(-80;-2)$. Ещё одно Направо 90 — клюв вверх, Вперёд 2 даёт $(-80;0)$.

Команда Дуга 5, 5, 0 из точки $(x;y)$ описывает полуокружность радиуса 5 с центром $(x+5;\,y)$ по часовой стрелке: конечная точка — $(x+10;\,y)$, а дуга выпирает вверх. Восемь таких дуг ведут из $(-80;0)$ в $(0;0)$ и замыкают линию.

Итак, фигура — прямоугольник $[-80;0]\times[-2;0]$, на верхней стороне которого лежат восемь полукругов радиуса 5 с центрами $(-75;0)$, $(-65;0)$, $\dots$, $(-5;0)$. Верхняя сторона прямоугольника проходит внутри фигуры, а точки стыка соседних дуг $(-70;0)$, $(-60;0)$, $\dots$, $(-10;0)$ лежат на границе и не считаются.

C = [-75, -65, -55, -45, -35, -25, -15, -5]   # центры полуокружностей, r = 5
n = 0
for x in range(-86, 7):
    for y in range(-3, 7):
        pr = -80 <= x <= 0 and -2 <= y <= 0                          # прямоугольник
        pk = any(y >= 0 and (x - c) ** 2 + y * y <= 25 for c in C)   # полукруги
        gr = any(y >= 0 and (x - c) ** 2 + y * y == 25 for c in C) \
             or (pr and (x == -80 or x == 0 or y == -2))             # точки на линии
        if (pr or pk) and not gr:
            n += 1
print(n)

Программа печатает 391. Для контроля: площадь равна $80\cdot 2+8\cdot\dfrac{\pi\cdot 5^{2}}{2}=160+100\pi\approx 474{,}2$. Ответ: 391

Решение:

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

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

Файл должен поместиться в отведённую память: $40960 \cdot i \le 163840$, откуда $i \le \frac{163840}{40960} = 4$.

Наибольшее подходящее целое $i = 4$.

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

W, H = 128, 320
V = 20 * 1024 * 8  # отведённая память в битах
i = V // (W * H)   # максимальное целое число бит на пиксель
print(i, 2 ** i)   # 4 16

Ответ: 16

Решение:

Буквы в алфавитном порядке: А, В, О, П, Р. Слова четырёхбуквенные, поэтому со всякой фиксированной первой буквы начинается ровно $5^3 = 125$ слов.

Перед словами, начинающимися с П, идут все слова на А, В и О — это $3 \cdot 125 = 375$ слов. Значит, первое слово на букву П (это ПААА) имеет номер $375 + 1 = 376$.

То же самое через перевод в пятеричную систему (А=0, В=1, О=2, П=3, Р=4): ПААА → $3000_5 = 3 \cdot 125 = 375$, номер $375 + 1 = 376$.

from itertools import product

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

Ответ: 376

Решение:

Откроем файл. В строке 1 записаны часы (0:00 … 23:00), в столбце A — даты, а измерения занимают блок B2:Y92: 91 день по 24 замера, всего 2184 числа.

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

=СРЗНАЧ(B2:Y92)-МИН(B2:Y92)

В англоязычной версии редактора это =AVERAGE(B2:Y92)-MIN(B2:Y92). Получаем $10{,}4653\ldots - 0{,}3 = 10{,}1653\ldots$ Целая часть равна 10. То же самое на Python (для CSV-версии файла):

import csv

values = []
rows = list(csv.reader(open('data.csv', encoding='cp1251'), delimiter=';'))
for row in rows[1:]:                      # пропускаем строку с часами
    for cell in row[1:]:                  # пропускаем столбец с датой
        values.append(float(cell.replace(',', '.')))

print(sum(values) / len(values) - min(values))   # 10.1653...

В ответе записываем только целую часть. Ответ: 10

Решение:

Открываем файл и выделяем текст VII главы — фрагмент от заголовка «VII» до заголовка следующей главы.

Нужны вхождения сочетания букв, которые не являются отдельным словом, поэтому считаем в два приёма.

1. Ищем «шарик» без учёта регистра и с выключенным «Только слово целиком» — все вхождения сочетания букв: 41.
2. Тот же поиск с включённым «Только слово целиком»: отдельное слово «шарик»/«Шарик» в этой главе не встречается ни разу — 0 (пёс здесь уже стал Шариковым).

Итого внутри других слов: $41-0=41$. Это «Шариков» (31 раз), «Шарикова» (7), «Шарикову» (2), «Шариковский» (1).

Проверка программой (глава сохранена в текстовый файл):

import re

text = open('glava7.txt', encoding='utf-8').read()
vsego = len(re.findall('шарик', text)) + len(re.findall('Шарик', text))
otdelno = len(re.findall(r'\bшарик\b', text)) + len(re.findall(r'\bШарик\b', text))
print(vsego - otdelno)

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

Решение:

1. Мощность алфавита. Латинских букв 26, плюс 2025 символов специального алфавита: $26 + 2025 = 2051$ различный символ.

2. Бит на символ. Ищем минимальное $i$ с условием $2^{i} \ge 2051$. Здесь $2^{11} = 2048 \lt 2051$ — не хватает всего трёх символов, поэтому берём $2^{12} = 4096 \ge 2051$ и $i = 12$ бит. Это главная ловушка задачи.

3. Байт на идентификатор. В идентификаторе 704 символа: $704 \cdot 12 = 8448$ бит, а $8448 : 8 = 1056$ — делится нацело, значит, на идентификатор отводится ровно 1056 байт.

4. Общий объём. $3840 \cdot 1056 = 4\,055\,040$ байт, что составляет $4\,055\,040 : 1024 = 3960$ Кбайт.

import math

alfavit = 26 + 2025
bit = math.ceil(math.log2(alfavit))
bayt = math.ceil(704 * bit / 8)
print(3840 * bayt // 1024)

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

Решение:

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

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

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

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

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

Ответ: 141

Решение:

Маска 255.255.255.0 содержит 24 единицы, поэтому первые три байта адреса закреплены за сетью, а последний байт свободен: в сети $2^8 = 256$ адресов вида 134.22.153.x.

Двоичная запись фиксированной части такова: 134 = 10000110, 22 = 00010110, 153 = 10011001. В этой 24-битной цепочке трёх единиц подряд нет, и заканчивается она ровно одной единицей (…1001). Поэтому адрес подходит тогда и только тогда, когда три единицы подряд появляются в девятибитном «хвосте»: последняя единица третьего байта плюс восемь свободных битов. Перебор всех 256 значений последнего байта показывает, что без трёх единиц подряд обходятся 125 адресов, а подходящих $256 - 125 = 131$.

def ip(a, b, c, d):
    return ((a * 256 + b) * 256 + c) * 256 + d

base = ip(134, 22, 153, 0)
count = 0
for i in range(2 ** 8):          # последний байт пробегает 0..255
    if '111' in format(base + i, '032b'):
        count += 1
print(count)                     # 131

Ответ: 131

Решение:

В 27-ричной системе цифры принимают значения $0 \ldots 26$; нас интересуют цифры со значением от 10 до 26.

Все основания — степени тройки, а $27 = 3^3$. Переведём слагаемые:

• $2 \cdot 729^{2014} = 2 \cdot 3^{12084} = 2 \cdot 27^{4028}$;
• $2 \cdot 243^{2016} = 2 \cdot 3^{10080} = 2 \cdot 27^{3360}$;
• $2 \cdot 81^{2018} = 2 \cdot 3^{8072} = 2 \cdot 3^2 \cdot 3^{8070} = 18 \cdot 27^{2690}$;
• $2 \cdot 27^{2020}$ — уже готово;
• $2 \cdot 9^{2022} = 2 \cdot 3^{4044} = 2 \cdot 27^{1348}$;
• $2024 = 2 \cdot 27^2 + 20 \cdot 27 + 26$.

Итак, $N = 2 \cdot 27^{4028} + \left(2 \cdot 27^{3360} - 18 \cdot 27^{2690}\right) + \left(2 \cdot 27^{2020} - 2 \cdot 27^{1348} - 2024\right)$. Скобки не пересекаются по разрядам, поэтому их можно обрабатывать по отдельности.

Первая скобка. $2 \cdot 27^{3360} - 18 \cdot 27^{2690} = 27^{2690}\left(2 \cdot 27^{670} - 18\right)$. Число $2 \cdot 27^{670} - 18$ — это цифра 1, затем 669 цифр 26, затем цифра $27 - 18 = 9$.

Вторая скобка. $2 \cdot 27^{2020} - 2 \cdot 27^{1348} = 27^{1348}\left(2 \cdot 27^{672} - 2\right)$ — это цифра 1, затем 671 цифра 26 и цифра 25 в разряде 1348. Теперь вычитаем $2024 = (2,\ 20,\ 26)_{27}$: младшие разряды нулевые, поэтому заём уменьшает 25 до 24, разряды с 1347-го по 3-й (их 1345) становятся цифрами 26, а $27^3 - 2024 = 17659 = 24 \cdot 27^2 + 6 \cdot 27 + 1$ даёт младшие цифры 24, 6, 1.

Остальные цифры записи — старшая двойка, единицы и нули, они не превышают 9. Считаем «большие» цифры:

$669 + 671 + 1345 = 2685$ цифр 26, плюс две цифры 24, итого $2685 + 2 = 2687$.

n = 2*729**2014 + 2*243**2016 - 2*81**2018 + 2*27**2020 - 2*9**2022 - 2024
count = 0
while n:
    if n % 27 > 9:
        count += 1
    n //= 27
print(count)

Ответ: 2687

Решение:

Формула $\neg \text{ДЕЛ}(x, A) \rightarrow (\text{ДЕЛ}(x, 18) \rightarrow \neg \text{ДЕЛ}(x, 81))$ ложна только когда посылка истинна, а следствие ложно, то есть когда одновременно

• $x$ не делится на $A$;
• $x$ делится на 18 и $x$ делится на 81.

Чтобы таких $x$ не было, нужно, чтобы каждое число, кратное и 18, и 81, делилось на $A$.

Числа, кратные 18 и 81 одновременно, — это в точности кратные $\text{НОК}(18, 81)$. Разложим: $18 = 2 \cdot 3^{2}$, $81 = 3^{4}$, поэтому $\text{НОК}(18, 81) = 2 \cdot 3^{4} = 162$.

Подставив $x = 162$, получаем, что $A$ обязано быть делителем числа 162. Наибольший делитель — само число 162, и оно подходит: любое кратное 162 делится на 162.

best = 0
for A in range(1, 1000):
    if all(x % A == 0 for x in range(162, 100000, 162)):
        best = A
print(best)   # 162

Ответ: 162

Решение:

Значения $F(n)$ при $n$ около 2000 астрономически велики, поэтому выражение нужно упростить символьно, последовательно раскрывая соотношение $F(n) = n(n - 1) + F(n - 1) + F(n - 2)$.

Шаг 1. Раскроем $F(2024) = 2024 \cdot 2023 + F(2023) + F(2022)$ и подставим в исходное выражение — слагаемые $F(2022)$ сократятся:

$$F(2024) - F(2022) - 2F(2021) - F(2020) = 2024 \cdot 2023 + F(2023) - 2F(2021) - F(2020).$$

Шаг 2. Раскроем $F(2023) = 2023 \cdot 2022 + F(2022) + F(2021)$:

$$= 2024 \cdot 2023 + 2023 \cdot 2022 + F(2022) - F(2021) - F(2020).$$

Шаг 3. Раскроем $F(2022) = 2022 \cdot 2021 + F(2021) + F(2020)$ — оставшиеся значения функции сокращаются полностью:

$$= 2024 \cdot 2023 + 2023 \cdot 2022 + 2022 \cdot 2021.$$

Остаётся посчитать три произведения: $2024 \cdot 2023 = 4094552$, $2023 \cdot 2022 = 4090506$, $2022 \cdot 2021 = 4086462$.

Их сумма: $4094552 + 4090506 + 4086462 = 12271520$.

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

print(F[2024] - F[2022] - 2 * F[2021] - F[2020])   # 12271520
print(2024 * 2023 + 2023 * 2022 + 2022 * 2021)     # 12271520

Ответ: 12271520

Решение:

Считаем файл в список целых чисел и просмотрим все пары соседних элементов $(a_i,\ a_{i+1})$ — их на единицу меньше, чем самих чисел.

Последняя цифра числа — это остаток от деления его модуля на 10. Модуль здесь принципиален: в Python для отрицательных чисел остаток считается по-другому, например $-3119 \bmod 10 = 1$, хотя число оканчивается на 9.

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

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

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

print(count, best)   # 1020 17197

Программа находит 1020 подходящих пар, наименьшее произведение модулей равно 17197.Ответ: 1020 17197

Решение:

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

Пусть $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$. Вертикальные стены (нельзя идти вправо) стоят:

• между 4-м и 5-м столбцами — в строках 12–16;
• между 7-м и 8-м столбцами — в строках 4–19;
• между 12-м и 13-м столбцами — в строках 2–11;
• между 17-м и 18-м столбцами — в строках 11–18;
• между 19-м и 20-м столбцами — в строках 5–10.

Горизонтальные стены (нельзя идти вниз) стоят между 4-й и 5-й строками в столбцах 16–19, между 11-й и 12-й строками в столбцах 10–12, между 16-й и 17-й строками в столбцах 2–4, между 18-й и 19-й строками в столбцах 13–17 и между 19-й и 20-й строками в столбцах 5–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 == 3 and 15 <= j <= 18) or (i == 10 and 9 <= j <= 11) or
            (i == 15 and 1 <= j <= 3) or (i == 17 and 12 <= j <= 16) or
            (i == 18 and 4 <= j <= 6))

# стена справа от клетки (i, j)
def wall_right(i, j):
    return ((j == 11 and 1 <= i <= 10) or (j == 6 and 3 <= i <= 18) or
            (j == 18 and 4 <= i <= 9) or (j == 16 and 10 <= i <= 17) or
            (j == 3 and 11 <= i <= 15))

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]

best_max = 0
best_min = 10 ** 9
for i in range(N):
    for j in range(N):
        # клетка конечная, если справа и снизу от неё стена (или край поля)
        if (j == N - 1 or wall_right(i, j)) and (i == N - 1 or wall_down(i, j)):
            best_max = max(best_max, MX[i][j])
            best_min = min(best_min, MN[i][j])
print(best_max, best_min)

Конечных клеток оказывается пять; накопленные в них суммы такие:

Конечная клетка (строка, столбец)	Максимум	Минимум
(11, 12)	1431	870
(16, 4)	1173	820
(18, 17)	2252	1369
(19, 7)	1566	947
(20, 20)	2255	1577

Наибольшая из всех итоговых сумм — 2255 (правая нижняя клетка), наименьшая — 820 (клетка в 16-й строке и 4-м столбце).

Ответ: 2255 820

Решение:

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

Ходы: $s\to s+1$, $s\to s+5$ и $s\to 4s$. Игра заканчивается одним ходом, если $s+1\ge105$ ($s\ge104$), или $s+5\ge105$ ($s\ge100$), или $4s\ge105$ ($s\ge26{,}25$, для целого $s$ — $s\ge27$). Значит, из позиции $s\ge27$ ходящий выигрывает одним ходом.

Нужно $S\le26$ (Петя не выигрывает сразу) и одновременно $S+1\ge27$, $S+5\ge27$, $4S\ge27$, то есть $S\ge26$, $S\ge22$ и $S\ge7$. Единственное значение — $S=26$.

Проверка: из 26 Петя получает 27, 31 или 104 — все не меньше 27, поэтому Ваня выигрывает своим первым ходом. Сам Петя выиграть сразу не мог: $27\lt105$, $31\lt105$, $104\lt105$.

def win1(s):
    return s + 1 >= 105 or s + 5 >= 105 or 4 * s >= 105

for S in range(1, 105):
    if not win1(S) and win1(S + 1) and win1(S + 5) and win1(4 * S):
        print(S)

Ответ: 26

Решение:

Напомним игру: в куче $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

Решение:

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

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

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

П1. Нужно $S \lt 115$, но чтобы каждый ход попадал в В1. Самое сильное требование даёт ход «добавить один камень»: $S+1 \ge 115$, то есть $S \ge 114$. Значит, единственная позиция П1 — это $S = 114$.

В2. Это позиции, из которых есть ход ровно в $114$: $S = 57$, $S = 113$.

Теперь про Ваню. Ваня выигрывает первым или вторым своим ходом при любой игре Пети, если каждый ход Пети приводит в позицию из В1 или В2 (и не заканчивает игру). Гарантированной победы первым ходом у Вани нет, если хотя бы один ход Пети ведёт не в В1, а в В2. Значит, нужно минимальное $S$, у которого все ходы попадают в $\text{В1} \cup \text{В2}$, но не все — в В1.

При $S = 112$ ходы Пети дают $113$ (В2), $224$ (В1) — условие выполнено. Меньших значений нет: при $S \lt 112$ ход «добавить камень» должен попасть в $\text{В1} \cup \text{В2} = \{57;\ 113\} \cup [115;\ 228]$, что оставляет только $S = 56$; но тогда второй ход даёт $2S = 112$ — позицию, которая не принадлежит ни В1, ни В2.

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

N = 229

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

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

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

Ответ: 112

Решение:

В файле 14 процессов с идентификаторами 101–114. Зависимости распадаются на две не связанные между собой группы:

• 101 и 102 → 103 → 104 и 105; 104 → 106; 105 и 106 → 107 → 108 (длительности 4, 3, 1, 5, 7, 3, 1, 2 мс);
• 109 → 111 и 114; 111 и 114 → 113; независимый 110 → 112 (длительности 8, 16, 14, 14, 6, 5 мс).

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

Сколько процессов вообще могут работать одновременно? Одновременно могут выполняться только попарно независимые процессы. В первой группе любые три процесса обязательно связаны цепочкой зависимостей, независимых пар всего три (104 и 105, 105 и 106, 101 и 102) — значит, оттуда одновременно работают не более двух процессов. Во второй группе 109 предшествует 111 и 114, а 113 следует за ними, из пары 110 и 112 второй зависит от первого; максимум независимых процессов здесь — три (например, 111, 114 и 110). Итого одновременно могут идти не более $2 + 3 = 5$ процессов, то есть пятёрка процессов — это ровно две «ленты» первой группы и три «ленты» второй.

Вторая группа три непрерывные ленты держит долго: сразу после 109 (8 мс) параллельно запускаются 111 (16 мс) и 114 (14 мс), а третью ленту даёт цепочка 110 → 112 ($6 + 5 = 11$ мс). Ограничения нет: $\min(16, 14, 11) = 11$ мс.

Первая группа — узкое место. После 103 параллельно могут идти только 104 и 105. Первая лента — цепочка 104 → 106 ($5 + 3 = 8$ мс), вторая лента — процесс 105 (7 мс). Продлить вторую ленту нечем: следующий за 105 процесс 107 требует ещё и завершения 106, а 106 заканчивается на 1 мс позже, чем 105, — на стыке лента простаивает. Поэтому две ленты первой группы заняты одновременно не дольше 7 мс.

Итог: $\min(11, 7) = 7$ мс. Такое расписание действительно существует (общее время выполнения всей совокупности при этом остаётся минимальным — 38 мс):

ID	Время, мс	Зависит от	Старт, мс	Финиш, мс
101	4	—	0	4
102	3	—	0	3
103	1	101; 102	4	5
109	8	—	0	8
104	5	103	8	13
105	7	103	8	15
110	6	—	8	14
111	16	109	8	24
114	14	109	8	22
106	3	104	13	16
112	5	110	14	19
107	1	105; 106	16	17
108	2	107	17	19
113	14	111; 114	24	38

На отрезке с 8-й по 15-ю миллисекунду одновременно работают ровно пять процессов: сначала 104, 105, 110, 111, 114; с 13-й мс вместо завершившегося 104 включается 106; с 14-й мс вместо 110 — процесс 112. В момент 15 мс заканчивается 105, и остаётся четыре процесса. Длина отрезка — $15 - 8 = 7$ мс. Проверка:

sched = {101: (0, 4),   102: (0, 3),   103: (4, 5),   109: (0, 8),
         104: (8, 13),  105: (8, 15),  110: (8, 14),
         111: (8, 24),  114: (8, 22),
         106: (13, 16), 112: (14, 19), 107: (16, 17),
         108: (17, 19), 113: (24, 38)}

best = cur = 0
for t in range(38):                       # t - миллисекунда [t, t+1)
    k = sum(1 for s, e in sched.values() if s <= t < e)
    cur = cur + 1 if k >= 5 else 0
    best = max(best, cur)
print(best)

Ответ: 7

Решение:

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

Участок $2 \to 6$ даёт три программы: АА (2 → 4 → 6), ВА (2 → 4 → 6) и С (2 → 6). Участок $6 \to 28$ удобно посчитать той же рекурсией: обозначим через $R(a, b)$ число программ, переводящих $a$ в $b$; тогда $R(b, b) = 1$, $R(a, b) = 0$ при $a \gt b$ и $R(a, b) = R(a + 2, b) + R(2a, b) + R(3a, b)$ в остальных случаях. Получаем $R(6, 28) = 10$.

Итого $3 \cdot 10 = 30$ программ. Для сравнения, всего программ из 2 в 28 без условия про шестёрку было бы 48, так что требование пройти через 6 действительно отсекает часть вариантов.

from functools import lru_cache

@lru_cache(None)
def R(a, b):
    if a > b:
        return 0
    if a == b:
        return 1
    return R(a + 2, b) + R(2 * a, b) + R(3 * a, b)

print(R(2, 6) * R(6, 28))   # 3 * 10 = 30

Ответ: 30

Решение:

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

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

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

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

print(mx)

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

Решение:

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

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

from fnmatch import fnmatch

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

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

Число	Частное от деления на 5171
11908813	2303
71995833	13923
81975863	15853
91955893	17783

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

Решение:

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

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

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

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

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)

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

3105 75

Ответ: 3105 75

Решение:

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