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

Решение:

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

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

Единственная вершина степени 4 — это Г, единственный такой пункт таблицы — 5. Значит, Г = 5, и его соседи 3, 4, 6, 7 отвечают вершинам А, Д, Е, К.

Различим их по соседям степени 2 (на схеме это Б и В, в таблице — пункты 1 и 2):

• А соединена сразу с двумя вершинами степени 2 (с Б и с В). В таблице так устроен только пункт 3 (соседи 1, 2 и 5), поэтому А = 3.
• Д соединена с Б, а Е — с В, то есть у каждой из них ровно один сосед степени 2. В таблице это пункты 6 (соседи 1, 4, 5) и 7 (соседи 2, 4, 5).
• У К соседей степени 2 нет вовсе; в таблице это пункт 4 (соседи 5, 6, 7).

Итак, Д и Е — это пункты 6 и 7 (в каком именно порядке, для ответа неважно). Дороги из Г в них: 5—6 = 19 и 5—7 = 20.

Сумма: 19 + 20 = 39.

Ответ: 39

Решение:

Функция $F = ( ( x \rightarrow y ) \rightarrow w ) \lor ( z \rightarrow ( y \land w ) )$ зависит от четырёх переменных, поэтому её полная таблица истинности содержит $2^4 = 16$ строк, а расставить переменные w, x, y, z по четырём столбцам можно $4! = 24$ способами.

Найдём все наборы, на которых $F = 0$. Таких наборов всего три (значения записаны в «алфавитном» порядке $w,\ x,\ y,\ z$):

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

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

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

Всё это удобно поручить программе. В Python импликация $a \rightarrow b$ — это a <= b.

from itertools import product, permutations

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

# фрагмент таблицы: '.' — незаполненная клетка, второе число — значение F
frag = [('10..', 0),
        ('..1.', 0),
        ('.10.', 0)]

def fits(mask, vals):
    return all(m == '.' or int(m) == v for m, v in zip(mask, vals))

for p in permutations('wxyz'):
    # для каждой строки фрагмента — все её допустимые дополнения
    variants = []
    for mask, f in frag:
        variants.append([vals for vals in product((0, 1), repeat=4)
                         if fits(mask, vals) and F(**dict(zip(p, vals))) == f])
    # строки фрагмента должны быть попарно различны
    for lines in product(*variants):
        if len(set(lines)) == len(lines):
            print(''.join(p))
            break

Программа печатает единственную расстановку — zyxw. Проверим её вручную. Столбцы идут в порядке $z,\ y,\ x,\ w$; восстановим пустые клетки (восстановленные значения выделены курсивом):

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

Все строки различны, известные клетки совпадают с фрагментом, и функция на них принимает требуемые значения — расстановка найдена верно.

Ответ: zyxw

Решение:

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

Шаг 1. В таблице «Ткани» включаем фильтр: Цвет = «красный», Сырьё = «хлопок», Плотность $\ge 195$ г/м². Условию удовлетворяют три ткани — бархат (405 г/м²), вельвет (410 г/м²) и джинса (420 г/м²). Выписываем их ID ткани.

Шаг 2. В таблице «Продукция» отбираем все модели, в наименовании которых есть слово «платье» (платье прямое, платье миди, платье-халат, платье-сарафан и т. д.). Категория потребителей в условии не ограничена, поэтому берём и детские, и женские модели.

Шаг 3. В таблице «Готовый товар» функцией ВПР добавляем к каждой строке цвет, сырьё и плотность ткани (по «ID ткани») и наименование модели (по «ID товара»), а затем оставляем строки, у которых ткань из шага 1 и наименование из шага 2. Таких строк 27.

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

Ответ: 1453717

Решение:

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

• В ветви 0: слово 01 — это А, свободна вершина 00 (2 знака).
• В ветви 1: слово 11 — это Б; в ветви 10 свободна вершина 100 (3 знака), а в ветви 101 слово 1010 — это В, свободна вершина 1011 (4 знака).

Свободных мест три — 00, 100 и 1011, — а кодовые слова нужны четырём буквам Г, Д, Е, Ж. Одну из вершин придётся разбить надвое, и выгоднее разбивать самую короткую: 00 превращается в 000 и 001.

Получаем набор 000, 001, 100, 1011 с суммарной длиной $3 + 3 + 3 + 4 = 13$.

Другие варианты хуже: разбиение вершины 100 даёт 00, 1000, 1001, 1011 — сумма $2 + 4 + 4 + 4 = 14$; разбиение вершины 1011 даёт 00, 100, 10110, 10111 — сумма $2 + 3 + 5 + 5 = 15$.

Ответ: 13

Решение:

Автомат приписывает друг к другу произведение цифр P и сумму цифр S, причём первым записывается большее из этих чисел. Значит, строку 33621 надо разрезать на две части так, чтобы первая часть была не меньше второй.

Сумма трёх цифр не превосходит $9 + 9 + 9 = 27$, поэтому часть, отвечающая за сумму, состоит не более чем из двух цифр. Разбираем варианты разреза:

• «3» и «3621», «33» и «621» — не годятся: первое число меньше второго, порядок невозрастания нарушен;
• «3362» и «1» — тогда одно из чисел равно 1. Сумма цифр трёхзначного числа равна 1 только у числа 100, но произведение его цифр равно 0, а не 3362. Произведение цифр равно 1 только у числа 111, но сумма его цифр равна 3, а не 3362. Не подходит;
• «336» и «21» — подходит: $336 \ge 21$, а суммой цифр число 336 быть не может, поэтому $P = 336$ и $S = 21$.

Ищем цифры $a, b, c$, для которых $a \cdot b \cdot c = 336$ и $a + b + c = 21$. Разложим на множители: $336 = 2^4 \cdot 3 \cdot 7$. Множитель 7 не может «разойтись» между цифрами, поэтому одна из цифр равна 7, а две другие дают в произведении $336 : 7 = 48$. Единственное разложение числа 48 на два множителя-цифры — это $6 \cdot 8$. Проверяем сумму: $6 + 7 + 8 = 21$ — верно.

Значит, цифры искомого числа — 6, 7 и 8; наибольшее число из этих цифр — 876. Проверка программой:

for n in range(999, 99, -1):
    a, b, c = int(str(n)[0]), int(str(n)[1]), int(str(n)[2])
    p, s = a * b * c, a + b + c
    x, y = max(p, s), min(p, s)
    if str(x) + str(y) == '33621':
        print(n)
        break

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

Решение:

Поворот на $120^\circ$ — это внешний угол правильного треугольника, поэтому пара команд «Вперёд 10 Направо 120», выполненная три раза, возвращает Черепаху в исходную точку с исходным направлением. Семь повторений — это два полных обхода плюс ещё одна сторона поверх уже нарисованной, так что линия на плоскости — обычный равносторонний треугольник со стороной 10.

Найдём его вершины. Старт в точке $(0;0)$, голова смотрит вверх, поэтому первая сторона идёт по оси ординат в точку $(0;10)$. Дальше поворот и движение приводят в точку $(5\sqrt3;\ 5)$, а третья сторона возвращает в начало координат. Итак, вершины: $(0;0)$, $(0;10)$ и $(5\sqrt3;\ 5) \approx (8{,}66;\ 5)$.

Левая сторона лежит на оси ординат, поэтому у внутренних точек $x \ge 1$, а из $5\sqrt3 \approx 8{,}66$ следует $x \le 8$. Нижняя сторона задаётся прямой $y = x/\sqrt3$, верхняя — прямой $y = 10 - x/\sqrt3$. Для каждого $x$ считаем целые $y$ строго между этими границами:

x	1	2	3	4	5	6	7	8
точек	9	7	7	5	5	3	1	1

В сумме $9 + 7 + 7 + 5 + 5 + 3 + 1 + 1 = 38$. Для контроля: площадь треугольника равна $\frac{\sqrt3}{4} \cdot 10^2 \approx 43{,}3$, что согласуется с полученным числом внутренних узлов.

from math import sqrt, ceil, floor

s = 10
total = 0
for x in range(1, floor(s * sqrt(3) / 2) + 1):
    lo, hi = x / sqrt(3), s - x / sqrt(3)
    total += len([y for y in range(ceil(lo), floor(hi) + 1) if lo < y < hi])
print(total)   # 38

Ответ: 38

Решение:

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

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

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

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

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

Ответ: 195

Решение:

Выпишем используемые буквы в алфавитном порядке: А, П, Р, С, У. Нужно последнее подходящее слово списка, то есть самое «старшее» по алфавиту слово, в котором буква У встречается не более одного раза и нет двух букв А подряд.

Строим его жадно, слева направо, беря на каждом месте максимально возможную букву. На первое место ставим У — это допустимо, ведь одна У разрешена. После этого У использовать уже нельзя, и старшая из оставшихся букв — С. Букв С подряд может стоять сколько угодно (ограничение касается только буквы А), поэтому остальные четыре места заполняем буквой С. Получаем слово УСССС: в нём одна У и нет сочетания АА.

Теперь найдём его номер. Занумеруем буквы по алфавиту: А — 0, П — 1, Р — 2, С — 3, У — 4. Тогда пятибуквенное слово превращается в пятизначное число в пятеричной системе счисления, а номер слова в списке на единицу больше значения этого числа (первому слову ААААА соответствует число 0).

Слову УСССС отвечает набор цифр 4, 3, 3, 3, 3:

$$4 \cdot 5^4 + 3 \cdot 5^3 + 3 \cdot 5^2 + 3 \cdot 5 + 3 = 2500 + 375 + 75 + 15 + 3 = 2968.$$

Значит, слово УСССС стоит под номером $2968 + 1 = 2969$.

from itertools import product

alpha = 'АПРСУ'          # буквы уже в алфавитном порядке
answer = 0
for i, w in enumerate(product(alpha, repeat=5), 1):
    s = ''.join(w)
    if s.count('У') <= 1 and 'АА' not in s:
        answer = i        # запоминаем последнее подходящее слово
print(answer)   # 2969

Ответ: 2969

Решение:

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

В любую свободную ячейку (например, AA1) записываем одну формулу:

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

Функция МАКС находит наибольшую температуру за три месяца, СРЗНАЧ — среднее арифметическое всех значений. В англоязычной версии редактора формула выглядит как =MAX(B2:Y92)-AVERAGE(B2:Y92). Максимум равен $38{,}0$, среднее — $23{,}7211\ldots$, их разность $38{,}0 - 23{,}7211\ldots = 14{,}2788\ldots$ Целая часть полученного числа равна 14. Ответ: 14

Решение:

Текст дан в пяти форматах — открываем любой из них в текстовом редакторе. Считать нужно только по главе III, поэтому выделяем фрагмент от заголовка «III» до заголовка «IV» (удобно скопировать главу в новый документ).

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

1. Ищем «по» с выключенным «Учитывать регистр» и выключенным «Только слово целиком» — все вхождения сочетания букв в главе: 114.
2. Тот же поиск с включённым «Только слово целиком» — редактор насчитает 11 совпадений: $114-11=103$.

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

$103 + 3 = 106$.

(Слова «почему-то» и «пошло-игривым» дополнительно учитывать не нужно: в них «по» и так стоит внутри части слова, редактор их отдельным словом не посчитал.)

Надёжнее посчитать программой — здесь дефис явно объявлен частью слова:

import re

text = open('glava3.txt', encoding='utf-8').read()
bukvy = '[0-9A-Za-zА-Яа-яЁё-]'
vsego = len(re.findall('[пП]о', text))
otdelno = len(re.findall('(?<!' + bukvy + ')[пП]о(?!' + bukvy + ')', text))
print(vsego - otdelno)

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

Решение:

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

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

Все 1536 идентификаторов занимают $1536 \cdot 414 = 635904$ байта, то есть $635904 : 1024 = 621$ Кбайт.

import math

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

Ответ: 621

Решение:

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

Приоритет у замены (2222, 11): она выполняется, пока в строке есть четыре подряд идущие двойки, и только если их нет — работает замена (1111, 22). Вначале двоек нет, поэтому четвёрки единиц превращаются в пары двоек, дальше замены чередуются, и результат проще получить моделированием.

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

s = "1" * 91
while "2222" in s or "1111" in s:
    if "2222" in s:
        s = zamenit(s, "2222", "11")
    else:
        s = zamenit(s, "1111", "22")
print(s)   # 22111

Проверка на коротких строках: начиная с $k=8$ единиц результат периодичен с периодом 6, и при $k = 13,\ 19,\ 25,\ \ldots$ получается 22111. Здесь $91 = 13 + 6 \cdot 13$, что согласуется с ответом программы. Ответ: 22111

Решение:

Маска 255.255.255.128 содержит 25 единиц и 7 нулей, поэтому первые 25 битов адреса закреплены за сетью и совпадают с адресом 193.221.145.0, а последние 7 битов свободны — всего в сети $2^7 = 128$ адресов.

В IP-адресе 32 бита, значит «единиц столько же, сколько нулей» означает ровно 16 единиц. Посчитаем единицы в неизменяемой части: 193 = 11000001 даёт 3 единицы, 221 = 11011101 даёт 6, 145 = 10010001 даёт 3, а старший (25-й) бит последнего байта равен нулю. Итого в фиксированной части $3 + 6 + 3 = 12$ единиц, поэтому среди 7 свободных битов должно быть ровно $16 - 12 = 4$ единицы. Число способов выбрать их равно $C_7^4 = 35$.

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

base = ip(193, 221, 145, 0)
count = 0
for i in range(2 ** 7):          # 7 свободных битов узла
    s = format(base + i, '032b')
    if s.count('1') == s.count('0'):
        count += 1
print(count)                     # 35

Ответ: 35

Решение:

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

$123x5_{15} = 1 \cdot 15^4 + 2 \cdot 15^3 + 3 \cdot 15^2 + x \cdot 15 + 5$,

$1x233_{15} = 1 \cdot 15^4 + x \cdot 15^3 + 2 \cdot 15^2 + 3 \cdot 15 + 3$.

Сумма: $S = 2 \cdot 15^4 + (x + 2) \cdot 15^3 + 5 \cdot 15^2 + (x + 3) \cdot 15 + 8$.

Заметим, что $15 \equiv 1 \pmod{14}$, поэтому и все степени пятнадцати дают остаток 1. Тогда сумма сравнима с суммой своих коэффициентов:

$S \equiv 2 + (x + 2) + 5 + (x + 3) + 8 = 2x + 20 \pmod{14}$.

Условие $2x + 20 \equiv 0 \pmod{14}$ равносильно $x + 10 \equiv 0 \pmod 7$, то есть $x \equiv 4 \pmod 7$. В алфавите 15-ричной системы (цифры $0 \ldots 14$) подходят $x = 4$ и $x = 11$; наименьшее — $x = 4$.

При $x = 4$: $S = 2 \cdot 50625 + 6 \cdot 3375 + 5 \cdot 225 + 7 \cdot 15 + 8 = 122738$, и $122738 : 14 = 8767$.

for x in range(15):
    a = 15**4 + 2*15**3 + 3*15**2 + x*15 + 5
    b = 15**4 + x*15**3 + 2*15**2 + 3*15 + 3
    if (a + b) % 14 == 0:
        print(x, (a + b) // 14)

Ответ: 8767

Решение:

Выражение $\neg(x \in A) \rightarrow ((x \in B) \equiv (x \in C))$ ложно только тогда, когда $x \notin A$, а принадлежности отрезкам $B$ и $C$ различны. Поэтому отрезок $A$ должен накрывать все точки, где $B$ и $C$ «расходятся», — их симметрическую разность.

Для $B = [4; 18]$ и $C = [12; 40]$:

• в $B$, но не в $C$: $4 \le x \lt 12$;
• в $C$, но не в $B$: $18 \lt x \le 40$.

Крайние точки этого множества — 4 слева и 40 справа, значит отрезок $A$ обязан содержать весь промежуток $[4; 40]$.

Наименьший подходящий отрезок — $A = [4; 40]$, его длина равна $40 - 4 = 36$.

def ok(a, b, step=0.5):
    for i in range(0, 200):
        x = i * step
        A = a <= x <= b
        B = 4 <= x <= 18
        C = 12 <= x <= 40
        if not (A or (B == C)):
            return False
    return True

print(ok(4, 40))      # True
print(ok(4.5, 40))    # False

Ответ: 36

Решение:

Правило $F(n) = n \cdot F(n-1)$ при $F(1) = 1$ задаёт факториал, но вычислять его не нужно: достаточно трижды раскрыть числитель.

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

Поэтому $\dfrac{F(2023)}{F(2020)} = 2023 \cdot 2022 \cdot 2021 = 4090506 \cdot 2021 = 8266912626$.

print(2023 * 2022 * 2021)   # 8266912626

Ответ: 8266912626

Решение:

Загружаем числа из файла в список и перебираем все пары соседних элементов.

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

Условие пары: обе последние цифры нечётные и разные. Считаем количество таких пар и минимальное произведение модулей их элементов.

a = [int(s) for s in open('44124_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)   # 864 4683

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

Решение:

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

Пусть $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

Решение:

Позиция игры — пара чисел $(a,b)$. За один ход можно прибавить 2 камня к одной из куч или увеличить одну из куч в три раза. Игра заканчивается, когда суммарное количество камней достигает 136.

Из позиции $(a,b)$ ходящий заканчивает игру, если $a+b+2\ge136$, или $3a+b\ge136$, или $a+3b\ge136$. Так как $3a+b=(a+b)+2a$ и $a+3b=(a+b)+2b$, условие равносильно $(a+b)+\max(2a,2b,2)\ge136$: выгоднее всего утроить бо́льшую кучу. Нужно наименьшее $S$, при котором у Пети есть ход, не заканчивающий игру, после которого Ваня выигрывает сразу.

Из начальной позиции $(2,S)$ Петя может получить позиции $(4,S)$, $(6,S)$, $(2,S+2)$ и $(2,3S)$. Самая опасная — $(2,3S)$: Ваня утраивает вторую кучу ещё раз и получает сумму $2+9S$. Условие $2+9S\ge136$ даёт $9S\ge134$, $S\ge14\tfrac89$, то есть $S\ge15$.

Другие ходы требуют большего $S$: из $(2,S+2)$ Ваня получает сумму $3S+8\ge136$, откуда $S\ge43$; из $(6,S)$ — $6+3S\ge136$, $S\ge44$; из $(4,S)$ — $4+3S\ge136$, $S\ge44$.

Проверим $S=15$. Петя ходит $(2,15)\to(2,45)$: сумма 47, игра продолжается. Ваня утраивает вторую кучу: $(2,135)$, сумма $137\ge136$ — победа первым ходом. Сам Петя закончить игру не мог: $2+15+2\cdot15=47\lt136$. При $S\lt15$ такая ситуация невозможна.

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

def win1(p):
    return any(x + y >= 136 for x, y in moves(p))

for S in range(1, 133):
    if any(x + y < 136 and win1((x, y)) for x, y in moves((2, S))):
        print(S)
        break

Ответ: 15

Решение:

Напомним условия игры: перед игроками две кучи камней, за ход можно добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в одной из куч вдвое; игра заканчивается, когда суммарное количество камней в кучах становится не менее $59$. Начальная позиция — $(5,\ S)$, первым ходит Петя.

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

$S = 24$. Сразу Петя выиграть не может ($5 + 2\cdot 24 = 53 \lt 59$). Петя удваивает первую кучу — получается позиция $(10,\ 24)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(11,\ 24)$ — Петя удваивает вторую кучу: $11 + 48 = 59$;
• $(10,\ 25)$ — Петя удваивает вторую кучу: $10 + 50 = 60$;
• $(20,\ 24)$ — Петя удваивает вторую кучу: $20 + 48 = 68$;
• $(10,\ 48)$ — Петя добавляет камень: $10 + 49 = 59$.

$S = 26$. Сразу Петя выиграть не может ($5 + 2\cdot 26 = 57 \lt 59$). Петя добавляет камень в первую кучу — получается позиция $(6,\ 26)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(7,\ 26)$ — Петя удваивает вторую кучу: $7 + 52 = 59$;
• $(6,\ 27)$ — Петя удваивает вторую кучу: $6 + 54 = 60$;
• $(12,\ 26)$ — Петя удваивает вторую кучу: $12 + 52 = 64$;
• $(6,\ 52)$ — Петя добавляет камень: $6 + 53 = 59$.

Полный перебор удобнее доверить программе:

N = 59

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

def over(p):                 # игра закончена
    return p[0] + p[1] >= N

def win1(p):                 # В1: выигрыш своим первым ходом
    return any(over(q) for q in moves(p))

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

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

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

Ответ: 24 26

Решение:

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

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

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

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

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

• $(8;\ 30)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(16;\ 30)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(17;\ 30)$ — в $(17;\ 60)$; из $(32;\ 30)$ — в $(64;\ 30)$; из $(16;\ 31)$ — в $(16;\ 62)$; из $(16;\ 60)$ — в $(17;\ 60)$);
• $(14;\ 30)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(14;\ 31)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(15;\ 31)$ — в $(15;\ 62)$; из $(28;\ 31)$ — в $(56;\ 31)$; из $(14;\ 32)$ — в $(14;\ 64)$; из $(14;\ 62)$ — в $(15;\ 62)$);
• $(7;\ 31)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(14;\ 31)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(15;\ 31)$ — в $(15;\ 62)$; из $(28;\ 31)$ — в $(56;\ 31)$; из $(14;\ 32)$ — в $(14;\ 64)$; из $(14;\ 62)$ — в $(15;\ 62)$);
• $(7;\ 60)$ — Ваня выигрывает сразу: одним ходом он получает $(7;\ 120)$, а это уже не меньше 77.

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

Ответ: 30

Решение:

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

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

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

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

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

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

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

Решение:

Обозначим через $R(x)$ количество программ, переводящих число $x$ в заданное конечное число. Из $x$ исполнитель может перейти либо в $x+1$ (команда 1), либо в $2x$ (команда 2), поэтому $$R(x)=R(x+1)+R(2x),$$ причём $R(\text{конечного числа})=1$ (пустая программа), а если $x$ уже больше конечного числа, то $R(x)=0$ — числа только растут.

Траектория обязана содержать 10, а 10 лежит между 1 и 20, поэтому каждая подходящая программа однозначно распадается на две независимые части: сначала $1\to 10$, потом $10\to 20$. По правилу произведения общее количество равно произведению количеств.

1) Из 1 в 10. Считаем $R$ от 10 вниз к 1 (удвоение из $x\ge 6$ сразу перескакивает через 10, поэтому там остаётся только «прибавить 1»):

$x$	10	9	8	7	6	5	4	3	2	1
$R(x)$	1	1	1	1	1	2	3	4	7	14

Например, $R(5)=R(6)+R(10)=1+1=2$, $R(2)=R(3)+R(4)=4+3=7$, $R(1)=R(2)+R(2)=14$. Итого 14 программ.

2) Из 10 в 20. Для любого $x\ge 11$ удвоение даёт больше 20, значит $R(x)=R(x+1)=1$ для всех $x=11,\dots,20$. А из 10 можно и прибавлять единицы, и сразу удвоить: $R(10)=R(11)+R(20)=1+1=2$.

Итого $14\cdot 2=28$.

from functools import lru_cache

def count(start, finish):
    @lru_cache(None)
    def R(x):
        if x > finish:
            return 0
        if x == finish:
            return 1
        return R(x + 1) + R(2 * x)
    return R(start)

print(count(1, 10) * count(10, 20))

Ответ: 28

Решение:

Условие «ни одна буква не стоит рядом с буквой, а цифра — с цифрой» означает, что на искомом участке буквы и цифры строго чередуются: любые два соседних символа должны быть разного типа. Конкретные значения (Q, R, W или 1, 2, 4) роли не играют — важен только тип символа.

Значит, достаточно одного прохода: если тип очередного символа отличается от типа предыдущего, серия продолжается, иначе начинается новая серия длины 1. Тип удобно определять методом isdigit().

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

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

print(mx)

Программа выводит 17 — это длина самого длинного чередующегося участка «буква-цифра-буква-…». Ответ: 17

Решение:

У целого числа $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

Решение:

Сортируем диаметры по убыванию и жадно строим башню, начиная с самого большого коржа: очередной корж кладём, если его диаметр хотя бы на 4 меньше диаметра последнего положенного. Обратите внимание: пример в условии разобран для порога 3, но в самом задании требуется разница не менее 4 единиц.

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

f = open('26.txt')
n = int(f.readline())
a = sorted((int(x) for x in f), reverse=True)

cnt = 0
last = None
for x in a:
    if last is None or x <= last - 4:
        cnt += 1
        last = x
print(cnt, last)

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

2172 50

Ответ: 2172 50

Решение:

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

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

Файл A: сумма больших чисел равна $650905$; она даёт остаток $13$ при делении на 33, то есть уже не делится на 33 — уменьшать ничего не нужно, ответ $650905$.Файл B: сумма больших чисел равна $666122358$ и делится на 33. Наименьшая ненулевая разность внутри пары, не кратная 33, равна $1622$, поэтому ответ $666122358 - 1622 = 666120736$.Ответ: 650905 666120736