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

Решение:

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

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

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

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

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

from itertools import product, permutations

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

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

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

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

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

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

Ответ: xwzy

Решение:

«Есть в наличии на складах» означает разность между тем, что поступило с производства, и тем, что выдано покупателям, посчитанную по всем операциям до конца указанного дня включительно.

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

Шаг 2. В таблице «Продукты» находим строку с наименованием «шиповник» и запоминаем её артикул.

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

Шаг 4. Двумя формулами СУММЕСЛИМН считаем сумму по полю «Количество, кг» отдельно для типа операции «Поступило с производства» и для типа «Выдано покупателю»: получается 72 кг и 31 кг. Остаток на складах: $72 - 31 = 41$ кг.

Ответ: 41

Решение:

Условие Фано означает, что ни одно кодовое слово не является началом другого. Перебираем кандидатов для буквы И по возрастанию длины, а внутри одной длины — по возрастанию числового значения.

Длина 1. Слово 0 — начало кода 000 (буква А); слово 1 — начало кода 101 (буква З). Не подходят.

Длина 2. Слово 00 — начало 000; 01 — начало 010 (Б); 10 — начало 101 (З); 11 — начало 11011 (Е) и 11010 (Ж). Не подходит ни одно.

Длина 3. Слово 000 занято буквой А; 001 — начало кода 00100 (Г); 010 занято буквой Б; 011 — начало кода 01111 (Д); 100 — начало кода 10001 (В); 101 занято буквой З; 110 — начало кодов 11011 и 11010. Остаётся слово 111: ни один имеющийся код с него не начинается и ни один код не является его началом. Оно подходит.

Ответ: 111

Решение:

Обозначим $M=N-(N\bmod 8)+(N\bmod 2)$ — результат первого шага. Число $N-(N\bmod 8)$ кратно 8, а прибавляется 0 для чётного $N$ и 1 для нечётного. Значит, $M$ — это число вида $8k$ или $8k+1$, и любое такое число достижимо.

Пусть в двоичной записи $M$ ровно $k$ единиц и $p=k\bmod 2$. На шаге 3а справа приписывается $p$, после чего сумма цифр $k+p$ чётна, поэтому на шаге 3б приписывается 0. Значит $R=4M+2p$.

Нужно наименьшее $R\gt 90$. Так как $p\le 1$, из $4M+2p\gt 90$ следует $4M\ge 89$, то есть $M\ge 23$. Ближайшие подходящие значения $M$ — это 24 и 25.

• $M=24=11000_2$: единиц две, $p=0$, запись $11000\to 110000\to 1100000$, $R=96\gt 90$;
• $M=25=11001_2$: единиц три, $p=1$, $R=4\cdot 25+2=102$.

Все более крупные $M$ дают $R\ge 4\cdot 32=128$. Наименьшее значение $R$, большее 90, равно 96.

def alg(n):
    b = bin(n - n % 8 + n % 2)[2:]
    b += str(sum(map(int, b)) % 2)
    b += str(sum(map(int, b)) % 2)
    return int(b, 2)

print(min(r for r in {alg(n) for n in range(1, 1000)} if r > 90))

Ответ: 96

Решение:

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

Цикл замыкается за два повтора: рисуется прямоугольник $30\times 40$, повёрнутый на $30^{\circ}$, с вершинами $(100;100)$, $(100+15\sqrt{3};\,85)$, $(80+15\sqrt{3};\,85-20\sqrt{3})$, $(80;\,100-20\sqrt{3})$, то есть примерно $(100;100)$, $(125{,}98;\,85)$, $(105{,}98;\,50{,}36)$, $(80;\,65{,}36)$.

Стороны наклонены под «неудобными» углами, поэтому считаем программой. Фигура выпуклая и обходится по часовой стрелке: точка лежит строго внутри, если для всех четырёх сторон косое произведение $(x_2-x_1)(y-y_1)-(y_2-y_1)(x-x_1)$ отрицательно.

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

Программа печатает 1200. Для контроля: площадь прямоугольника равна $30\cdot 40=1200$, а на границе лежит единственная целая точка — вершина $(100;100)$. Ответ: 1200

Решение:

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

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

Файл должен поместиться в отведённую память: $3300000 \cdot i \le 10813440$, откуда $i \le \frac{10813440}{3300000} \approx 3{,}28$.

Число бит на пиксель — целое, поэтому наибольшее подходящее значение $i = 3$.

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

W, H = 1000, 3300
V = 1320 * 1024 * 8  # отведённая память в битах
i = V // (W * H)     # максимальное целое число бит на пиксель
print(i, 2 ** i)     # 3 8

Ответ: 8

Решение:

Кодовое слово состоит из трёх позиций. Буква К должна встретиться ровно один раз, поэтому сначала выберем для неё позицию — это можно сделать $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

Решение:

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

Маска 255.255.255.192 в двоичном виде — 11111111.11111111.11111111.11000000, в ней 26 единиц. Значит, первые 26 битов адреса зафиксированы, а последние 6 свободны и дают $2^6 = 64$ адреса. Адрес сети: 128 & 192 = 10000000 & 11000000 = 10000000, то есть сеть 132.71.21.128, а её неизменяемая часть в двоичной записи — 10000100.01000111.00010101.10.

Сосчитаем единицы в этой фиксированной части: в 132 их 2, в 71 — 4, в 21 — 3, в двух старших битах последнего байта — 1, всего $2+4+3+1 = 10$. Эти десять единиц есть у любого адреса сети, убрать их нельзя. Остальные 6 битов мы выбираем сами, и чтобы сумма единиц была наименьшей, все их делаем нулями — получается сам адрес сети 132.71.21.128 с суммой единиц 10.

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

from itertools import product

def to_bits(s):
    return ''.join(format(int(x), '08b') for x in s.split('.'))

ip = to_bits('132.71.21.128')
mask = to_bits('255.255.255.192')
k = mask.count('1')
head = ip[:k]
addrs = [head + ''.join(t) for t in product('01', repeat=32 - k)]
print(min(a.count('1') for a in addrs))

Ответ: 10

Решение:

Пароль набирается из 52-символьного набора строчных и прописных латинских букв, значит мощность алфавита составляет $52$ символа. На один символ нужно минимальное целое $i$, при котором $2^i \ge 52$. Так как $2^{5} = 32 \lt 52 \lt 64 = 2^{6}$, получаем $i = 6$ бит.

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

На всех пользователей отведено одинаковое число байт, поэтому на одного пользователя приходится $500 : 20 = 25$ байт.

Из них 6 байт занимает пароль, значит на дополнительные сведения остаётся $25 - 6 = 19$ байт.

import math

N = 52                        # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(7 * i / 8)      # байт на пароль
print(500 // 20 - b)          # доп. сведения, байт

Ответ: 19

Решение:

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

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

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

def rabota(s):
    while "12" in s or "3322" in s or "2222" in s:
        if "12" in s:
            s = zamenit(s, "12", "33")
        if "2222" in s:
            s = zamenit(s, "2222", "1")
        if "3322" in s:
            s = zamenit(s, "3322", "21")
    return s

for n in range(4, 10000):
    s = rabota("1" + "2" * n)
    if sum(int(c) for c in s) == 218:
        print(n, s)
        break
# 177 333...3332

Первое подходящее значение — $n = 177$: программа превращает строку в 72 тройки и одну двойку, сумма цифр равна $3 \cdot 72 + 2 = 218$. Ответ: 177

Решение:

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

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

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

Решение:

Основание системы счисления 15, а делитель $14 = 15-1$. Так как $15 \equiv 1 \pmod{14}$, любое число сравнимо по модулю 14 с суммой своих 15-ричных цифр. Поэтому сумма делится на 14 тогда и только тогда, когда на 14 делится сумма цифр обоих слагаемых.

• $135x7_{15}$: $1+3+5+x+7 = 16 + x$;
• $7x531_{15}$: $7+x+5+3+1 = 16 + x$.

Всего $32 + 2x \equiv 0 \pmod{14}$, то есть $2x \equiv 10 \pmod{14}$, или $x \equiv 5 \pmod 7$. В алфавите 15-ричной системы подходят $x = 5$ и $x = 12$; наименьшее — $x = 5$.

Подставим $x = 5$: $13557_{15} = 61957$, $75531_{15} = 372421$, сумма равна $434378$, а $434378 : 14 = 31027$.

b = 15

def num(ds):
    n = 0
    for d in ds:
        n = n * b + d
    return n

for x in range(b):                       # ищем наименьшее x
    s = num([1, 3, 5, x, 7]) + num([7, x, 5, 3, 1])
    if s % 14 == 0:
        print(x, s // 14)                # 5 31027
        break

Ответ: 31027

Решение:

Отрицание всей формулы истинно, когда конъюнкция под ним ложна. Значит для любого натурального $x$ должно быть не так, что одновременно

• (а) $\text{ТРЕУГ}(x, 12, 20) \equiv \neg\left(\text{МАКС}(x, 5) \gt 28\right)$ истинно;
• (б) $\text{ТРЕУГ}(x, A, 3)$ истинно.

Разбираем (а). Неравенство треугольника для сторон $x$, 12 и 20 даёт $x + 12 \gt 20$ и $12 + 20 \gt x$, то есть $\text{ТРЕУГ}(x, 12, 20)$ истинно при $9 \leq x \leq 31$.

Далее, $\text{МАКС}(x, 5) \gt 28$ означает $x \gt 28$, поэтому $\neg\left(\text{МАКС}(x, 5) \gt 28\right)$ истинно при $x \leq 28$.

Эквивалентность (а) истинна там, где обе части совпадают:

• $x \leq 8$: ложь и истина — (а) ложно;
• $9 \leq x \leq 28$: истина и истина — (а) истинно;
• $29 \leq x \leq 31$: истина и ложь — (а) ложно;
• $x \geq 32$: ложь и ложь — (а) истинно.

Разбираем (б). На всех $x$, где (а) истинно, нужно, чтобы $\text{ТРЕУГ}(x, A, 3)$ было ложно. Для сторон $x$, $A$ и 3 треугольник существует, если $x + 3 \gt A$, $A + 3 \gt x$ и $x + A \gt 3$.

При $9 \leq x \leq 28$ и натуральном $A$ условие $x + A \gt 3$ выполнено всегда, поэтому треугольник не существует ровно тогда, когда $A \geq x + 3$ или $A \leq x - 3$.

Это должно выполняться для каждого $x$ от 9 до 28. Самое жёсткое ограничение даёт $x = 9$: нужно $A \leq 6$ либо $A \geq 12$. Но $x = 28$ требует $A \leq 25$ либо $A \geq 31$, а при $A \geq 31$ уже нарушается случай $x \geq 32$: например, при $x = 32$ и $A = 31$ все три неравенства треугольника выполняются. Остаётся ветвь $A \leq 6$, и она годится сразу для всех $x \geq 9$, так как тогда $A \leq x - 3$.

Наибольшее подходящее натуральное число — $A = 6$ (при $A = 7$ и $x = 9$ стороны 9, 7 и 3 образуют треугольник, и формула ложна).

def treug(a, b, c):
    a, b, c = sorted((a, b, c))
    return a > 0 and a + b > c

def maks(a, b):
    return a if a > b else b

def ok(A):
    return all(not ((treug(x, 12, 20) == (not (maks(x, 5) > 28))) and treug(x, A, 3))
               for x in range(1, 1000))

print(max(A for A in range(1, 100) if ok(A)))

Ответ: 6

Решение:

Сначала найдём $F(2)$, которое входит в правило для нечётных $n$: число 2 чётное и $2 \gt 1$, поэтому $F(2) = 3 \cdot F(1) = 3$. Значит при нечётном $n \gt 1$ правило принимает вид $F(n) = 5n + F(n-1) + 3$.

Каждое значение зависит только от предыдущего, поэтому просто идём по возрастанию $n$:

$F(1) = 1$, $F(2) = 3 \cdot 1 = 3$, $F(3) = 5 \cdot 3 + 3 + 3 = 21$, $F(4) = 3 \cdot 21 = 63$, $F(5) = 5 \cdot 5 + 63 + 3 = 91$, $F(6) = 3 \cdot 91 = 273$ и так далее.

Последний шаг: $F(23) = 5 \cdot 23 + F(22) + 3 = 115 + 2214153 + 3 = 2214271$.

from functools import lru_cache

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

print(F(23))   # 2214271

Ответ: 2214271

Решение:

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

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

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

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

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

print(count, best)   # 1020 17197

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

Решение:

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

Пусть $a_{ij}$ — номинал монеты в клетке, $M_{ij}$ и $m_{ij}$ — максимальная и минимальная накопленные суммы. Тогда $M_{ij}=\max(M_{i-1,j},\,M_{i,j-1})+a_{ij}$ и $m_{ij}=\min(m_{i-1,j},\,m_{i,j-1})+a_{ij}$, причём соседняя клетка учитывается только тогда, когда между ней и текущей нет стены. Для левой верхней клетки $M_{11}=m_{11}=a_{11}$.

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

В приложенном файле поле имеет размер $20\times20$. Вертикальные стены (нельзя идти вправо) стоят:

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

Горизонтальные стены (нельзя идти вниз) стоят между 4-й и 5-й строками в столбцах 16–19, между 11-й и 12-й строками в столбцах 10–12, между 16-й и 17-й строками в столбцах 2–4, между 18-й и 19-й строками в столбцах 13–17 и между 19-й и 20-й строками в столбцах 5–7.

Скопируем содержимое таблицы в текстовый файл 18.txt (числа разделены пробелами или знаками табуляции) и обработаем его программой.

f = open('18.txt')
a = [[int(x) for x in s.split()] for s in f]
N = len(a)

# стена снизу от клетки (i, j); строки и столбцы нумеруются с нуля
def wall_down(i, j):
    return ((i == 3 and 15 <= j <= 18) or (i == 10 and 9 <= j <= 11) or
            (i == 15 and 1 <= j <= 3) or (i == 17 and 12 <= j <= 16) or
            (i == 18 and 4 <= j <= 6))

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

MX = [[0] * N for i in range(N)]   # максимум, накопленный к клетке
MN = [[0] * N for i in range(N)]   # минимум
for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            MX[i][j] = MN[i][j] = a[0][0]
            continue
        v = []
        if i > 0 and not wall_down(i - 1, j):
            v.append((MX[i - 1][j], MN[i - 1][j]))
        if j > 0 and not wall_right(i, j - 1):
            v.append((MX[i][j - 1], MN[i][j - 1]))
        MX[i][j] = max(x for x, y in v) + a[i][j]
        MN[i][j] = min(y for x, y in v) + a[i][j]

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

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

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

Ответ: 2255 820

Решение:

Позицию обозначаем (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

Решение:

Сначала опишем позиции, из которых игра заканчивается одним ходом. Из кучи в $n$ камней ($n \le 128$) ходящий выигрывает сразу, если $n + 1 \ge 129$ или $2n \ge 129$, то есть при $n \ge 65$. Значит, при $n$ от 65 до 128 ходящий побеждает немедленно.

Теперь найдём позицию, в которую Пете выгодно попасть после первого хода. Из кучи в 64 камня возможны только 65 и 128 — обе позиции выигрышны для соперника, поэтому 64 проигрышна для того, кто из неё ходит. Более того, 64 — единственная такая позиция: чтобы все ходы вели в диапазон 65–128, нужно $n + 1 \ge 65$, то есть $n \ge 64$, и одновременно $n \le 64$, иначе ходящий выиграл бы сам.

Итак, стратегия Пети — первым ходом получить ровно 64 камня, после чего Ваня вынужденно отдаёт позицию 65 или 128, и Петя добивает вторым ходом (из 65 удвоением до 130, из 128 добавлением камня до 129). Попасть в 64 можно из $S = 63$ (добавить камень) и из $S = 32$ (удвоить). Оба значения не превосходят 64, поэтому первым ходом Петя выиграть не может — второе условие задачи тоже выполнено.

Записываем найденные значения в порядке возрастания: 32 и 63.

def win_now(s):
    return s + 1 >= 129 or 2 * s >= 129

res = []
for s in range(1, 129):
    if win_now(s):                       # Петя выигрывает сразу — не подходит
        continue
    for m in (s + 1, 2 * s):             # ход Пети
        if not win_now(m) and all(win_now(k) for k in (m + 1, 2 * m)):
            res.append(s)
            break
print(res[:2])                           # [32, 63]

Ответ: 32 63

Решение:

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

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

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

def moves(s):
    return [s + 1, 2 * s]

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

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

• $87$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $88$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $89$ — в $178$; из $176$ — в $177$);
• $172$ — Ваня выигрывает сразу: одним ходом он получает $344$, а это уже не меньше 177.

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

Ответ: 86

Решение:

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

Решение:

В файле записана одна длинная строка из букв T, U, V, W, X, Y, Z (десять миллионов символов). Нужен самый длинный непрерывный кусок этой строки, в котором буква T встречается ровно 100 раз.

Ключевая идея: любой такой кусок содержит ровно сто подряд идущих (по порядку следования в строке) букв T, а между ними и по краям стоят произвольные другие буквы. Значит, достаточно перебрать все окна из 100 подряд идущих букв T и для каждого окна раздвинуть границы максимально широко — влево до предыдущей буквы T (не захватывая её) и вправо до следующей буквы T (тоже не захватывая её). Если слева или справа буквы T больше нет, границей служит начало или конец строки. Из всех полученных длин берём наибольшую.

Для этого сначала выпишем в список номера позиций всех букв T, а затем пройдёмся по нему окном ширины 100.

s = open('24.txt').read().strip()
p = [i for i in range(len(s)) if s[i] == 'T']

best = 0
for k in range(len(p) - 99):
    # окно из ста букв T: p[k] … p[k+99]
    left = p[k - 1] + 1 if k > 0 else 0
    right = p[k + 100] - 1 if k + 100 < len(p) else len(s) - 1
    best = max(best, right - left + 1)

print(best)

Программа работает за один проход по списку позиций, то есть за $O(N)$, и выводит 133. Это означает, что в найденном фрагменте кроме ста букв T стоят ещё 33 буквы других видов. Ответ: 133

Решение:

Перебирать все числа до $10^{10}$ не нужно: подходящие числа делятся на 1917, поэтому достаточно пройти по кратным — $1917, 2\cdot1917, 3\cdot1917, \ldots$ Их примерно в 1917 раз меньше.

Проверку маски удобно свести к регулярному выражению: символ «?» — это ровно один любой символ, то есть ., а символ «*» — любая (в том числе пустая) последовательность, то есть .*. Маска 3?12?14*5 превращается в шаблон 3.12.14.*5, и число подходит, если запись числа целиком совпадает с шаблоном.

Маска содержит два символа «?» (по одной произвольной цифре каждый) и одну «звёздочку», которая может раскрыться и в пустую строку — поэтому подходят числа разной длины, вплоть до $10^{10}$.

import re

pattern = '3.12.14.*5'
d = 1917
k = d
while k <= 10 ** 10:
    if re.fullmatch(pattern, str(k)):
        print(k, k // d)
    k += d

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

351261495 183235
3212614035 1675855
3412614645 1780185
3712414275 1936575
3912414885 2040905

Ответ: 351261495 183235 3212614035 1675855 3412614645 1780185 3712414275 1936575 3912414885 2040905

Решение:

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

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

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

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

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

2172 50

Ответ: 2172 50

Решение:

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