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

Решение:

Дизъюнкция равна нулю только тогда, когда равно нулю каждое слагаемое. Значит во всех трёх строках $z=0$, выражение $w \equiv y$ ложно, то есть $w \ne y$, и $\neg x \land y = 0$, то есть $x=1$ или $y=0$.

Наборов, удовлетворяющих сразу всем этим условиям, ровно три: $(w,x,y,z)$ равно $(0,1,1,0)$, $(1,0,0,0)$ или $(1,1,0,0)$. Строк во фрагменте тоже три, и они различны, поэтому фрагмент состоит в точности из этих наборов — остаётся понять, какой столбец какой переменной отвечает.

Так как $z=0$ везде, в столбце переменной $z$ не может быть единиц. Единицы есть в первом, втором и четвёртом столбцах, значит $z$ — третий столбец.

Столбцы $w$ и $y$ обязаны различаться всюду, где обе клетки заполнены. В третьей строке первый и второй столбцы оба равны 1, во второй строке первый и четвёртый столбцы оба равны 1 — эти пары отпадают. Остаётся, что $w$ и $y$ стоят во втором и четвёртом столбцах, а $x$ — в первом.

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

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

from itertools import permutations, product

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

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

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

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

Ответ: xyzw

Решение:

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

Заняты коды 00, 010, 011, 1001, 1010, 1011, 1100, 1101, 111.

Слова длины 1: 0 – начало 00; 1 – начало 111. Не подходят.

Слова длины 2: 00 занято; 01 – начало 010; 10 – начало 1001; 11 – начало 111. Не подходят.

Слова длины 3: 000 и 001 начинаются с кода 00; 010 и 011 заняты; 100 – начало 1001; 101 – начало 1010; 110 – начало 1100; 111 занято. Не подходят.

Слова длины 4, начинающиеся с 0, невозможны: любое из них начинается с 00, 010 или 011. Наименьшее подходящее слово длины 4 – 1000: ни одно из имеющихся кодовых слов не является его началом, и оно само не является началом ни одного из них.

Ответ: 1000.

Решение:

Пусть $r=N\bmod 4$ — последняя цифра четверичной записи $N$. Разберём, что приписывается справа в каждом случае.

• $r=0$: приписываются две последние четверичные цифры, то есть запись удлиняется на два разряда, а приписанное значение равно $N\bmod 16$. Значит $R=16N+(N\bmod 16)$.
• $r=1$: $2r=2=2_4$ — один разряд, поэтому $R=4N+2$.
• $r=2$: $2r=4=10_4$ — два разряда, поэтому $R=16N+4$.
• $r=3$: $2r=6=12_4$ — два разряда, поэтому $R=16N+6$.

Сверим с примерами из условия: $N=11$, $r=3$, $R=16\cdot 11+6=182$; $N=12$, $r=0$, $R=16\cdot 12+12=204$. Совпадает.

Ключевое наблюдение: только при $r=1$ число увеличивается в 4 раза, во всех остальных случаях — в 16 раз.

Нужно наименьшее $N$, при котором $R\ge 1088$. Рассмотрим все четыре случая.

• $r=1$: $4N+2\ge 1088\Rightarrow N\ge 272$. Наименьшее число вида $4k+1$ — это $N=273$.
• $r=2$: $16N+4\ge 1088\Rightarrow N\ge 68$. Наименьшее число вида $4k+2$ — это $N=70$, $R=1124$.
• $r=3$: $16N+6\ge 1088\Rightarrow N\ge 68$. Наименьшее число вида $4k+3$ — это $N=71$, $R=1142$.
• $r=0$: $N=64$ даёт $R=1024$ — мало; следующее кратное четырём $N=68$ даёт $R=16\cdot 68+4=1092\ge 1088$ — подходит.

Обратим внимание на «ловушку»: $N=66$ даёт $R=1060$, а $N=67$ даёт $R=1078$ — оба меньше 1088. Наименьшее из чисел 273, 70, 71, 68 — это 68.

def alg(n):
    q = ''
    m = n
    while m:
        q = str(m % 4) + q
        m //= 4
    if n % 4 == 0:
        q += q[-2:]
    else:
        t = (n % 4) * 2
        q += str(t) if t < 4 else str(t // 4) + str(t % 4)
    return int(q, 4)

print(min(n for n in range(1, 1000) if alg(n) >= 1088))

Ответ: 68

Решение:

После Направо 60 голова смотрит под углом $30^{\circ}$ к оси $Ox$. В цикле Вперёд 8 поднимает Черепаху в точку $(4\sqrt{3};\,4)$, Направо 120 разворачивает её вниз, Вперёд 4 возвращает на ось, а Направо 240 восстанавливает исходное направление. Значит каждый повтор рисует прямоугольный треугольник с катетами $4\sqrt{3}$ и 4 и гипотенузой 8, опирающийся на ось $Ox$; четыре зубца доводят Черепаху до точки $(16\sqrt{3};\,0)$.

Дальше Направо 120 направляет голову вниз, Вперёд 2 даёт $(16\sqrt{3};\,-2)$, Направо 90 и Вперёд $16\sqrt{3}$ — точку $(0;-2)$, а Направо 90 Вперёд 2 замыкает линию в начале координат.

Итак, фигура — прямоугольник $[0;\,16\sqrt{3}]\times[-2;\,0]$ с четырьмя треугольными зубцами сверху; $16\sqrt{3}\approx 27{,}71$. Фигура невыпуклая, поэтому в программе считаем методом луча и отдельно отбрасываем точки, лежащие на ломаной:

from math import sin, cos, radians, hypot

P = [(0.0, 0.0)]
x = y = 0.0
a = 90.0

def F(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):
    global a
    a -= m

R(60)
for i in range(4):
    F(8); R(120); F(4); R(240)
R(120); F(2); R(90); F(16 * 3 ** 0.5); R(90); F(2)

def on_line(px, py):          # точка лежит на самой ломаной?
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        L = hypot(x2 - x1, y2 - y1)
        d = ((x2 - x1) * (py - y1) - (y2 - y1) * (px - x1)) / L
        if abs(d) < 1e-6 and min(x1, x2) - 1e-6 <= px <= max(x1, x2) + 1e-6 \
                         and min(y1, y2) - 1e-6 <= py <= max(y1, y2) + 1e-6:
            return True
    return False

def inside(px, py):           # луч вправо: чётность числа пересечений
    c = False
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        if (y1 > py) != (y2 > py):
            if x1 + (py - y1) * (x2 - x1) / (y2 - y1) > px:
                c = not c
    return c

xs = [p[0] for p in P]; ys = [p[1] for p in P]
print(sum(inside(px, py) and not on_line(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)))

Программа печатает 91. По строкам это: при $y=-1$ — 27 точек ($x=1,\dots,27$); при $y=0$ — тоже 27 (отрезок оси проходит внутри фигуры, а «впадины» $4\sqrt{3}$, $8\sqrt{3}$, $12\sqrt{3}$ не целые); при $y=1$ — 20, при $y=2$ — 12, при $y=3$ — 5. Итого $27+27+20+12+5=91$.

Ответ: 91

Решение:

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

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

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

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

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

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

Ответ: 128

Решение:

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

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

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

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

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

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

from itertools import product

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

Ответ: 2969

Решение:

В каждой строке таблицы семь чисел. Первое условие означает, что набор кратностей значений в строке равен $2+2+1+1+1$: ровно два значения встречаются по два раза, а оставшиеся три числа попарно различны, то есть всего в строке ровно пять различных значений.

«Повторяющиеся числа» — это те четыре ячейки, которые образуют пары. Если пары составлены из чисел $a$ и $b$, то их среднее равно $\frac{a+a+b+b}{4}=\frac{a+b}{2}$, и его нужно сравнить со средним всех семи чисел строки.

Удобнее всего открыть csv-версию файла программой: для каждой строки построить счётчик значений, проверить кратности и сравнить два средних.

from collections import Counter

count = 0
for line in open('9.csv', encoding='utf-8'):
    row = [int(x) for x in line.split(';')]
    c = Counter(row)
    pairs = [v for v in c if c[v] == 2]
    if len(pairs) == 2 and len(c) == 5:
        rep = [x for x in row if c[x] == 2]
        if sum(rep) / len(rep) < sum(row) / len(row):
            count += 1

print(count)

Условие len(pairs) == 2 and len(c) == 5 как раз и означает «две пары плюс три различных числа». Программа просматривает все 16 000 строк и находит 83 подходящие.

Ответ: 83

Решение:

Левые два байта у всех адресов сети одинаковы: $126 = 01111110_2$ даёт 6 единиц, $255$ даёт 8. Значит $L = 14$ всегда.

Маска 255.255.240.0 $= \ldots.11110000.00000000_2$: в третьем байте зафиксирована старшая тетрада числа $A$, младшая тетрада свободна, четвёртый байт свободен целиком.

Наибольшее возможное число единиц в правых двух байтах равно

$$R_{\max} = \nu(A \wedge 240) + 4 + 8,$$

где $\nu(x)$ — количество единиц в двоичной записи $x$. Условие «для всех адресов $L\ge R$» равносильно $14 \ge \nu(A \wedge 240) + 12$, то есть в старшей тетраде $A$ не более двух единиц.

Чтобы $A$ было максимальным, берём наибольшую тетраду с двумя единицами — $1100_2 = 12$ (тетрады 1101, 1110, 1111 дают три и более единиц), а младшую тетраду делаем максимальной: $1111_2$. Получаем $A = 11001111_2 = 207$.

ones = lambda x: bin(x).count('1')
for A in range(255, -1, -1):
    if all(ones(126) + ones(255) >= ones((A & 240) | y) + ones(b4)
           for y in range(16) for b4 in range(256)):
        print(A)      # 207
        break

Ответ: 207

Решение:

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

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

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

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

Ответ: 4352

Решение:

Команда заменить(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

Решение:

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

$12yx9_{21} = 1 \cdot 21^4 + 2 \cdot 21^3 + y \cdot 21^2 + x \cdot 21 + 9$,

$36y99_{21} = 3 \cdot 21^4 + 6 \cdot 21^3 + y \cdot 21^2 + 9 \cdot 21 + 9$.

Сумма: $S = 4 \cdot 21^4 + 8 \cdot 21^3 + 2y \cdot 21^2 + (x + 9) \cdot 21 + 18$.

Найдём остатки степеней по модулю 18: $21 \equiv 3$, $21^2 = 441 \equiv 9$, $21^3 \equiv 3 \cdot 9 = 27 \equiv 9$, $21^4 \equiv 9 \cdot 9 = 81 \equiv 9 \pmod{18}$. Тогда

$S \equiv 4 \cdot 9 + 8 \cdot 9 + 2y \cdot 9 + 3(x + 9) + 18 \equiv 36 + 72 + 18y + 3x + 27 + 18 \equiv 3x + 9 \pmod{18}$,

потому что $36$, $72$, $18y$ и $18$ кратны 18. Слагаемое с $y$ исчезло — значит остаток и вправду не зависит от $y$, как и требуется в условии.

Условие $3x + 9 \equiv 0 \pmod{18}$ равносильно $x + 3 \equiv 0 \pmod 6$, то есть $x \equiv 3 \pmod 6$. В алфавите 21-ричной системы (цифры $0 \ldots 20$) это $x \in \{3,\ 9,\ 15\}$; наименьшее — $x = 3$.

При $x = 3$ и $y = 5$: $S = 4 \cdot 194481 + 8 \cdot 9261 + 10 \cdot 441 + 12 \cdot 21 + 18 = 856692$, и $856692 : 18 = 47594$.

def num(digits, base):
    v = 0
    for d in digits:
        v = v * base + d
    return v

good = [x for x in range(21)
        if all((num([1,2,y,x,9], 21) + num([3,6,y,9,9], 21)) % 18 == 0
               for y in range(21))]
x = min(good)
print(good, x, (num([1,2,5,x,9], 21) + num([3,6,5,9,9], 21)) // 18)

Ответ: 47594

Решение:

Дизъюнкция $(\text{ДЕЛ}(x, 2) \rightarrow \neg \text{ДЕЛ}(x, 3)) \lor (x + A \ge 100)$ ложна только тогда, когда ложны оба слагаемых.

Первая скобка — импликация; она ложна ровно тогда, когда $x$ делится на 2 и при этом не выполняется $\neg \text{ДЕЛ}(x, 3)$, то есть когда $x$ делится и на 2, и на 3 — иначе говоря, когда $x$ кратно 6.

Значит вторая скобка $x + A \ge 100$ обязана быть истинной для всех $x$, кратных 6 (при остальных $x$ формула истинна и без неё).

Условие $x + A \ge 100$ тем жёстче, чем меньше $x$. Наименьшее натуральное кратное шести — это $x = 6$, откуда $6 + A \ge 100$, то есть $A \ge 94$.

При $A = 94$ для любого кратного 6 числа $x \ge 6$ выполнено $x + 94 \ge 100$, значит наименьшее подходящее значение равно 94.

for A in range(1, 200):
    if all((x % 2 != 0 or x % 3 != 0) or x + A >= 100
           for x in range(1, 10000)):
        print(A)   # 94
        break

Ответ: 94

Решение:

Число 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

Решение:

Задача решается в два прохода. Сначала находим порог — максимальный элемент всей последовательности, кратный 3; в этом файле он равен 999. Затем перебираем пары соседних элементов и отбираем те, у которых хотя бы одно число делится на 3, а сумма пары не превосходит найденного порога.

Проверка делимости на 3 через остаток в Python корректна и для отрицательных чисел: $x \bmod 3 = 0$ тогда и только тогда, когда $x$ кратно 3.

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

m = max(x for x in a if x % 3 == 0)   # 999 - порог

count = 0
best = None
for x, y in zip(a, a[1:]):
    if (x % 3 == 0 or y % 3 == 0) and x + y <= m:
        count += 1
        if best is None or x + y > best:
            best = x + y

print(count, best)   # 2439 998

Подходящих пар 2439, наибольшая из их сумм равна 998 (это меньше порога 999, поэтому условие выполнено).

Ответ: 2439 998

Решение:

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

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

В приложенном файле поле имеет размер $16\times16$. Единственная внутренняя стена (утолщённая линия) — горизонтальная, между 6-й и 7-й строками в столбцах с 5-го по 10-й: в эти клетки 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 == 5 and 4 <= j <= 9

# стена справа от клетки (i, j) — вертикальных внутренних стен нет
def wall_right(i, j):
    return False

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(MN[N - 1][N - 1], MX[N - 1][N - 1])

Программа выводит 518 758: минимальная сумма равна 518, максимальная — 758. В ответе сначала записывается минимальная сумма, затем максимальная.

Ответ: 518 758

Ваня выигрывает первым ходом, если после хода Пети из позиции (a, b) он может получить сумму не менее 154, то есть если max(a + b + 4, 3a + b, a + 3b) ≥ 154.

При S ≤ 47 Петя не может выиграть первым ходом: наибольшая достижимая им сумма равна max(33 + S, 11 + 3S) < 154.

Проверяем S по возрастанию. При S = 15 после любого хода Пети (30, 30, 48 или 56 камней в сумме) Ваня не может набрать 154: наибольшая сумма получается из (11, 45) и равна 11 + 135 = 146.

При S = 16 Петя может неудачно сходить в позицию (11, 48). Тогда Ваня утраивает вторую кучу: (11, 144), сумма 155 ≥ 154, и Ваня выигрывает.

Ответ: 16.

Решение:

Напомним игру: в куче $S$ камней, своим ходом игрок добавляет в кучу один или пять камней либо увеличивает её в четыре раза; выигрывает тот, после чьего хода в куче окажется не менее 205 камней.

Самый «сильный» ход — умножение, поэтому выиграть одним ходом можно тогда и только тогда, когда $4S \ge 205$, то есть при $S \ge 52$ (прибавление камней помогло бы лишь при $S \ge 200$).

Найдём проигрышную позицию — кучу, из которой ходящий сам не выигрывает, но любой его ход отдаёт победу сопернику. Слабейший ход «+1» тоже должен попадать в зону $\ge 52$, поэтому $S \ge 51$; вместе с $S \le 51$ это даёт единственную кучу — 51 камней. Проверим её: из 51 камней получаются 52, 56 и 204 камней — все меньше 205, так что сам ходящий не выигрывает; но каждое из этих чисел не меньше 52, поэтому соперник следующим ходом доводит кучу до 205.

Итак, Петя должен своим первым ходом получить ровно 51 камней:

• ходом «+1»: $S = 50$;
• ходом «+5»: $S = 46$;
• ход «×4» не подходит: 51 не делится на 4.

Оба значения меньше 52, то есть за один ход Петя не выигрывает; меньших подходящих значений нет.

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

N = 205

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

def win1(s):                      # выигрыш первым же ходом
    return any(t >= N for t in moves(s))

def lose1(s):                     # ходящий проигрывает: любой его ход даёт сопернику победу
    return not win1(s) and all(win1(t) for t in moves(s))

def win2(s):                      # первым ходом не выигрывает, вторым — выигрывает
    return not win1(s) and any(lose1(t) for t in moves(s))

print([s for s in range(1, N) if win2(s)][:2])   # [46, 50]

Ответ: 46 50

Решение:

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

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

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

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

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

• $99$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $100$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $101$ — в $202$; из $200$ — в $201$);
• $196$ — Ваня выигрывает сразу: одним ходом он получает $392$, а это уже не меньше 201.

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

Ответ: 98

Решение:

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

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

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

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

finish = {}
for i in sorted(data):
    dur, deps = data[i]
    finish[i] = max([finish[d] for d in deps], default=0) + dur

print(max(finish.values()))

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

Ответ: 14

Решение.

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

Решение:

Алфавитный порядок для наших символов — это X, Y, Z. Значит «обратный алфавитный порядок» означает, что каждый следующий символ не идёт в алфавите позже предыдущего: $s_i\le s_{i-1}$ (нестрогое неравенство, потому что повторы разрешены). Для символов это обычное сравнение строк в Python.

Достаточно одного прохода по файлу: храним длину текущей подходящей серии cur. Если очередной символ не больше предыдущего, серия продолжается (cur += 1), иначе серия обрывается и новая начинается с текущего символа (cur = 1). Максимум из всех значений cur и есть ответ.

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

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

print(mx)

Программа выводит 19: в файле есть 19 подряд идущих символов, образующих невозрастающую цепочку (например, несколько Z, затем несколько Y, затем несколько X), а 20 таких подряд нет.

Ответ: 19

Решение:

Переведём маску 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

Решение:

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

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

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

Первая строка прилагаемого файла содержит $S$ и $N$, далее идут $N$ объёмов посылок.

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)

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

629 50

Ответ: 629 50

Решение:

Нужно выбрать три показания с номерами минут $i \lt j \lt l$ так, чтобы $j - i \ge K$ и $l - j \ge K$, а сумма $a_i + a_j + a_l$ была наибольшей. Перебор всех троек — это $O(N^3)$, для файла B с сотнями тысяч показаний он не закончится никогда, поэтому нужен линейный алгоритм.

Идея: зафиксируем среднее из трёх чисел. Если средним выбрано показание с номером $j$, то левое число можно брать любое с номером не больше $j-K$, а правое — любое с номером не меньше $j+K$. Обе части независимы, поэтому выгоднее всего взять максимум на левом префиксе и максимум на правом суффиксе. Оба массива максимумов считаются заранее одним проходом:

• pref[i] — наибольшее из показаний с номерами от 0 до i;
• suf[i] — наибольшее из показаний с номерами от i до конца.

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

def solve(name):
    f = open(name)
    k = int(f.readline())
    n = int(f.readline())
    a = [int(f.readline()) for i in range(n)]

    pref = [0] * n
    pref[0] = a[0]
    for i in range(1, n):
        pref[i] = max(pref[i - 1], a[i])

    suf = [0] * n
    suf[n - 1] = a[n - 1]
    for i in range(n - 2, -1, -1):
        suf[i] = max(suf[i + 1], a[i])

    best = -10**18
    for j in range(k, n - k):
        best = max(best, pref[j - k] + a[j] + suf[j + k])
    print(best)

solve('27_A.txt')
solve('27_B.txt')

На типовом примере из условия программа выдаёт 170 — значит, она реализует именно требуемое правило. Для файла A получаем 189536, для файла B — 17210.

Ответ: 189536 17210