Вариант 4 · Июль 2026

Решение:
Проанализировав граф, определим, что пункту D соответствует номер 7 (это единственный узел, чьими соседями являются вершины со степенями 2, 2 и 3). Исходя из этого, пункту F присваиваем номер 8. Далее находим вершину G — это номер 1 (поскольку у вершины H есть сосед со степенью 2), следовательно, для H получаем номер 6. Таким образом, пункту B соответствует номер 3. Вершина E, связанная с G и имеющая соседа со степенью 2, сопоставляется с номером 2.

Ответ: 34

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

Решение:

Дизъюнкция равна нулю только тогда, когда равно нулю каждое слагаемое. Значит во всех трёх строках $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 ткани», о модели — по полю «ID товара».

Шаг 1. В таблице «Ткани» включаем фильтр: Цвет = «красный», Сырьё = «хлопок», Плотность $\ge 195$ г/м². Условию удовлетворяют три ткани — бархат (405 г/м²), вельвет (410 г/м²) и джинса (420 г/м²). Выписываем их ID ткани.

Шаг 2. В таблице «Продукция» отбираем все модели, в наименовании которых есть слово «платье» (платье прямое, платье миди, платье-халат, платье-сарафан и т. д.). Категория потребителей в условии не ограничена, поэтому берём и детские, и женские модели.

Шаг 3. В таблице «Готовый товар» функцией ВПР добавляем к каждой строке цвет, сырьё и плотность ткани (по «ID ткани») и наименование модели (по «ID товара»), а затем оставляем строки, у которых ткань из шага 1 и наименование из шага 2. Таких строк 27.

Шаг 4. Стоимость одной строки равна произведению количества на складе и отпускной цены. Итоговую сумму удобно получить формулой СУММПРОИЗВ по двум столбцам отобранных строк (или добавить столбец с произведением и просуммировать его). Получается 1453717 рублей.

Ответ: 1453717

Решение:

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

Ветвь 0 занята целиком (слова 00 и 01), поэтому все новые слова начинаются с единицы. В ветви 10 занято слово 100 — свободна вершина 101; в ветви 11 занято слово 111 — свободна вершина 110.

Свободных слов длины не более 3 всего два: 101 и 110. Букв же три, поэтому все три слова длины 3 получить нельзя — одну из вершин придётся разбить надвое.

Например, набор 101, 1100, 1101 даёт сумму длин $3 + 4 + 4 = 11$. Столько же даёт и набор 110, 1010, 1011. Меньше получить нельзя.

Ответ: 11

Решение:

Приписывание цифр справа — это умножение на степень четвёрки. Разберём, сколько цифр приписывается в каждом случае. Если $N$ делится на 4, приписываются сразу две цифры, и $R$ примерно в 16 раз больше $N$. Если остаток равен 2 или 3, то удвоенный остаток равен $4 = 10_4$ или $6 = 12_4$ — это тоже две цифры, и снова $R \approx 16N$. И только при остатке 1 удвоенный остаток равен $2 = 2_4$ — одна цифра, поэтому $R = 4N + 2$.

Нам нужно $R \lt 261$, то есть $R$ — маленькое, значит выгоден только случай с остатком 1. Из $4N + 2 \lt 261$ получаем $N \le 64$, а вместе с условием $N \bmod 4 = 1$ наибольшее такое $N$ равно 61.

Проверка: $61 = 331_4$, остаток $61 \bmod 4 = 1$, удвоенный остаток $2 = 2_4$, поэтому $R = 3312_4 = 3 \cdot 64 + 3 \cdot 16 + 1 \cdot 4 + 2 = 246 \lt 261$. Все числа $N \gt 61$ дают больший результат: 62, 63 и 64 удлиняют запись на две цифры (получается $R$ порядка тысячи), а следующий «дешёвый» кандидат $N = 65 = 1001_4$ даёт $10012_4 = 262$, что уже не меньше 261.

def to4(n):
    s = ''
    while n:
        s = str(n % 4) + s
        n //= 4
    return s or '0'

def R(N):
    q = to4(N)
    q += q[-2:] if N % 4 == 0 else to4(2 * (N % 4))
    return int(q, 4)

print(max(N for N in range(1, 1000) if R(N) < 261))   # 61

Ответ: 61

Решение:

Направо 180 Вперёд 3 переводит Цаплю из $(0;0)$ в $(0;-3)$. Направо 90 направляет клюв вдоль отрицательного направления оси $Ox$, Вперёд 48 даёт $(-48;-3)$. Ещё одно Направо 90 — клюв вверх, Вперёд 3 даёт $(-48;0)$.

Команда Дуга 4, 4, 0 из точки $(x;y)$ описывает полуокружность радиуса 4 с центром $(x+4;\,y)$ по часовой стрелке: конечная точка — $(x+8;\,y)$, а дуга выпирает вверх. Шесть таких дуг ведут из $(-48;0)$ в $(0;0)$ и замыкают линию.

Фигура — прямоугольник $[-48;0]\times[-3;0]$, на верхней стороне которого лежат шесть полукругов радиуса 4 с центрами $(-44;0)$, $(-36;0)$, $(-28;0)$, $(-20;0)$, $(-12;0)$, $(-4;0)$. Верхняя сторона прямоугольника проходит внутри фигуры, а точки стыка дуг $(-40;0)$, $(-32;0)$, $(-24;0)$, $(-16;0)$, $(-8;0)$ лежат на границе и не считаются.

C = [-44, -36, -28, -20, -12, -4]             # центры полуокружностей, r = 4
n = 0
for x in range(-54, 7):
    for y in range(-4, 6):
        pr = -48 <= x <= 0 and -3 <= y <= 0                          # прямоугольник
        pk = any(y >= 0 and (x - c) ** 2 + y * y <= 16 for c in C)   # полукруги
        gr = any(y >= 0 and (x - c) ** 2 + y * y == 16 for c in C) \
             or (pr and (x == -48 or x == 0 or y == -3))             # точки на линии
        if (pr or pk) and not gr:
            n += 1
print(n)

Программа печатает 250. Для контроля: площадь равна $48\cdot 3+6\cdot\dfrac{\pi\cdot 4^{2}}{2}=144+48\pi\approx 294{,}8$. Ответ: 250

Решение:

Пусть цвет одного пикселя кодируется $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

Решение:

Буквы в алфавитном порядке: А, Л, М, О, С. Наименьшее подходящее слово строим жадно, слева направо ставя минимальную допустимую букву.

Условия: букв А не более одной, букв М ровно две, буквы Л нет совсем.

• 1-я буква — А (одна А разрешена);
• 2-я и 3-я — М: вторую А ставить нельзя, буква Л запрещена, значит следующая по алфавиту доступная буква — М, и обе нужные М выгодно поставить левее;
• 4-я и 5-я — О: А исчерпана, Л запрещена, М уже ровно две, поэтому минимальная доступная буква — О.

Получилось слово АММОО. Заменим буквы цифрами пятеричной системы (А=0, Л=1, М=2, О=3, С=4): АММОО → $02233_5$, его значение $$2 \cdot 5^3 + 2 \cdot 5^2 + 3 \cdot 5 + 3 = 250 + 50 + 15 + 3 = 318.$$ Номер слова равен $318 + 1 = 319$.

from itertools import product

for n, w in enumerate(product('АЛМОС', repeat=5), 1):
    s = ''.join(w)
    if s.count('А') <= 1 and s.count('М') == 2 and 'Л' not in s:
        print(n, s)
        break

Ответ: 319

Решение:

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

Решение:

Открываем прилагаемый файл в текстовом редакторе и пользуемся поиском (Ctrl+F). Текст ищем по всему роману — выделять фрагмент не нужно.

Параметры поиска:

• «Только слово целиком» — включено: формы «начало», «начала», «началом», «начале», «началась», а также слова, внутри которых встречается это сочетание букв («сначала», «вначале», «назначал», «означало», «обозначал»), считать нельзя;
• «Учитывать регистр» — включено: по условию нужно слово со строчной буквы.

«Найти все» даёт 18 совпадений (варианта «Начал» с прописной буквы в тексте нет, так что здесь учёт регистра на результат не влияет, но включать его всё равно правильно).

Проверка программой (роман сохранён как текстовый файл):

import re

text = open('text.txt', encoding='utf-8').read()
print(len(re.findall(r'\bначал\b', text)))

Программа печатает 18.Ответ: 18

Решение:

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

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

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

Для 30 пользователей потребуется $30 \cdot 15 = 450$ байт.

import math

N = 26 + 10                   # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(7 * i / 8)      # байт на пароль
print(30 * (b + 9))           # ответ в байтах

Ответ: 450

Решение:

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

• >0 → 22> : цифра 0 заменяется на две двойки, вклад в сумму 4;
• >1 → 2> : цифра 1 заменяется на двойку, вклад 2;
• >2 → 1> : цифра 2 заменяется на единицу, вклад 1.

Каждая цифра исходной строки обрабатывается ровно один раз, поэтому порядок цифр не важен, а сумма цифр результата равна $$15 \cdot 4 + n \cdot 2 + 15 \cdot 1 = 75 + 2n.$$

Осталось перебрать $n$: при $n=1$ сумма $77 = 7 \cdot 11$ — составное число; при $n=2$ сумма $79$ — простое. Наименьшее подходящее значение $n = 2$.

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

def prostoe(x):
    d = 2
    while d * d <= x:
        if x % d == 0:
            return False
        d += 1
    return x > 1

def rabota(s):
    while ">0" in s or ">1" in s or ">2" in s:
        if ">0" in s:
            s = zamenit(s, ">0", "22>")
        if ">1" in s:
            s = zamenit(s, ">1", "2>")
        if ">2" in s:
            s = zamenit(s, ">2", "1>")
    return s

n = 1
while True:
    s = rabota(">" + "0" * 15 + "1" * n + "2" * 15)
    summa = sum(int(c) for c in s if c != ">")
    if prostoe(summa):
        print(n, summa)   # 2 79
        break
    n += 1

Ответ: 2

Решение:

Сначала находим саму сеть: её адрес — поразрядная конъюнкция адреса узла и маски. В маске 255.255.255.240 ровно $24+4=28$ единиц, и 192 & 240 = 192, поэтому адрес сети — 132.72.244.192. Свободных битов $32-28=4$, значит в сети $2^4=16$ адресов: от 132.72.244.192 до 132.72.244.207.

Теперь смотрим на неизменную часть двоичной записи — первые 28 битов одинаковы у всех адресов сети. Третий байт 244 = 11110100 целиком лежит в этом префиксе и уже содержит четыре единицы подряд. Значит цепочка из трёх единиц найдётся в записи каждого адреса, и условию удовлетворяют все 16 адресов сети.

ip = [132, 72, 244, 192]
mask = [255, 255, 255, 240]

def to_int(a):
    return (a[0] << 24) | (a[1] << 16) | (a[2] << 8) | a[3]

n, m = to_int(ip), to_int(mask)
base = n & m                       # адрес сети
host = 32 - bin(m).count('1')      # число свободных битов
cnt = 0
for i in range(2 ** host):
    s = bin(base + i)[2:].zfill(32)
    if '111' in s:
        cnt += 1
print(cnt)

Ответ: 16

Решение:

Распишем операнды по степеням основания 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

Решение:

Дизъюнкция ложна только тогда, когда ложны все три её слагаемых. Значит, выражение тождественно истинно ровно тогда, когда не найдётся пары целых неотрицательных $x$ и $y$, для которой одновременно $y \le x$, $x \le 60$ и $x + 2y \ge A$.

Иначе говоря, на всём «опасном» множестве $0 \le y \le x \le 60$ обязано выполняться неравенство $x + 2y \lt A$. Осталось найти наибольшее значение суммы $x + 2y$ на этом множестве. Чем больше $x$, тем больше и допустимое $y$, поэтому максимум достигается в самой «дальней» точке $x = y = 60$ и равен $60 + 2 \cdot 60 = 180$.

Значит, нужно $A \gt 180$, и наименьшее целое такое число — $A = 181$. Проверим: при $A = 181$ в любой точке проверочного множества $x + 2y \le 180 \lt 181$, то есть истинно первое слагаемое; вне этого множества истинно второе ($y \gt x$) или третье ($x \gt 60$) слагаемое. При $A = 180$ выражение ломается на паре $x = y = 60$: там все три скобки ложны.

best = max(x + 2 * y
           for x in range(0, 61)
           for y in range(0, x + 1))
print(best + 1)   # 181

Ответ: 181

Решение:

Правило $F(n) = n \cdot F(n-1)$ при $F(1) = 1$ задаёт факториал, но вычислять его не нужно: достаточно трижды раскрыть числитель.

$$F(2023) = 2023 \cdot F(2022) = 2023 \cdot 2022 \cdot F(2021) = 2023 \cdot 2022 \cdot 2021 \cdot F(2020).$$

Поэтому $\dfrac{F(2023)}{F(2020)} = 2023 \cdot 2022 \cdot 2021 = 4090506 \cdot 2021 = 8266912626$.

print(2023 * 2022 * 2021)   # 8266912626

Ответ: 8266912626

Решение:

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

Последняя цифра числа — остаток от деления его модуля на 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

Решение:

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

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

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

import openpyxl

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

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

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

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

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

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

Ответ: 2167 718

Решение:

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

Ходы: $s\to s+1$ и $s\to 2s$. Одним ходом игра заканчивается, если $s+1\ge2022$ ($s\ge2021$) или $2s\ge2022$ ($s\ge1011$). Значит, из позиции $s\ge1011$ ходящий выигрывает одним ходом.

Нужно $S\le1010$ (Петя не выигрывает сразу) и $S+1\ge1011$, $2S\ge1011$, то есть $S\ge1010$ и $S\ge506$. Остаётся $S=1010$.

Проверка: из 1010 Петя получает 1011 или 2020, и в обоих случаях Ваня удваивает кучу: $2\cdot1011=2022\ge2022$ и $2\cdot2020=4040\ge2022$. Сам Петя выиграть сразу не мог: $1011\lt2022$ и $2020\lt2022$.

def win1(s):
    return s + 1 >= 2022 or 2 * s >= 2022

for S in range(1, 2021):
    if not win1(S) and win1(S + 1) and win1(2 * S):
        print(S)

Ответ: 1010

Решение:

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

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

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

• $(4,\ 69)$ — Петя удваивает вторую кучу: $4 + 138 = 142$;
• $(2,\ 71)$ — Петя удваивает вторую кучу: $2 + 142 = 144$;
• $(2,\ 138)$ — Петя добавляет два камня: $2 + 140 = 142$.

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

• $(6,\ 68)$ — Петя удваивает вторую кучу: $6 + 136 = 142$;
• $(8,\ 68)$ — Петя удваивает вторую кучу: $8 + 136 = 144$;
• $(4,\ 70)$ — Петя удваивает вторую кучу: $4 + 140 = 144$;
• $(4,\ 136)$ — Петя добавляет два камня: $4 + 138 = 142$.

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

N = 142

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

def over(p):                 # игра закончена
    return p[0] + p[1] >= N

def win1(p):                 # В1: выигрыш своим первым ходом
    return any(over(q) for q in moves(p))

def lose1(p):                # П1: любой ход отдаёт победу сопернику
    return all(not over(q) and win1(q) for q in moves(p))

def win2(p):                 # В2: выигрыш вторым ходом, но не первым
    return not win1(p) and any(not over(r) and lose1(r) for r in moves(p))

print(*[s for s in range(1, 139) if win2((2, s))][:2])   # два наименьших

Ответ: 67 68

Решение:

Напомним условие игры из задания 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$ — процессы из третьего столбца; для независимого процесса просто $F(B) = t(B)$. Вся совокупность закончится в момент, равный наибольшему из значений $F$.

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

ID процесса	Время выполнения, мс	Зависит от	Момент завершения, мс
1	2	0	2
2	5	1	7
3	3	0	3
4	2	3	5
5	4	2; 4	11
6	1	0	1
7	1	6	2
8	4	7	6
9	2	6	3
10	3	0	3
11	5	0	5
12	8	8; 9; 10; 11	14

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

# данные из прилагаемого файла: 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

Решение:

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

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

from functools import lru_cache

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

print(f(60, 20) * f(20, 1))

Получаем $f(60, 20) = 22$ и $f(20, 1) = 80$, то есть всего $22 \cdot 80 = 1760$ программ. Ответ: 1760

Решение:

Нужен самый длинный участок, целиком состоящий из символов X и Y. Символы Z разрезают файл на такие участки, поэтому достаточно найти длину самого длинного «куска» между соседними Z.

Проход по файлу: счётчик cur увеличиваем на каждом символе, отличном от Z, и обнуляем на каждом Z; ответ — максимум счётчика.

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

mx = cur = 0
for c in s:
    if c != 'Z':
        cur += 1
        if cur > mx:
            mx = cur
    else:
        cur = 0

print(mx)

То же самое в одну строку через разбиение строки: print(max(len(p) for p in s.split('Z'))). Программа выводит 34. Ответ: 34

Решение:

Перебирать все числа до $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

Решение:

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

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

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

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

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

2767 51

Ответ: 2767 51

Решение:

Занумеруем пункты числами $0,1,\dots,N-1$ (пункт $c$ — это $(c+1)$-й километр), вес пункта $w_c$ — количество комплектов питания. Трасса кольцевая и движение двустороннее, поэтому расстояние от цеха в пункте $c$ до пункта $p$ равно $\min(d,\,N-d)$, где $d=(p-c)\bmod N$. Нужно найти $\min_c C(c)$, где $C(c)=\sum_p w_p\min(d,N-d)$.

Прямой перебор всех $c$ с пересчётом суммы — это $O(N^2)$, для файла B это нереально. Заметим, что при фиксированном $c$ пункты разбиваются на две дуги: до $A=\lfloor N/2\rfloor$ шагов вперёд (там расстояние равно смещению $d$) и до $B=\lfloor (N-1)/2\rfloor$ шагов назад (расстояние равно смещению $e$). Так как $A+B+1=N$, каждый пункт учитывается ровно один раз, и $$C(c)=\sum_{d=0}^{A} d\,w_{c+d}+\sum_{e=1}^{B} e\,w_{c-e}$$ (индексы по модулю $N$).

Обе суммы берутся по окну постоянной длины, которое сдвигается вместе с $c$. Продублируем массив весов ($ww=w+w$) и построим две префиксные суммы: $P_1[t]=\sum_{i\lt t} ww_i$ и $P_2[t]=\sum_{i\lt t} i\,ww_i$. Тогда, подставляя $t=c+d$ и $t=c+N-e$, получаем $$\sum_{d=0}^{A} d\,w_{c+d}=\bigl(P_2[c+A+1]-P_2[c]\bigr)-c\bigl(P_1[c+A+1]-P_1[c]\bigr),$$ $$\sum_{e=1}^{B} e\,w_{c-e}=(c+N)\bigl(P_1[c+N]-P_1[c+N-B]\bigr)-\bigl(P_2[c+N]-P_2[c+N-B]\bigr).$$ Каждое значение $C(c)$ считается за $O(1)$, весь алгоритм — за $O(N)$.

def solve(name):
    f = open(name)
    n = int(f.readline())
    w = [int(f.readline()) for _ in range(n)]   # w[c] — пункт (c+1)-го километра
    a = n // 2            # смещения «вперёд»: 0, 1, ..., a
    b = (n - 1) // 2      # смещения «назад»:  1, 2, ..., b   (a + b + 1 = n)
    ww = w + w            # удваиваем массив, чтобы не считать индексы по модулю
    p1 = [0] * (2 * n + 1)          # p1[t] = сумма ww[0..t-1]
    p2 = [0] * (2 * n + 1)          # p2[t] = сумма i*ww[i] для i = 0..t-1
    for t in range(2 * n):
        p1[t + 1] = p1[t] + ww[t]
        p2[t + 1] = p2[t] + t * ww[t]
    best = None
    for c in range(n):
        hi = c + a + 1
        fwd = (p2[hi] - p2[c]) - c * (p1[hi] - p1[c])
        lo = c + n - b
        bwd = (c + n) * (p1[c + n] - p1[lo]) - (p2[c + n] - p2[lo])
        cost = fwd + bwd
        if best is None or cost < best:
            best = cost
    return best

print(solve('A.txt'), solve('B.txt'))

Проверка на примере из условия ($N=6$, веса $8,20,5,13,7,19$): минимум достигается в пункте 6 и равен $1\cdot 7+0\cdot 19+1\cdot 8+2\cdot 20+3\cdot 5+2\cdot 13=96$.Для файла A минимум равен $141\,530$ (цех в пункте $105$), для файла B — $18\,192\,010\,182\,272$.Ответ: 141530 18192010182272