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

Решение:

Конъюнкция равна единице, только если истинны все множители: $z=1$, $w=0$ и $x \rightarrow y = 1$.

Таких наборов ровно три: $(w,x,y,z)$ равно $(0,0,0,1)$, $(0,0,1,1)$ или $(0,1,1,1)$.

Во всех строках $w=0$, поэтому в столбце $w$ не может быть единиц. Единицы есть в первом, третьем и четвёртом столбцах, значит $w$ — второй столбец (он полностью пуст).

Во второй и третьей строках первый столбец равен 1. Если бы это была переменная $x$, то в обеих строках $x=1$, откуда $y=1$, и вместе с $z=1$, $w=0$ обе строки оказались бы набором $(0,1,1,1)$ — но строки различны. Переменной $z$ первый столбец тоже не соответствует: в первой строке там 0, а $z=1$ всегда. Значит первый столбец — $y$.

В первой строке $y=0$, поэтому $x=0$ (иначе нарушится условие $x \rightarrow y$), а третий столбец в этой строке равен 1. Следовательно третий столбец — не $x$, а $z$; переменной $x$ остаётся четвёртый столбец.

Тот же результат даёт перебор всех 24 расстановок переменных по столбцам:

from itertools import permutations, product

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

rows = [t for t in product([0, 1], repeat=4) if F(*t)]   # наборы (w, x, y, z) с F = 1

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

for cols in permutations('wxyz'):        # cols[i] — переменная в i-м столбце
    for order in permutations(rows, 3):  # какой набор какой строке фрагмента
        val = [dict(zip('wxyz', t)) for t in order]
        if all(frag[r][i] is None or frag[r][i] == val[r][cols[i]]
               for r in range(3) for i in range(4)):
            print(''.join(cols))
            break

Ответ: ywzx

Решение:

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

Шаг 1. В таблице «Магазин» отбираем магазины Заречного района и выписываем их ID магазина (их четыре).

Шаг 2. В таблице «Товар» находим строку «Яйцо диетическое» и запоминаем её артикул.

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

Шаг 4. Двумя формулами СУММЕСЛИМН считаем сумму столбца «Количество упаковок, шт.» отдельно по типу операции «Поступление» и по типу «Продажа»: 1420 и 454 упаковки. Увеличение: $1420 - 454 = 966$ упаковок.

Ответ: 966

Решение:

Известно: А — 101000, Б — 111100, В — 000. Кодовые слова нужны ещё двум буквам — Г и Д, причём как можно короче.

Свободных слов длины 1 нет: 0 является началом слова 000 (буква В), а 1 — началом слов 101000 и 111100.

Среди слов длины 2: 00 является началом слова 000, 10 — началом слова 101000, 11 — началом слова 111100. Свободно только одно слово — 01.

Значит, длину 2 может получить лишь одна из двух букв, а второй достанется слово длины не менее 3. Такое слово есть: например, 001 (оно не является началом ни одного из слов 101000, 111100, 000, и они не являются его началом). Подходит и 100, и 110.

Минимальная сумма длин: $2 + 3 = 5$.

Ответ: 5

Решение:

Автомат выводит две суммы квадратов цифр, записанные подряд в порядке невозрастания. Каждая такая сумма имеет вид $a^2+b^2$, где $a$ и $b$ — цифры, поэтому она не превосходит $9^2+9^2=162$, то есть содержит не больше трёх цифр.

Значит, число 7434 нужно разбить на два куска $A$ и $B$, причём $A\ge B$ и оба не больше 162. Разбиение 7 и 434 не подходит: $7\lt 434$. Разбиение 743 и 4 не подходит: $743\gt 162$. Остаётся единственный вариант: $A=74$, $B=34$.

Пусть исходное число — $\overline{d_1d_2d_3}$. Тогда $d_1^2+d_2^2=74$ и $d_2^2+d_3^2=34$.

Квадраты цифр — это 0, 1, 4, 9, 16, 25, 36, 49, 64, 81. Перебирая пары, получаем:

• 74 представляется единственным способом: $25+49$, то есть цифрами 5 и 7;
• 34 представляется единственным способом: $9+25$, то есть цифрами 3 и 5.

Цифра $d_2$ входит в обе пары, поэтому $d_2=5$. Отсюда $d_1=7$ и $d_3=3$: число определяется однозначно.

def f(n):
    d = [int(c) for c in str(n)]
    a = d[0] ** 2 + d[1] ** 2
    b = d[1] ** 2 + d[2] ** 2
    return int(str(max(a, b)) + str(min(a, b)))

print(max(n for n in range(100, 1000) if f(n) == 7434))

Ответ: 753

Решение:

Хвост поднят, поэтому Вперёд 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

Решение:

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

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

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

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

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

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

Ответ: 16

Решение:

Восьмеричные цифры без единицы — это $0,2,3,4,5,6,7$: четыре чётные $(0,2,4,6)$ и три нечётные $(3,5,7)$. Условие «никакие две чётные и никакие две нечётные цифры не стоят рядом» означает, что чётность цифр строго чередуется, поэтому подходят лишь два шаблона: ЧНЧНЧ и НЧНЧН (Ч — чётная цифра, Н — нечётная). Дополнительно все цифры различны, а первая цифра не может быть нулём.

Шаблон НЧНЧН: нечётных цифр ровно три, и все они идут в дело — $3!=6$ способов; на два чётных места ставим упорядоченную пару из четырёх чётных цифр — $4\cdot3=12$ способов; ноль на первое место здесь попасть не может. Итого $6\cdot12=72$ числа.

Шаблон ЧНЧНЧ: упорядоченных троек чётных цифр $4\cdot3\cdot2=24$, из них начинаются с нуля $3\cdot2=6$, остаётся 18; нечётные цифры дают $3\cdot2=6$ способов. Итого $18\cdot6=108$ чисел. Всего $72+108=180$.

from itertools import permutations

digits = [0, 2, 3, 4, 5, 6, 7]        # восьмеричные цифры без единицы
count = 0
for p in permutations(digits, 5):     # все цифры различны
    if p[0] == 0:
        continue
    if all(p[i] % 2 != p[i + 1] % 2 for i in range(4)):
        count += 1
print(count)   # 180

Ответ: 180

Решение:

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

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

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

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

import csv

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

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

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

Решение:

Левые два байта у всех адресов сети одинаковы: $255 = 11111111_2$ даёт 8 единиц, $211 = 11010011_2$ даёт 5. Значит $L = 13$ при любом адресе сети.

Маска 255.255.$A$.0 фиксирует старшие разряды третьего байта: если в $A$ ровно $s$ единиц, то в третьем байте свободны $8-s$ младших битов, а четвёртый байт свободен целиком. Наибольшее число единиц в правых двух байтах равно

$$R_{\max} = \nu(33 \wedge A) + (8-s) + 8,$$

где $\nu(x)$ — число единиц в двоичной записи $x$; здесь $33 = 00100001_2$. Условие «для всех адресов $L\ge R$» означает $R_{\max}\le 13$.

Перебираем допустимые значения байта маски, начиная с меньших:

• $A = 224$ ($s=3$): $33 \wedge 224 = 32$, одна единица, $R_{\max} = 1 + 5 + 8 = 14 \gt 13$ — не подходит;
• $A = 240$ ($s=4$): $33 \wedge 240 = 32$, одна единица, $R_{\max} = 1 + 4 + 8 = 13 \le 13$ — подходит.

ones = lambda x: bin(x).count('1')
for A in [0, 128, 192, 224, 240, 248, 252, 254, 255]:
    free = 8 - ones(A)
    if ones(255) + ones(211) >= ones(33 & A) + free + 8:
        print(A)      # 240
        break

Ответ: 240

Решение:

Идентификатор набирается из 8-символьного набора А, В, C, D, Е, F, G, H, значит мощность алфавита составляет $8$ символов. Алфавит содержит ровно $2^{3} = 8$ символов, поэтому на один символ достаточно $i = 3$ бита.

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

Кроме идентификатора на один объект отводится ещё 24 байта дополнительных сведений, поэтому одна запись занимает $6 + 24 = 30$ байт.

Для 20 объектов потребуется $20 \cdot 30 = 600$ байт.

import math

N = 8                         # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(15 * i / 8)     # байт на идентификатор
print(20 * (b + 24))          # ответ в байтах

Ответ: 600

Решение:

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

Пока в строке есть пять подряд идущих единиц, работает только замена (11111, 555). Так как $2022 = 5 \cdot 404 + 2$, она выполнится 404 раза, и строка станет такой: $404 \cdot 3 = 1212$ пятёрок, а затем две оставшиеся единицы.

Дальше пятёрок в строке становится на 2 меньше при каждом выполнении замены (555, 5): $1212 \to 1210 \to \ldots \to 4 \to 2$. Число 1212 чётное, поэтому процесс останавливается на двух пятёрках, а две единицы в конце уже ничем не затрагиваются.

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

s = "1" * 2022
while "11111" in s or "555" in s:
    if "11111" in s:
        s = zamenit(s, "11111", "555")
    else:
        s = zamenit(s, "555", "5")
print(s)   # 5511

Ответ: 5511

Решение:

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

Получаем $f(31, 12) = 9$ и $f(12, 2) = 19$, то есть всего $9 \cdot 19 = 171$ программ. Ответ: 171

Решение:

Приведём всё к степеням тройки: $9^{111}=3^{222}$, $8 = 22_3$. Тогда

$$N = 3^{333} - 3^{222} + \left(3^{22} - 8\right).$$

$3^{333}-3^{222} = 3^{222}\left(3^{111}-1\right)$ — это 111 двоек в разрядах с 332-го по 222-й, ниже нули.

Далее $3^{22}-8 = \left(3^{22}-3^{2}\right)+1$. Разность $3^{22}-3^{2} = 3^{2}\left(3^{20}-1\right)$ даёт 20 двоек в разрядах с 21-го по 2-й, а прибавленная единица становится младшей цифрой. Получаем 20 двоек, затем 0, затем 1.

Итого запись: 111 двоек, 200 нулей, 20 двоек, 0, 1 (всего 333 цифры). Количество двоек: $111 + 20 = 131$.

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

n = 3**333 + 3**22 - 9**111 - 8
print(to_base(n, 3).count('2'))     # 131

Ответ: 131

Решение:

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

$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

Решение:

Число 35 нечётное, поэтому работает третья строка определения, а она уменьшает аргумент сразу на 2. Значит вся цепочка вычислений идёт по нечётным числам, и формула для чётных $n$ вообще не используется. Упростим нечётную ветку:

$$F(n) = 3(n + 1) + F(n - 2) - 2 = 3n + 1 + F(n - 2), \quad n \text{ — нечётное}, \; n \gt 2.$$

База — $F(1) = 1$. Идём вверх шагами по 2:

Например, $F(3) = 3 \cdot 3 + 1 + F(1) = 10 + 1 = 11$, а последний шаг: $F(35) = 3 \cdot 35 + 1 + F(33) = 106 + 881 = 987$.

import sys
sys.setrecursionlimit(10000)

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

print(F(35))   # 987

Ответ: 987

Решение:

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

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

• между 2-м и 3-м столбцами — в строках 2–8;
• между 4-м и 5-м столбцами — в строках 5–13;
• между 6-м и 7-м столбцами — в строках 10–18;
• между 9-м и 10-м столбцами — в строках 2–9;
• между 12-м и 13-м столбцами — в строках 6–14;
• между 15-м и 16-м столбцами — в строках 9–18.

Горизонтальные внутренние стены (движение вниз запрещено) стоят между 2-й и 3-й строками в столбцах 4–8 и между 17-й и 18-й строками в столбцах 9–14.

Скопируем содержимое таблицы в текстовый файл 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 == 1 and 3 <= j <= 7) or (i == 16 and 8 <= j <= 13)

# стена справа от клетки (i, j)
def wall_right(i, j):
    return ((j == 1 and 1 <= i <= 7) or (j == 8 and 1 <= i <= 8) or
            (j == 3 and 4 <= i <= 12) or (j == 11 and 5 <= i <= 13) or
            (j == 5 and 9 <= i <= 17) or (j == 14 and 8 <= i <= 17))

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

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

Решение:

Позицию обозначаем (x, y), а следить будем за произведением $xy$. Посмотрим, как его меняет ход: $(x+1)y = xy+y \le 2xy$ и $x(y+1) = xy+x \le 2xy$ (ведь $x \ge 1$ и $y \ge 1$), а удвоение любой кучи даёт ровно $2xy$. Значит одним ходом произведение увеличивается не более чем вдвое, и удвоение кучи этот максимум как раз даёт.

Отсюда: игрок заканчивает игру своим ходом тогда и только тогда, когда $2xy \ge 144$, то есть когда $xy \ge 72$.

В начальной позиции (1, S) произведение равно $S$. После хода Пети оно не больше $2S$, после ответного хода Вани — не больше $4S$. Значит Ваня способен закончить игру своим первым ходом тогда и только тогда, когда $4S \ge 144$, то есть при $S \ge 36$.

Проверим $S = 36$. Сам Петя не выигрывает: максимум, что он может, — довести произведение до $2\cdot36 = 72$, а нужно 144. Но если он удвоит вторую кучу, возникнет позиция (1, 72) с произведением 72; Ваня удваивает её ещё раз и получает (1, 144) с произведением 144 — игра закончена, выиграл Ваня.

Проверка перебором:

N = 144

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

def win1(p):                      # ходящий выигрывает первым же ходом
    return any(x * y >= N for x, y in moves(p))

for s in range(1, 143):
    p = (1, s)
    # сам Петя выиграть не может, но неудачным ходом дарит победу Ване
    if not win1(p) and any(win1(q) for q in moves(p)):
        print(s)                  # 36
        break

Ответ: 36

Решение:

Напомним игру: позиция (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. Перед игроками две кучи камней, игроки ходят по очереди, первым ходит Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в одной из куч в два раза; позицию будем записывать парой чисел. Игра заканчивается в тот момент, когда суммарное количество камней в кучах становится не менее 59; побеждает тот, кто сделал последний ход. В начальный момент в первой куче пять камней, во второй — $S$ камней, $1 \le S \le 53$.

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

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

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

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

• $(6;\ 23)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(12;\ 23)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(13;\ 23)$ — в $(13;\ 46)$; из $(24;\ 23)$ — в $(48;\ 23)$; из $(12;\ 24)$ — в $(12;\ 48)$; из $(12;\ 46)$ — в $(13;\ 46)$);
• $(10;\ 23)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(10;\ 24)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(11;\ 24)$ — в $(11;\ 48)$; из $(20;\ 24)$ — в $(40;\ 24)$; из $(10;\ 25)$ — в $(10;\ 50)$; из $(10;\ 48)$ — в $(11;\ 48)$);
• $(5;\ 24)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(10;\ 24)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(11;\ 24)$ — в $(11;\ 48)$; из $(20;\ 24)$ — в $(40;\ 24)$; из $(10;\ 25)$ — в $(10;\ 50)$; из $(10;\ 48)$ — в $(11;\ 48)$);
• $(5;\ 46)$ — Ваня выигрывает сразу: одним ходом он получает $(5;\ 92)$, а это уже не меньше 59.

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

Ответ: 23

Решение:

Момент завершения процесса $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

Решение.

В файле 1088 рёбер. Рёбра ведут только из вершины с меньшим номером в вершину с большим, поэтому граф ациклический, а порядок 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]))

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

Решение:

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

Решение:

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

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

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

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

f = open('26.txt')
s, n = map(int, f.readline().split())
a = sorted(int(x) for x in f)

total = 0
k = 0
for x in a:
    if total + x <= s:
        total += x
        k += 1
    else:
        break

base = sum(a[:k - 1])                            # k-1 самых маленьких
big = max(x for x in a[k - 1:] if base + x <= s)  # самый большой, который ещё влезает
print(k, big)

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

3105 75

Ответ: 3105 75

Решение:

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

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

Файл A: сумма больших чисел равна $665848$; она даёт остаток $8$ при делении на 35, то есть уже не делится на 35 — уменьшать ничего не нужно, ответ $665848$.Файл B: сумма больших чисел равна $665535990$ и делится на 35. Наименьшая ненулевая разность внутри пары, не кратная 35, равна $1653$, поэтому ответ $665535990 - 1653 = 665534337$.Ответ: 665848 665534337