Вариант 5 · Октябрь 2026

Решение:

Функция $F = x \land (y \rightarrow z) \land (\neg y \rightarrow (\neg z \equiv w))$ — это конъюнкция, поэтому разберём, когда она равна 1. Прежде всего обязательно $x = 1$. Дальше два случая:

• если $y = 1$, то из $y \rightarrow z$ следует $z = 1$, а третья скобка выполняется автоматически (её посылка $\neg y = 0$);
• если $y = 0$, то вторая скобка истинна, а третья требует $w = \neg z$, то есть $z$ и $w$ должны быть различны.

Значит, единица получается ровно в четырёх наборах $(x, y, z, w)$: $(1,1,1,0)$, $(1,1,1,1)$, $(1,0,0,1)$, $(1,0,1,0)$.

Шаг 1. Находим столбец x. В первых двух строках фрагмента $F = 1$, значит, в них $x = 1$. В первой строке нули стоят в столбцах 3 и 4 — там $x$ стоять не может. Во второй строке нули стоят в столбцах 2 и 3 — там $x$ тоже стоять не может. Остаётся единственный вариант: $x$ — первый столбец.

Шаг 2. Находим столбец y. В первой строке фрагмента среди $y, z, w$ уже видно два нуля (столбцы 3 и 4), во второй — тоже два (столбцы 2 и 3). Из четырёх «единичных» наборов два нуля среди $y, z, w$ есть только у $(1,0,0,1)$ и $(1,0,1,0)$. В первой строке фрагмента второй столбец равен 1, а во второй строке он равен 0, так что это разные наборы — то есть первая и вторая строки в каком-то порядке и есть эти два набора.

В обоих наборах $y = 0$, а $z$ и $w$ принимают в них разные значения. Столбец 3 равен нулю в обеих строках, поэтому $y$ — третий столбец.

Шаг 3. Различаем z и w. Они стоят во втором и четвёртом столбцах. Используем третью строку фрагмента: там первый столбец равен 1 ($x = 1$), третий равен 1 ($y = 1$), четвёртый равен 1, и при этом $F = 0$. Но при $x = 1$ и $y = 1$ функция равна нулю только если $z = 0$. Значит, в четвёртом столбце стоит не $z$, а $w$; тогда $z$ — второй столбец.

Итого порядок столбцов: $x$, $z$, $y$, $w$.

Тот же ответ даёт короткая программа, перебирающая все 24 расстановки переменных по столбцам:

from itertools import permutations, product

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

frag = [((None, None, 0, 0), 1),
        ((None, 0, 0, None), 1),
        ((1, None, 1, 1), 0)]

def fits(pat, row):
    return all(p is None or p == v for p, v in zip(pat, row))

for p in permutations('xyzw'):
    table = []
    for vals in product([0, 1], repeat=4):
        d = dict(zip(p, vals))
        table.append((vals, int(bool(F(d['x'], d['y'], d['z'], d['w'])))))
    for tri in permutations(table, 3):
        if all(fits(pat, row) and val == f
               for (pat, val), (row, f) in zip(frag, tri)):
            print(''.join(p))
            break

Ответ: xzyw

Решение:

Нужна масса зефира, который был получен магазинами, то есть учитываем только операции с типом «Поступление», а «Продажу» игнорируем. Данные разнесены по трём таблицам: даты, количество упаковок и тип операции лежат в «Движении товаров», масса упаковки — в «Товаре» (связь по полю «Артикул»), адрес — в «Магазине» (связь по полю «ID магазина»).

Сначала по таблице «Магазин» находим магазины на улице Металлургов. Их два: M2 по адресу «ул. Металлургов, 12» и M16 по адресу «ул. Металлургов. 29». Во втором адресе после слова «Металлургов» стоит точка, а не запятая, поэтому поиск по строке «Металлургов,» этот магазин теряет — это главная ловушка задания: без M16 ответ получается ровно вдвое меньше, 1785.

Затем в таблице «Товар» отбираем зефир — это артикулы с 4 по 7: «Зефир в шоколаде» (250 граммов в упаковке), «Зефир ванильный» (800), «Зефир воздушный» (500) и «Зефир лимонный» (1000). Все четыре товара измеряются в граммах, поэтому масса одной операции равна количеству упаковок, умноженному на количество граммов в упаковке.

В таблице «Движение товаров» отводим свободный столбец G, записываем в ячейку G2 формулу и копируем её до конца таблицы (до строки 4321), а затем суммируем столбец и делим результат на 1000, чтобы перевести граммы в килограммы:

=ЕСЛИ(И(F2="Поступление";
        B2>=ДАТА(2023;6;4); B2<=ДАТА(2023;6;13);
        ИЛИ(C2="M2"; C2="M16");
        D2>=4; D2<=7);
     E2*ВПР(D2; Товар!A:E; 5; 0);
     0)

=СУММ(G2:G4321)/1000

Сумма равна 3 570 000 граммов, то есть 3570 кг (по 1785 кг на каждый из двух магазинов на улице Металлургов).

Ответ: 3570

Решение:

Известно: А — 01000, Б — 10001, В — 11010, Г — 00. Нужны три новых кодовых слова с наименьшей суммарной длиной.

Свободных слов длины 1 нет: 0 является началом слова 00 (буква Г), а 1 — началом слова 10001.

Свободных слов длины 2 тоже нет: 00 занято буквой Г, 01 является началом слова 01000, 10 — началом слова 10001, 11 — началом слова 11010.

Значит, каждое из трёх новых слов имеет длину не менее 3. Подходящие слова длины 3 действительно найдутся: в ветви 01 занята только вершина 010 (там лежит А) — свободно 011; в ветви 10 занята вершина 100 — свободно 101; в ветви 11 занята вершина 110 — свободно 111.

Получаем набор 011, 101, 111 с минимальной суммой длин $3 + 3 + 3 = 9$.

Ответ: 9

Решение:

Первый шаг алгоритма — вычитание остатка от деления на 4 — превращает $N$ в число $M = N - (N \bmod 4)$, кратное четырём. Дальше к двоичной записи $M$ дважды приписывается справа бит чётности, то есть запись удлиняется ровно на два разряда: $R = 4M + 2b_1 + b_0$, где $b_1$ и $b_0$ — приписанные биты.

Отсюда $R \ge 4M$, и из условия $R \lt 47$ следует $M \le 11$. Кратных четырём значений тут немного: $M = 0$, $M = 4$, $M = 8$. Чем больше $M$, тем больше $R$, поэтому берём наибольшее подходящее $M = 8$ и проверяем его.

Запись числа 8 — 1000. Сумма цифр равна 1, остаток от деления на 2 равен 1, приписываем: 10001. Теперь сумма цифр равна 2, остаток 0, приписываем: 100010. Это $32 + 2 = 34$, и действительно $34 \lt 47$. Для сравнения, $M = 4$ даёт $100 \to 1001 \to 10010 = 18$, а $M = 12$ уже даёт $1100 \to 11000 \to 110000 = 48 \gt 47$. Наибольшее подходящее $R$ равно 34 (оно получается при $N = 8, 9, 10, 11$).

def R(N):
    b = bin(N - N % 4)[2:]
    for _ in range(2):
        b += str(sum(int(c) for c in b) % 2)
    return int(b, 2)

print(max(R(N) for N in range(1, 1000) if R(N) < 47))   # 34

Ответ: 34

Решение:

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

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

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

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

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

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

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

from math import sin, cos, radians

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

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

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

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

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

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

Ответ: 588

Решение:

В палитре 8192 цвета, а $8192 = 2^{13}$, значит на один пиксель отводится 13 бит.

Объём одной фотографии: $1024 \cdot 960 \cdot 13 = 12\,779\,520$ бит.

Объём пакета из 160 снимков: $12\,779\,520 \cdot 160 = 2\,044\,723\,200$ бит.

Скорость передачи $14\,680\,064 = 14 \cdot 2^{20}$ бит/с, поэтому время передачи пакета равно $$t = \frac{2\,044\,723\,200}{14\,680\,064} = \frac{1950}{14} = \frac{975}{7} \approx 139{,}29 \text{ с.}$$

Целая часть полученного числа — 139.

print(1024 * 960 * 13 * 160 // 14680064)

Ответ: 139

Решение:

Кодовое слово состоит из трёх позиций. Буква К должна встретиться ровно один раз, поэтому сначала выберем для неё позицию — это можно сделать $3$ способами.

Каждая из двух оставшихся позиций заполняется любой из четырёх букв Ш, О, Л, А: букву К туда ставить нельзя, иначе она встретится больше одного раза. Это даёт $4^2 = 16$ вариантов.

По правилу произведения общее количество слов равно $3 \cdot 4^2 = 3 \cdot 16 = 48$.

from itertools import product

count = 0
for w in product('ШКОЛА', repeat=3):
    if w.count('К') == 1:
        count += 1
print(count)   # 48

Ответ: 48

Решение:

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

Разбор задачи:

Для решения воспользуемся библиотекой ipaddress. Сформируем объект сети на основе заданного IP-адреса и маски подсети. Далее в цикле переберем все доступные адреса в этой сети. Для каждого узла проверим условие: количество единиц в его двоичном представлении должно быть четным. Если условие выполняется, увеличиваем счетчик. В конце выводим итоговое количество подходящих адресов.

Ответ: 1024

Источник: ФИПИ

Решение:

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

Один идентификатор из 108 символов занимает $108 \cdot 7 = 756$ бит. Число байт должно быть целым и минимальным: $756 = 8 \cdot 94 + 4$, поэтому под него отводится 95 байт.

Все 25 600 идентификаторов занимают $25600 \cdot 95 = 2432000$ байт, то есть $2432000 : 1024 = 2375$ Кбайт.

import math

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

Ответ: 2375

Решение:

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

Три конструкции ЕСЛИ внутри цикла выполняются последовательно, так что за один проход тела цикла может произойти несколько замен. Аналитически сумму цифр не выразить, но диапазон $3 \lt n \lt 10000$ невелик, поэтому перебираем все допустимые $n$ программой.

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

def rabota(s):
    while "31" in s or "411" in s or "1111" in s:
        if "31" in s:
            s = zamenit(s, "31", "1")
        if "411" in s:
            s = zamenit(s, "411", "13")
        if "1111" in s:
            s = zamenit(s, "1111", "4")
    return s

for n in range(4, 10000):
    s = rabota("4" + "1" * n)
    if sum(int(c) for c in s) == 34:
        print(n, s)
        break
# 187 1333413341341

Наименьшее подходящее значение — $n = 187$: остаётся строка 1333413341341 с суммой цифр 34.

Ответ: 187

Решение:

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

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$: $f(x, x) = 1$ (пустая программа), $f(x, y) = 0$ при $x \gt y$ (число уже «перескочило» цель, а уменьшать команды не умеют). В остальных случаях перебираем первую команду («прибавить 1», «прибавить 4» или «умножить на 2»):

$$f(x, y) = f(x + 1,\, y) + f(x + 4,\, y) + f(2x,\, y).$$

Числа $11$ и $17$ траектория содержать не должна, поэтому переходы в них запрещаем — соответствующие слагаемые отбрасываем.

from functools import lru_cache

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

print(f(3, 24))

Программа выводит $298$.

Ответ: 298

Решение:

Основание 16 — это $4^2$, поэтому $4^{2k} = 16^{k}$, а $4^{2k+1} = 4 \cdot 16^{k}$. Переведём каждое слагаемое:

• $3 \cdot 4^{38} = 3 \cdot 16^{19}$;
• $2 \cdot 4^{23} = 2 \cdot 4 \cdot 16^{11} = 8 \cdot 16^{11}$;
• $4^{20} = 16^{10}$;
• $3 \cdot 4^{5} = 3 \cdot 4 \cdot 16^{2} = 12 \cdot 16^{2}$ и $2 \cdot 4^{4} = 2 \cdot 16^{2}$, вместе $14 \cdot 16^{2}$;
• $1 = 1 \cdot 16^{0}$.

Все коэффициенты $(3,\ 8,\ 1,\ 14,\ 1)$ меньше 16, значит переносов нет и это уже готовые шестнадцатеричные цифры:

$N = 3\,\underbrace{0\ldots0}_{7}\,8\,1\,\underbrace{0\ldots0}_{7}\,\mathrm{E}\,0\,1_{16}$

Старший разряд — 19-й, поэтому в записи 20 цифр. Ненулевых среди них 5 (в разрядах 19, 11, 10, 2 и 0), значит нулей $20 - 5 = 15$.

n = 3*4**38 + 2*4**23 + 4**20 + 3*4**5 + 2*4**4 + 1
s = ''
while n:
    s = '0123456789ABCDEF'[n % 16] + s
    n //= 16
print(s, s.count('0'))

Ответ: 15

Решение:

Формула $\neg \text{ДЕЛ}(x, A) \rightarrow (\text{ДЕЛ}(x, 6) \rightarrow \neg \text{ДЕЛ}(x, 9))$ обращается в 0 только тогда, когда посылка истинна, а следствие ложно, то есть когда $x$ не делится на $A$, но делится и на 6, и на 9.

Следовательно, тождественная истинность равносильна условию: любое число, кратное одновременно 6 и 9, делится на $A$.

Такие числа — это в точности кратные $\text{НОК}(6, 9)$. Так как $6 = 2 \cdot 3$ и $9 = 3^{2}$, получаем $\text{НОК}(6, 9) = 2 \cdot 3^{2} = 18$.

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

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

Ответ: 18

Решение:

Правило $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

Решение:

Задача решается одним проходом по файлу, но сначала нужно вычислить «планку» — максимальный элемент последовательности, оканчивающийся на 13. Число оканчивается на 13 тогда и только тогда, когда остаток от его деления на 100 равен 13. Для данного файла эта планка равна 98413.

Дальше перебираем все тройки идущих подряд элементов (то есть окна вида $a_i, a_{i+1}, a_{i+2}$) и проверяем два условия: ровно два числа тройки трёхзначные, то есть лежат в диапазоне от 100 до 999, и сумма всех трёх чисел не превосходит найденной планки. Считаем такие тройки и параллельно запоминаем наибольшую из их сумм.

Подходящих троек оказывается 959, а наибольшая сумма среди них равна 97471.

a = [int(line) for line in open('17.txt')]

limit = max(x for x in a if x % 100 == 13)   # 98413

count = 0
best = 0
for i in range(len(a) - 2):
    t = a[i:i + 3]
    if sum(100 <= x <= 999 for x in t) == 2 and sum(t) <= limit:
        count += 1
        best = max(best, sum(t))

print(count, best)   # 959 97471

Ответ: 959 97471

Решение:

Робот ходит только вправо и вниз, поэтому в любую клетку он может прийти лишь слева или сверху. Это классическая динамика по таблице: рядом с исходным полем $20 \times 20$ строим ещё две таблицы того же размера — в первой накапливаем максимально возможную сумму, во второй минимально возможную.

В левую верхнюю клетку обеих таблиц записываем саму монету (в этом файле это 99). Остальные клетки заполняем построчно слева направо по правилу: значение равно монете из исходной таблицы плюс наибольшее (соответственно наименьшее) из значений соседей слева и сверху, причём сосед учитывается только тогда, когда между ним и текущей клеткой нет утолщённой линии — стены. Если оба входа перекрыты стенами, клетка недостижима и остаётся пустой. Например, если исходные данные лежат в диапазоне A1:T20, а таблицу максимумов разместить в A23:T42, то в клетку B24 (она отвечает клетке R2C2 поля) пишем =B2+МАКС(A24;B23), а там, где вход перекрыт стеной, соответствующий аргумент из формулы просто убираем.

Маршрут заканчивается в «угловой» клетке — той, у которой перекрыты и правый, и нижний переходы. В этом файле таких достижимых клеток три: R15C18, R20C12 и R20C20. Ответ ищем только среди них, а не по всей таблице. Наибольшая накопленная сумма получается в правой нижней клетке R20C20 и равна 2167, наименьшая — в клетке R15C18 и равна 718.

import openpyxl

ws = openpyxl.load_workbook('18.xlsx').active
N = 20
coin = [[ws.cell(r + 1, c + 1).value for c in range(N)] for r in range(N)]

def thick(r, c, side):          # утолщённая линия = стена
    return getattr(ws.cell(r + 1, c + 1).border, side).style == 'thick'

def wall_right(r, c):
    return c == N - 1 or thick(r, c, 'right') or thick(r, c + 1, 'left')

def wall_down(r, c):
    return r == N - 1 or thick(r, c, 'bottom') or thick(r + 1, c, 'top')

hi = [[None] * N for _ in range(N)]
lo = [[None] * N for _ in range(N)]
hi[0][0] = lo[0][0] = coin[0][0]
for r in range(N):
    for c in range(N):
        if hi[r][c] is None:
            continue
        for nr, nc, blocked in ((r, c + 1, wall_right(r, c)),
                                (r + 1, c, wall_down(r, c))):
            if blocked:
                continue
            a = hi[r][c] + coin[nr][nc]
            b = lo[r][c] + coin[nr][nc]
            hi[nr][nc] = a if hi[nr][nc] is None else max(hi[nr][nc], a)
            lo[nr][nc] = b if lo[nr][nc] is None else min(lo[nr][nc], b)

ends = [(r, c) for r in range(N) for c in range(N)
        if hi[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(hi[r][c] for r, c in ends), min(lo[r][c] for r, c in ends))
# 2167 718

Ответ: 2167 718

Решение:

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

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

Из начальной позиции $(3,S)$ Петя может получить позиции $(5,S)$, $(6,S)$, $(3,S+2)$ и $(3,2S)$. Самая опасная — $(3,2S)$: Ваня удваивает вторую кучу ещё раз и получает сумму $3+4S$. Условие $3+4S\ge122$ даёт $4S\ge119$, $S\ge29{,}75$, то есть $S\ge30$.

Другие ходы требуют большего $S$: из $(3,S+2)$ сумма после хода Вани равна $2S+7\ge122$, откуда $S\ge58$; из $(6,S)$ — $6+2S\ge122$, $S\ge58$; из $(5,S)$ — $5+2S\ge122$, $S\ge59$.

Проверим $S=30$. Петя ходит $(3,30)\to(3,60)$: сумма 63, игра продолжается. Ваня удваивает: $(3,120)$, сумма $123\ge122$ — победа первым ходом. Сам Петя выиграть сразу не мог: $3+30+30=63\lt122$. При $S\lt30$ такая ситуация невозможна.

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

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

for S in range(1, 118):
    if any(x + y < 122 and win1((x, y)) for x, y in moves((3, S))):
        print(S)
        break

Ответ: 30

Решение:

Напомним игру: позиция (x, y) — две кучи; своим ходом игрок добавляет в одну из куч два камня либо увеличивает одну из куч в три раза; игра заканчивается, когда в кучах суммарно окажется не менее 136 камней. В начале первая куча — 2 камня, вторая — S камней.

За один ход сумма растёт на 2, на $2x$ или на $2y$ (утроение кучи прибавляет две такие же кучи), значит игрок заканчивает игру своим ходом тогда и только тогда, когда $x+y+2\max(x,\,y,\,1) \ge 136$. В интересующих нас позициях вторая куча больше, поэтому условие принимает вид $x+3y \ge 136$.

Чтобы выиграть вторым ходом, Петя должен передать Ване проигрышную позицию: из неё Ваня закончить игру не может, но любой его ход отдаёт победу Пете. Слабейший ход Вани — «+2» в первую кучу, после него нужно $x+2+3y \ge 136$, то есть $x+3y \ge 134$; а чтобы сам Ваня не выиграл, нужно $x+3y \le 135$. Итак, проигрышные позиции — те, где $x+3y$ равно 134 или 135.

S = 42. Позиция (2, 42): $2+3\cdot 42 = 128 \lt 136$ — сам Петя не выигрывает. Он добавляет два камня во вторую кучу: (2, 44), где $2+3\cdot 44 = 134$. Любой ответ Вани проигрышен: (4, 44) даёт $4+132=136$, (2, 46) даёт $2+138=140$, (6, 44) даёт $6+132=138$, (2, 132) — тем более; во всех случаях Петя вторым ходом утраивает бо́льшую кучу и набирает не менее 136 камней.

S = 43. Позиция (2, 43): $2+129=131 \lt 136$. Теперь ход «+2 во вторую кучу» не годится: в позиции (2, 45) уже $2+135=137 \ge 136$, и Ваня выигрывает сразу. Зато Петя может утроить первую кучу: (6, 43), где $6+3\cdot 43 = 135$ — проигрышная позиция. Ответы Вани: (8, 43) даёт $8+129=137$, (6, 45) даёт $6+135=141$, (18, 43) даёт $18+129=147$, (6, 129) — тем более; всюду Петя заканчивает игру вторым ходом.

Меньших значений нет, что подтверждает перебор:

N = 136
A = 2                             # камней в первой куче

def moves(p):
    x, y = p
    return [(x + 2, y), (x, y + 2), (3 * x, y), (x, 3 * y)]

def win1(p):                      # ходящий заканчивает игру своим ходом
    return any(x + y >= N for x, y 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))

print([s for s in range(1, 133) if win2((A, s))][:2])   # [42, 43]

Ответ: 42 43

Решение:

Напомним условие игры из задания 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

Время завершения процесса p равно его собственному времени плюс наибольшее из времён завершения процессов, от которых он зависит: t(p) = time(p) + max t(зависимости). Для независимого процесса t(p) = time(p).

Считаем t(p) для всех 25 процессов файла в порядке зависимостей.

Всё вычисление завершится тогда, когда завершится последний процесс, то есть в момент max t(p) = 34 мс.

Ответ: 34.

Решение.

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

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

Ответ: 1649.

Решение:

Условие «ни одна буква не стоит рядом с буквой, а цифра — с цифрой» означает, что на искомом участке буквы и цифры строго чередуются: любые два соседних символа должны быть разного типа. Конкретные значения (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

Решение:

Переведём маску 1?2157*4 в условие на строку десятичной записи числа: первая цифра равна 1; вторая цифра любая (символ «?»); далее подряд идут цифры 2157; затем произвольная, возможно пустая, последовательность цифр (символ «*»); последняя цифра равна 4. Отсюда сразу видно, что в числе не менее семи цифр.

Перебирать все числа до $10^{10}$ незачем: достаточно пройти только по кратным 2024, тогда делимость выполняется автоматически, а проверять останется лишь совпадение с маской. Таких кратных около пяти миллионов, программа отрабатывает за секунды.

for n in range(2024, 10**10 + 1, 2024):
    s = str(n)
    if len(s) >= 7 and s[0] == '1' and s[2:6] == '2157' and s[-1] == '4':
        print(n, n // 2024)

Условие len(s) >= 7 гарантирует, что блок 2157 и завершающая цифра 4 не накладываются друг на друга, то есть «*» действительно может быть пустой последовательностью. Программа находит 11 чисел; выводим их по возрастанию вместе с частными:

Ответ: 142157664 70236 1021575544 504731 1121571264 554136 1221577104 603546 1321572824 652951 1421578664 702361 1521574384 751766 1621570104 801171 1721575944 850581 1821571664 899986 1921577504 949396

Решение:

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

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

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

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

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

k = max(dp)

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

print(k, gap)

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

Ответ: 32 15

Решение:

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