Вариант 9 · Сентябрь 2026

Решение:

Функция $F = \neg(x \rightarrow z) \lor (y \equiv w) \lor y$ — дизъюнкция трёх слагаемых, и во всех трёх строках $F = 0$. Значит в каждой строке каждое слагаемое равно нулю:

• $y = 0$;
• $(y \equiv w) = 0$; при $y = 0$ это даёт $w = 1$;
• $\neg(x \rightarrow z) = 0$, то есть $x \rightarrow z = 1$: $x = 0$ или $z = 1$.

Столбец $w$. В нём во всех строках стоит 1. Первый столбец отпадает (в третьей строке там 0), второй столбец отпадает (в первой строке там 0), третий столбец отпадает (во второй строке там 0). Значит $w$ — четвёртый столбец.

Столбец $y$. В нём во всех строках стоит 0. Первый столбец отпадает (в первой строке там 1), второй столбец отпадает (во второй строке там 1), четвёртый занят переменной $w$. Значит $y$ — третий столбец; во второй строке там действительно 0.

Столбцы $x$ и $z$. Им остаются первый и второй столбцы, а в первой строке в них стоят 1 и 0. Если бы $x$ был первым столбцом ($x = 1$), а $z$ — вторым ($z = 0$), то $x \rightarrow z = 0$ и $F = 1$, что противоречит таблице. Значит $x$ — второй столбец, а $z$ — первый.

Проверка: первая строка — 1 0 0 1; вторая строка (_ 1 0 _) даёт $x = 1$, тогда $z = 1$, то есть 1 1 0 1; третья строка (0 _ _ _) даёт $z = 0$, тогда $x = 0$, то есть 0 0 0 1. Все три строки различны, во всех $F = 0$.

Итак, столбцы слева направо: $z$, $x$, $y$, $w$.

Ответ: zxyw

Решение:

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

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

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

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

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

Ответ: 2750

Решение:

Известно: Д — 1, Я — 011.

Кодовое слово Д — 1 занимает всю ветвь, начинающуюся с единицы, поэтому буквы И, К и Л кодируются словами, начинающимися с 0. В этой ветви слово 011 занято буквой Я, свободны вершины 00 и 010. Свободных мест два, а букв три, поэтому одну вершину придётся разбить надвое.

В слове ИДИЛЛИЯ буква И встречается 3 раза, Л — 2 раза, Д — 1 раз, Я — 1 раз, а буква К не встречается ни разу, значит именно ей выгодно отдать длинное слово.

Самую короткую свободную вершину 00 отдаём самой частой букве И, а вершину 010 разбиваем на 0100 и 0101 для букв Л и К:

Суммарно $6 + 1 + 8 + 3 = 18$ двоичных знаков.

Если разбить вместо этого вершину 00 (И — 000, К — 001, Л — 010), получится $3 \cdot 3 + 1 + 3 \cdot 2 + 3 = 19$ знаков — хуже.

Ответ: 18

Решение:

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

Решение:

Внутренний цикл Повтори 2 [Вперёд 10 Направо 90 Вперёд 10 Направо 90] рисует квадрат $10\times 10$ и возвращает Черепаху в исходную точку с исходным направлением.

Затем с поднятым хвостом Вперёд 10 Направо 90 Вперёд 5 Налево 90 сдвигает её на $(+5;+10)$, голова снова вдоль оси $Oy$.

Значит рисуются три квадрата: $[0;10]\times[0;10]$, $[5;15]\times[10;20]$ и $[10;20]\times[20;30]$.

Соседние квадраты не накладываются, а лишь примыкают друг к другу: первый и второй — по отрезку $y=10$, $5\le x\le 10$; второй и третий — по отрезку $y=20$, $10\le x\le 15$. Каждый такой общий отрезок длины 5 оказывается внутри объединения и убирает из суммарного периметра по 5 у каждого из двух квадратов, то есть 10 на пару.

Итого $3\cdot 40-10-10=100$.

Проверка прямым обходом границы: $(0;0)$, $(10;0)$, $(10;10)$, $(15;10)$, $(15;20)$, $(20;20)$, $(20;30)$, $(10;30)$, $(10;20)$, $(5;20)$, $(5;10)$, $(0;10)$ и назад в $(0;0)$; сумма длин $10+10+5+10+5+10+10+10+5+10+5+10=100$.

Ответ: 100

Решение:

Всего пикселей: $512\cdot 750=384000$.

Сжатый файл занимает 80 Кбайт, а файл оригинала больше него на 65%, то есть $80\cdot 1{,}65=132$ Кбайт.

Переведём размер оригинала в биты: $132\cdot 1024\cdot 8=1081344$ бит.

На один пиксель приходится $\dfrac{1081344}{384000}=2{,}816$ бит. Глубина цвета $i$ — целое число бит, а из $i\le 2{,}816$ получаем максимум $i=2$.

Количество цветов $N=2^{i}=2^{2}=4$.

Ответ: 4

Решение:

Букв семь, в алфавитном порядке: А, Е, И, К, Л, П, Р. Слово с номером $n$ — это число $n-1$ в семеричной системе счисления (А=0, Е=1, И=2, К=3, Л=4, П=5, Р=6).

Так как основание 7 нечётно, чётность $n-1$ зависит от суммы всех цифр, поэтому просто перебираем все $7^6 = 117\,649$ слов и отбираем те, у которых номер чётный, первая буква не К, а букв И не менее двух.

from itertools import product

count = 0
for n, w in enumerate(product('АЕИКЛПР', repeat=6), 1):
    s = ''.join(w)
    if n % 2 == 0 and s[0] != 'К' and s.count('И') >= 2:
        count += 1
print(count)

Программа выводит 10892. Ответ: 10892

Решение:

В файле 3100 строк, в каждой четыре натуральных числа $a, b, c, d$. Строка подходит, если выполнены оба условия.

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

Второе условие: числа разбиваются на две пары с равными суммами. Разбиений четырёх чисел на две пары всего три, поэтому достаточно проверить три равенства: $a + b = c + d$, $a + c = b + d$, $a + d = b + c$.

import csv

count = 0
for row in csv.reader(open('data.csv'), delimiter=';'):
    a, b, c, d = [int(x) for x in row]
    s = sorted([a, b, c, d])
    big_ok = s[3] < s[0] + s[1] + s[2]
    pairs_ok = (a + b == c + d) or (a + c == b + d) or (a + d == b + c)
    if big_ok and pairs_ok:
        count += 1
print(count)   # 118

Программа находит 118 таких строк. Ответ: 118

Решение:

В маске 32 бита: $k$ единиц подряд, затем $32-k$ нулей. Нулей будет как можно больше, когда единиц как можно меньше, поэтому ищем наименьшее допустимое $k$.

Все единицы адреса сети должны сохраниться после наложения маски. Третий байт адреса сети равен $220 = 11011100_2$; самая правая единица всего адреса сети стоит именно в нём, на шестой позиции байта, то есть это 22-й бит адреса. Он обязан попасть в единичную часть маски: $k \ge 22$.

Ограничение сверху даёт четвёртый байт: число 205 должно обнулиться целиком, откуда $k \le 24$. Значит $k$ может быть 22, 23 или 24; наименьшее — 22, маска 255.255.252.0, и действительно $220\ \text{И}\ 252 = 220$.

Количество нулей в маске равно $32 - 22 = 10$.

def to_int(s):
    v = 0
    for byte in s.split('.'):
        v = v * 256 + int(byte)
    return v

ip  = to_int('171.5.220.205')
net = to_int('171.5.220.0')

ok = [k for k in range(33)
      if ip & (((1 << k) - 1) << (32 - k)) == net]
print(ok, 32 - min(ok))   # [22, 23, 24] -> 10

Ответ: 10

Решение:

Алфавит идентификатора состоит из 10 десятичных цифр и 250 специальных символов, то есть из $10+250=260$ символов. Если на один символ отводится $i$ бит, то должно выполняться $2^i \ge 260$. Так как $2^8=256 \lt 260$, а $2^9=512 \ge 260$, минимальное $i$ равно 9.

Идентификатор содержит 60 символов, значит на него уходит $60 \cdot 9 = 540$ бит. Хранится он в целом и минимальном числе байт: $540 : 8 = 67{,}5$, поэтому под один идентификатор отводится 68 байт.

Для 65 536 идентификаторов нужно $65536 \cdot 68$ байт. Удобно сразу перейти к килобайтам: $65536 : 1024 = 64$, поэтому объём памяти равен $64 \cdot 68 = 4352$ Кбайт.

bits = 9                      # 2**8 = 256 < 260 <= 512 = 2**9
size = -(-60 * bits // 8)     # 540 бит -> 68 байт (округление вверх)
print(65536 * size // 1024)   # 4352

Ответ: 4352

Решение:

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

• >1 → 222> : цифра 1 даёт три двойки, вклад в сумму 6;
• >2 → 3> : цифра 2 даёт тройку, вклад 3;
• >3 → 1> : цифра 3 даёт единицу, вклад 1.

Каждая цифра обрабатывается ровно один раз, поэтому их порядок не важен, и сумма цифр итоговой строки равна $$11 \cdot 6 + n \cdot 3 + 11 \cdot 1 = 77 + 3n.$$

При $n=1$ получаем $80$ — составное; при $n=2$ получаем $83$ — простое число. Наименьшее подходящее $n = 2$.

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", "222>")
        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" * 11 + "2" * n + "3" * 11)
    summa = sum(int(c) for c in s if c != ">")
    if prostoe(summa):
        print(n, summa)   # 2 83
        break
    n += 1

Ответ: 2

Решение:

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

Пусть $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(60, 10) * f(10, 2))

Получаем $f(60, 10) = 163$ и $f(10, 2) = 12$, то есть всего $163 \cdot 12 = 1956$ программ. Ответ: 1956

Решение:

Так как $9 = 3^{2}$, выразим все слагаемые через степени девятки:

• $2\cdot 3^{2022} = 2\cdot 9^{1011}$;
• $5\cdot 3^{1800} = 5\cdot 9^{900}$;
• $3^{1001} + 4\cdot 3^{1000} = 3\cdot 3^{1000} + 4\cdot 3^{1000} = 7\cdot 3^{1000} = 7\cdot 9^{500}$;
• $3 = 3\cdot 9^{0}$.

Значит, $N = 2\cdot 9^{1011} + 5\cdot 9^{900} + 7\cdot 9^{500} + 3$. Коэффициенты 2, 5, 7, 3 — допустимые девятеричные цифры и стоят в разных разрядах, переносов нет, поэтому это уже готовая девятеричная запись.

Старший разряд — 1011-й, всего цифр $1012$, ненулевых из них четыре. Значащих нулей: $1012 - 4 = 1008$.

def to_base(n, b):
    s = ''
    while n:
        s = str(n % b) + s
        n //= b
    return s

n = 2 * 3**2022 + 5 * 3**1800 + 3**1001 + 4 * 3**1000 + 3
print(to_base(n, 9).count('0'))     # 1008

Ответ: 1008

Решение:

Дизъюнкция ложна, только если ложны все четыре части, то есть одновременно

$x \geq 4$, $x \lt 20$, $y \lt 3x + A$, $y \geq 100$.

Значит формула тождественно истинна тогда и только тогда, когда при всех целых $4 \leq x \leq 19$ и всех $y \geq 100$ выполняется $y \geq 3x + A$.

Самый жёсткий случай — наименьшее $y = 100$ и наибольшее $x = 19$:

$100 \geq 3 \cdot 19 + A = 57 + A \Rightarrow A \leq 43$.

При $A = 43$ для всех $x \leq 19$ имеем $3x + 43 \leq 100 \leq y$, то есть формула истинна. Наибольшее целое $A = 43$.

Ответ: 43

Решение:

Значения считаем по порядку, начиная с $F(0) = F(1) = 1$. Для чётных $n \gt 1$ значение просто удваивается, для нечётных используем $F(n) = 3 + F(n-1) \cdot F(n-2) - F(n-1) - F(n-2)$ (удобно свернуть его как $F(n) = \bigl(F(n-1) - 1\bigr)\bigl(F(n-2) - 1\bigr) + 2$).

$F(2) = 2 \cdot 1 = 2$; $F(3) = 3 + 2 \cdot 1 - 2 - 1 = 2$; $F(4) = 2 \cdot 2 = 4$; $F(5) = 3 + 4 \cdot 2 - 4 - 2 = 5$; $F(6) = 10$; $F(7) = 3 + 10 \cdot 5 - 10 - 5 = 38$; $F(8) = 76$; $F(9) = 3 + 76 \cdot 38 - 76 - 38 = 2777$; $F(10) = 5554$; $F(11) = 3 + 5554 \cdot 2777 - 5554 - 2777 = 15415130$; $F(12) = 2 \cdot 15415130 = 30830260$.

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n <= 1:
        return 1
    if n % 2 == 1:
        return 3 + F(n - 1) * F(n - 2) - F(n - 1) - F(n - 2)
    return 2 * F(n - 1)

print(F(12))   # 30830260

Ответ: 30830260

Решение:

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

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

• между 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)

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

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

Ответ: 2255 820

Решение:

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

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

Нужно $S\le51$ (Петя не выигрывает сразу) и одновременно $S+1\ge52$, $S+5\ge52$, $4S\ge52$, то есть $S\ge51$, $S\ge47$ и $S\ge13$. Остаётся $S=51$.

Проверка: из 51 Петя получает 52, 56 или 204 — все не меньше 52, поэтому Ваня заканчивает игру своим ходом. Сам Петя выиграть сразу не мог: $52\lt205$, $56\lt205$, $204\lt205$.

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

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

Ответ: 51

Решение:

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

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

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

• $(15,\ 43)$ — Петя удваивает вторую кучу: $15 + 86 = 101$;
• $(14,\ 44)$ — Петя удваивает вторую кучу: $14 + 88 = 102$;
• $(28,\ 43)$ — Петя удваивает вторую кучу: $28 + 86 = 114$;
• $(14,\ 86)$ — Петя добавляет камень: $14 + 87 = 101$.

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

• $(9,\ 46)$ — Петя удваивает вторую кучу: $9 + 92 = 101$;
• $(8,\ 47)$ — Петя удваивает вторую кучу: $8 + 94 = 102$;
• $(16,\ 46)$ — Петя удваивает вторую кучу: $16 + 92 = 108$;
• $(8,\ 92)$ — Петя добавляет камень: $8 + 93 = 101$.

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

N = 101

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, 94) if win2((7, s))][:2])   # два наименьших

Ответ: 43 46

Решение:

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

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

В1. Из позиции $(3,\ S)$ игру заканчивают ход «добавить два камня» ($S+5 \ge 122$) и удвоение большей кучи ($2S+3 \ge 122$). Второе условие слабее, поэтому В1 — это все $S \ge 60$.

П1 для начальной позиции — единственное значение $S = 59$; В2 — значения $S = 57$, $S = 58$.

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

При $S = 55$ четыре хода Пети дают позиции $(3,\ 57)$ (В2), $(5,\ 55)$ (В2), $(6,\ 55)$ (В2), $(3,\ 110)$ (В1). Все они для Вани выигрышны не позже второго хода, но три из них — только вторым ходом, поэтому гарантированно выиграть первым ходом Ваня не может. Полный перебор подтверждает, что меньших значений $S$ с таким свойством нет.

Перебор всех $S$ удобно сделать программой:

N = 122

def moves(p):
    a, b = p
    return [(a + 2, b), (a, b + 2), (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))

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

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

Ответ: 55

Решение:

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

Подставим $t = 2$ и заполним столбец $F$:

Наибольшее значение равно 12 мс, условие «не более 12 мс» выполнено. При $t = 3$ общее время стало бы равно 13 мс, что больше 12, поэтому 2 — максимально возможное целое значение.

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

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

def total(t):
    finish = {}
    for i in sorted(data):
        dur, deps = data[i]
        if dur is None:
            dur = t
        finish[i] = max([finish[d] for d in deps], default=0) + dur
    return max(finish.values())

print(max(t for t in range(1, 1000) if total(t) <= 12))

Ответ: 2

Решение.

В файле 1097 рёбер. Рёбра ведут только из вершины с меньшим номером в вершину с большим, поэтому граф ациклический, а порядок 1, 2, …, 100 — топологический: любой путь проходит вершины по возрастанию номеров.

Значит, кратчайшие расстояния считаются одним проходом по вершинам в порядке возрастания номера. Заведём массив d, положим d[1] = 0, остальные — «бесконечность», и для каждой вершины по очереди пробуем улучшить расстояния до её соседей.

edges = []
for line in open('23.txt'):
    a, b, w = line.split()
    edges.append((int(a), int(b), float(w)))

INF = float('inf')
d = [INF] * 101
d[1] = 0
for v in range(1, 101):
    if d[v] == INF:
        continue
    for a, b, w in edges:
        if a == v and d[v] + w < d[b]:
            d[b] = d[v] + w

print(int(d[100]))

Программа печатает 2460. Задание просит целую часть длины, поэтому дробная часть отбрасывается. Ответ: 2460.

Решение:

Запрещена только одна конфигурация — две буквы 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

Решение:

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

Здесь $M = n/p + p$ — сумма крайних делителей. Условие «оканчивается на 8» касается последней цифры, то есть m % 10 == 8. Перебираем числа, начиная с 700001, по возрастанию и останавливаемся, найдя пять подходящих.

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

n = 700000
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m % 10 == 8:
        print(n, m)
        found += 1

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

700005 233338
700007 100008
700012 350008
700015 140008
700031 24168

Ответ: 700005 233338 700007 100008 700012 350008 700015 140008 700031 24168

Решение:

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

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

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 - 3:
        cnt += 1
        last = x
print(cnt, last)

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

2767 51

Ответ: 2767 51

Решение:

Сначала забудем про делимость и возьмём из каждой пары большее число. Полученная сумма $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