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

Решение:

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

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

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

Те же три набора нетрудно получить и перебором:

from itertools import product


def impl(a, b):
    return (not a) or b


def F(w, x, y, z):
    return impl(w, impl(impl(z, x), y))


for w, x, y, z in product((0, 1), repeat=4):
    if not F(w, x, y, z):
        print(w, x, y, z)

Ответ: wyzx

Решение:

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

Шаг 1. В таблице «Аптека» отбираем строки с сетью «Здоровое поколение» и выписываем ID этих аптек.

Шаг 2. В таблице «Препараты» находим пустырник. Важно: под этим названием в базе два разных артикула — упаковка по 20 таблеток за 60 рублей и упаковка по 30 таблеток за 95 рублей. Нужны оба.

Шаг 3. В таблице «Движение лекарственных средств» оставляем строки: тип операции «Продажа», ID аптеки — из шага 1, артикул — один из двух найденных. Вся таблица и так охватывает 1–14 июня, так что дополнительное ограничение по дате ничего не отсекает. Суммируем «Количество упаковок»: 96 упаковок первого артикула и 105 упаковок второго.

Шаг 4. Умножаем количество на цену соответствующего артикула и складываем: $96 \cdot 60 + 105 \cdot 95 = 5760 + 9975 = 15735$ рублей. В таблице это удобно сделать формулой СУММПРОИЗВ по столбцам «Количество упаковок» и подтянутой функцией ВПР цене.

Ответ: 15735

Решение:

Известно: А — 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

Решение:

Автомат приписывает друг к другу произведение цифр P и сумму цифр S, причём первым записывается большее из этих чисел. Значит, строку 33621 надо разрезать на две части так, чтобы первая часть была не меньше второй.

Сумма трёх цифр не превосходит $9 + 9 + 9 = 27$, поэтому часть, отвечающая за сумму, состоит не более чем из двух цифр. Разбираем варианты разреза:

• «3» и «3621», «33» и «621» — не годятся: первое число меньше второго, порядок невозрастания нарушен;
• «3362» и «1» — тогда одно из чисел равно 1. Сумма цифр трёхзначного числа равна 1 только у числа 100, но произведение его цифр равно 0, а не 3362. Произведение цифр равно 1 только у числа 111, но сумма его цифр равна 3, а не 3362. Не подходит;
• «336» и «21» — подходит: $336 \ge 21$, а суммой цифр число 336 быть не может, поэтому $P = 336$ и $S = 21$.

Ищем цифры $a, b, c$, для которых $a \cdot b \cdot c = 336$ и $a + b + c = 21$. Разложим на множители: $336 = 2^4 \cdot 3 \cdot 7$. Множитель 7 не может «разойтись» между цифрами, поэтому одна из цифр равна 7, а две другие дают в произведении $336 : 7 = 48$. Единственное разложение числа 48 на два множителя-цифры — это $6 \cdot 8$. Проверяем сумму: $6 + 7 + 8 = 21$ — верно.

Значит, цифры искомого числа — 6, 7 и 8; наибольшее число из этих цифр — 876. Проверка программой:

for n in range(999, 99, -1):
    a, b, c = int(str(n)[0]), int(str(n)[1]), int(str(n)[2])
    p, s = a * b * c, a + b + c
    x, y = max(p, s), min(p, s)
    if str(x) + str(y) == '33621':
        print(n)
        break

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

Решение:

После команды Направо 60 голова Черепахи повёрнута на $30^\circ$ к оси абсцисс, а дальше каждый шаг — отрезок длины 9 и поворот ровно на $60^\circ$ в одну и ту же сторону. Шесть таких шагов дают полный оборот $6\cdot 60^\circ=360^\circ$ и замыкают правильный шестиугольник со стороной 9; седьмой шаг просто повторяет первую сторону и новой линии не добавляет.

Вершины шестиугольника: $(0;0)$, $\left(\tfrac{9\sqrt3}{2};\,4{,}5\right)$, $(9\sqrt3;\,0)$, $(9\sqrt3;\,-9)$, $\left(\tfrac{9\sqrt3}{2};\,-13{,}5\right)$, $(0;\,-9)$. Его площадь равна $\tfrac{3\sqrt3}{2}\cdot 9^2\approx 210{,}4$, значит искомое число близко к 210. На границе лежат ровно 10 целых точек — весь левый вертикальный отрезок от $(0;-9)$ до $(0;0)$; по условию их учитывать не следует.

Точный подсчёт удобно доверить программе: воспроизводим ход Черепахи, берём первые шесть полученных вершин и для каждого узла решётки проверяем, что все векторные произведения сторон на векторы к этому узлу одного знака — это и означает «строго внутри выпуклого многоугольника».

from math import cos, sin, radians

x = y = 0.0
h = 90.0                 # голова смотрит вверх
P = [(0.0, 0.0)]

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

def F(n):                # Вперёд n
    global x, y
    x += n * cos(radians(h))
    y += n * sin(radians(h))
    P.append((x, y))

R(60)
for _ in range(7):
    F(9)
    R(60)

poly = P[:6]             # шесть вершин шестиугольника

def inside(px, py):
    d = []
    for i in range(6):
        ax, ay = poly[i]
        bx, by = poly[(i + 1) % 6]
        d.append((bx - ax) * (py - ay) - (by - ay) * (px - ax))
    return all(t > 1e-9 for t in d) or all(t < -1e-9 for t in d)

print(sum(inside(a, b) for a in range(-20, 21) for b in range(-20, 21)))

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

Решение:

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

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

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

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

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

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

Ответ: 16

Решение:

Буквы в алфавитном порядке: А, М, О, Т. Слова четырёхбуквенные, поэтому с каждой фиксированной первой буквы начинается ровно $4^3 = 64$ слова.

Раньше слов на букву О идут все слова на А и на М — это $2 \cdot 64 = 128$ слов. Значит, первое слово на О (это ОААА) имеет номер $128 + 1 = 129$.

Тот же результат через четверичную систему (А=0, М=1, О=2, Т=3): ОААА → $2000_4 = 2 \cdot 4^3 = 128$, номер $128 + 1 = 129$.

from itertools import product

for n, w in enumerate(product('АМОТ', repeat=4), 1):
    if w[0] == 'О':
        print(n, ''.join(w))
        break

Ответ: 129

Решение:

В файле 6400 строк, в каждой шесть натуральных чисел. Строка подходит, если выполнены оба условия:

• ровно одно значение встречается в строке ровно два раза, а остальные четыре числа попарно различны — то есть среди шести чисел ровно одно «двойное» и ровно четыре «одиночных»;
• среднее арифметическое четырёх неповторяющихся чисел не превосходит суммы повторяющихся чисел; повторяющееся число $x$ стоит дважды, поэтому их сумма равна $2x$.

Проще всего перебрать строки программой, подсчитывая, сколько раз встречается каждое число (класс Counter):

import csv
from collections import Counter

count = 0
for row in csv.reader(open('data.csv'), delimiter=';'):
    nums = [int(x) for x in row]
    c = Counter(nums)
    twice = [v for v, k in c.items() if k == 2]   # значения, встречающиеся 2 раза
    once = [v for v, k in c.items() if k == 1]    # значения, встречающиеся 1 раз
    if len(twice) == 1 and len(once) == 4:
        if sum(once) / 4 <= 2 * twice[0]:
            count += 1
print(count)   # 2241

Условие len(twice) == 1 and len(once) == 4 как раз и означает «ровно одно число повторяется ровно два раза, остальные различны»: оно отбрасывает строки, где какое-то число встречается три и более раз или где повторяющихся пар несколько. Программа находит 2241 подходящую строку. Ответ: 2241

Решение:

В маске 255.255.224.0 ровно $8+8+3=19$ единиц, и 192 & 224 = 192, поэтому адрес сети — 208.229.192.0. Свободных битов $32-19=13$, то есть в сети $2^{13}=8192$ адресов.

Два последних бита адреса относятся к номеру узла и потому меняются свободно. Условие «запись оканчивается на две единицы» жёстко фиксирует оба этих бита, а остальные $13-2=11$ битов остаются произвольными. Значит подходящих адресов $2^{11}=2048$ — ровно четверть сети.

ip = [208, 229, 192, 0]
mask = [255, 255, 224, 0]

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 s.endswith('11'):
        cnt += 1
print(cnt)

Ответ: 2048

Решение:

В идентификаторе используются 26 латинских букв и 2020 символов специального алфавита, значит мощность алфавита составляет $26 + 2020 = 2046$ символов. На один символ нужно минимальное целое $i$, при котором $2^i \ge 2046$. Так как $2^{10} = 1024 \lt 2046 \lt 2048 = 2^{11}$, получаем $i = 11$ бит.

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

Все 13 312 идентификаторов занимают $13312 \cdot 135 = 1797120$ байт, то есть $1797120 : 1024 = 1755$ Кбайт.

import math

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

Ответ: 1755

Решение:

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

Гадать, что произойдёт с 2023 единицами, не нужно — достаточно прогнать программу на коротких строках вида «22 + $k$ единиц + 22». Получается: $k=5$ — 121222, $k=6$ — 1212122, $k=7$ — 121222, $k=8$ — 1212122 и т. д. Начиная с $k=5$ результат зависит только от чётности $k$: при нечётном $k$ это 121222, при чётном — 1212122.

Число 2023 нечётное, поэтому получится строка 121222. Прямой прогон программы это подтверждает.

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

s = "22" + "1" * 2023 + "22"
while "211" in s or "112" in s:
    s = zamenit(s, "11", "1")
    if "21" in s:
        s = zamenit(s, "21", "12")
    else:
        s = zamenit(s, "12", "1")
print(s)   # 121222

Ответ: 121222

Решение:

Названия команд (цифры или буквы) на подсчёт не влияют: из $x$ можно попасть в $x+1$ или в $2x$. Пусть $R(x)$ — число программ, переводящих $x$ в конечное число. Тогда $$R(x)=R(x+1)+R(2x),$$ $R(\text{конечного числа})=1$, $R(x)=0$ при $x$, большем конечного числа, и $R(17)=0$, потому что 17 запрещено (числа только растут, так что запрет достаточно поставить один раз).

Траектория обязана содержать 10, поэтому задача распадается на две части: $1\to 10$ и $10\to 35$; ответ — произведение.

1) Из 1 в 10. Все числа траектории здесь не превосходят 10, так что запрет на 17 не работает:

Получаем 14 программ.

2) Из 10 в 35 без числа 17. Для $x\ge 18$ удвоение даёт больше 35, поэтому $R(x)=1$ при $x=18,\dots,35$. Далее $R(17)=0$ (запрещено) и считаем вниз:

Здесь, например, $R(16)=R(17)+R(32)=0+1=1$, $R(15)=R(16)+R(30)=1+1=2$, и так далее до $R(10)=R(11)+R(20)=6+1=7$.

Итого $14\cdot 7=98$.

from functools import lru_cache

def count(start, finish, forbidden):
    @lru_cache(None)
    def R(x):
        if x > finish or x in forbidden:
            return 0
        if x == finish:
            return 1
        return R(x + 1) + R(2 * x)
    return R(start)

print(count(1, 10, ()) * count(10, 35, (17,)))

Ответ: 98

Решение:

Приведём всё к степеням четвёрки: $16^{100}=4^{200}$, $64=4^{3}$. Тогда

$$N = 4^{700} + 4^{100} - 4^{200} - 4^{3}.$$

Сначала $4^{700}-4^{200} = 4^{200}\left(4^{500}-1\right)$ — это 500 троек в разрядах с 699-го по 200-й, ниже нули.

Прибавляем $4^{100}$ (единица в разряде 100) и вычитаем $4^{3}$: заём съедает эту единицу, разряды с 99-го по 4-й становятся тройками, а в разряде 3 получается $4-1=3$. Значит, тройки стоят в разрядах с 99-го по 3-й — это 97 троек, а разряды 2, 1, 0 нулевые.

Итого запись: 500 троек, 100 нулей, 97 троек, 3 нуля. Количество троек: $500 + 97 = 597$.

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

n = 4**700 + 4**100 - 16**100 - 64
print(to_base(n, 4).count('3'))     # 597

Ответ: 597

Решение:

Дизъюнкция $(\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

Решение:

Достаточно перебрать все целые числа отрезка $[1016;\ 7937]$ и проверить четыре условия: число делится на 3, но не делится ни на 7, ни на 17, ни на 19, ни на 27. (Условие «не делится на 27» отсеивает часть кратных 3.)

count = 0
last = 0
for n in range(1016, 7938):
    if n % 3 == 0 and n % 7 != 0 and n % 17 != 0 and n % 19 != 0 and n % 27 != 0:
        count += 1
        last = n          # числа идут по возрастанию, поэтому последнее и есть максимальное

print(count, last)   # 1568 7935

Максимум можно найти и вручную, спускаясь от правого конца отрезка: 7937 и 7936 не делятся на 3, а $7935 = 3 \cdot 2645$ делится на 3 и при этом не делится ни на 7 ($7935 = 7 \cdot 1133 + 4$), ни на 17 ($7935 = 17 \cdot 466 + 13$), ни на 19 ($7935 = 19 \cdot 417 + 12$), ни на 27 ($7935 = 27 \cdot 293 + 24$). Значит наибольшее число — 7935.В электронных таблицах то же самое делается формулой: в столбце A — числа от 1016 до 7937, в столбце B — проверка =ЕСЛИ(И(ОСТАТ(A1;3)=0; ОСТАТ(A1;7)<>0; ОСТАТ(A1;17)<>0; ОСТАТ(A1;19)<>0; ОСТАТ(A1;27)<>0);A1;0), затем СЧЁТЕСЛИ и МАКС по столбцу B.Ответ: 1568 7935

Решение:

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

Пусть $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). За один ход общее количество камней растёт либо на 1 (добавили камень), либо на x, либо на y (удвоили соответствующую кучу). Значит одним ходом можно прибавить не больше чем $\max(x,\,y,\,1)$, и игрок заканчивает игру своим ходом тогда и только тогда, когда $x+y+\max(x,\,y,\,1) \ge 77$.

Нам нужен неудачный ход Пети, после которого Ваня заканчивает игру. Иначе говоря, из позиции (7, S) за два хода (сначала Петя, потом Ваня) должно набираться не менее 77 камней. Больше всего даёт двукратное удвоение большей кучи: (7, S) → (7, 2S) → (7, 4S), всего $7+4S$ камней; любая другая пара ходов даёт меньше — например, (7, S+1) → (7, 2S+2) даёт лишь $7+2S+2$, а (7+1, S) → (7+1, 2S) даёт $7+1+2S$.

Условие $7+4S \ge 77$ равносильно $S \ge \frac{77-7}{4} = 17{,}5$, поэтому минимальное подходящее значение $S = 18$.

Проверим его. Сам Петя выиграть не может: удвоив большую кучу, он получит $7+2\cdot18 = 43$ камней, а это меньше 77. Но если он удвоит вторую кучу, возникнет позиция (7, 36); тогда Ваня удваивает её ещё раз, получает (7, 72), то есть 79 камней — не меньше 77, и Ваня выигрывает своим первым ходом.

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

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

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, 70):
    p = (A, s)
    # сам Петя выиграть не может, но неудачным ходом дарит победу Ване
    if not win1(p) and any(win1(q) for q in moves(p)):
        print(s)                  # 18
        break

Ответ: 18

Решение:

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

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

В1. Из кучи в $S$ камней игру заканчивают ходы $S+1 \ge 2022$ или $2S \ge 2022$. Второе условие слабее, поэтому В1 — это все $S \ge 1011$.

П1. Нужно, чтобы $S \lt 1011$, но оба хода попадали в В1: $S+1 \ge 1011$ и $2S \ge 1011$. Первое неравенство даёт $S \ge 1010$, поэтому единственная позиция П1 — это $S = 1010$ (проверка: $2 \cdot 1010 = 2020 \lt 2022$, игра ещё не окончена).

В2. Петя не выигрывает сразу, но обязан перевести кучу ровно в $1010$ камней. Это возможно двумя способами: $S+1 = 1010$, откуда $S = 1009$, и $2S = 1010$, откуда $S = 505$. Оба значения меньше $1011$, то есть за один ход Петя действительно не выигрывает.

После хода Пети в позицию $1010$ Ваня любым ходом получает $1011$ или $2020$ камней — в обоих случаях игра ещё не окончена, но Петя следующим ходом доводит кучу до $2022$ и более ($1011 \cdot 2 = 2022 \ge 2022$ и $2020 + 1 = 2021 \ge 2022$). Это и есть выигрыш вторым ходом.

Тот же ответ даёт короткая программа:

N = 2022

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

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

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

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

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

Ответ: 505 1009

Решение:

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

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

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

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

def over(p):
    return p[0] * p[1] >= N

def win1(p):                  # ходящий выигрывает своим первым ходом
    return any(over(q) for q in moves(p))

def lose1(p):                 # соперник выигрывает своим первым ходом
    return not win1(p) and all(win1(q) for q in moves(p))

def win2(p):                  # ходящий выигрывает своим вторым ходом
    return not win1(p) and any(lose1(q) for q in moves(p))

def lose2(p):                 # соперник выигрывает первым или вторым ходом
    return not win1(p) and all(win1(q) or win2(q) for q in moves(p))

for s in range(1, 142):
    p = (2, s)
    if over(p):
        break
    if lose2(p) and not lose1(p):
        print(s)
        break

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

• $(3;\ 22)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(3;\ 23)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(4;\ 23)$ — в $(8;\ 23)$; из $(6;\ 23)$ — в $(7;\ 23)$; из $(3;\ 24)$ — в $(6;\ 24)$; из $(3;\ 46)$ — в $(4;\ 46)$);
• $(4;\ 22)$ — Ваня выигрывает сразу: одним ходом он получает $(8;\ 22)$, а это уже не меньше 144;
• $(2;\ 23)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(3;\ 23)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(4;\ 23)$ — в $(8;\ 23)$; из $(6;\ 23)$ — в $(7;\ 23)$; из $(3;\ 24)$ — в $(6;\ 24)$; из $(3;\ 46)$ — в $(4;\ 46)$);
• $(2;\ 44)$ — Ваня выигрывает сразу: одним ходом он получает $(4;\ 44)$, а это уже не меньше 144.

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

Ответ: 22

Решение:

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

Для данных из файла получается такое расписание (12 процессов):

Теперь идём по шкале времени по одной миллисекунде и считаем, сколько процессов активно в каждый момент. Четыре процесса одновременно работают на двух участках: с 0 до 3 мс это процессы 1, 2, 9 и 10, а с 9 до 13 мс — процессы 4, 5, 11 и 12. Больше четырёх процессов не работает никогда.

Складываем длины этих участков: $3 + 4 = 7$ мс.

rows = [(1, 4, []), (2, 3, []), (3, 5, [1, 2]), (4, 7, [3]),
        (5, 6, [3]), (6, 2, [5]), (7, 5, [4, 6]), (8, 2, [7]),
        (9, 7, []), (10, 8, []), (11, 6, [9]), (12, 6, [10])]

dur = {i: t for i, t, d in rows}
dep = {i: d for i, t, d in rows}
start, finish = {}, {}

def calc(i):
    if i not in finish:
        start[i] = max([calc(j) for j in dep[i]], default=0)
        finish[i] = start[i] + dur[i]
    return finish[i]

for i in dur:
    calc(i)

total = 0
for t in range(max(finish.values())):        # такты по 1 мс
    if sum(start[i] <= t < finish[i] for i in dur) == 4:
        total += 1
print(total)   # 7

Ответ: 7

Решение.

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

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

Решение:

Запрещена только одна конфигурация — две буквы P подряд, то есть подстрока PP. Все остальные сочетания символов допустимы, поэтому серия обрывается ровно в тех местах, где встречается PP.

Идём по файлу и храним длину текущей допустимой серии cur. Если текущий и предыдущий символы оба равны P, старая серия закончилась, и новая начинается с текущего символа: cur = 1. Иначе cur += 1. Ответ — максимум cur.

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

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

print(mx)

Важно, что при обрыве новая серия начинается именно со второй буквы P: она сама по себе запрещённой пары не образует и может стать началом следующего участка. Программа выводит 188. Ответ: 188

Решение:

Наибольший делитель числа $n$, не равный самому $n$, — это $n/p$, где $p$ — наименьший простой делитель $n$. Поэтому достаточно найти $p$ перебором $d$ от 2 до $\sqrt{n}$, а затем проверить, простое ли частное $n/p$.

Простые числа сразу отбрасываем: по условию для них такого делителя не существует. Заметим, что оставшееся условие равносильно тому, что число $n$ раскладывается минимум на три простых множителя с учётом кратности: если множителей всего два, то $n = p\cdot q$ и частное $n/p = q$ простое.

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

def big_div(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d      # наибольший делитель, не равный n
        d += 1
    return 0                   # n простое: такого делителя нет

n = 350000
found = 0
while found < 6:
    n += 1
    d = big_div(n)
    if d != 0 and not is_prime(d):
        print(n, d)
        found += 1

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

350001 116667
350002 175001
350004 175002
350007 116669
350008 175004
350009 31819

Ответ: 350001 116667 350002 175001 350004 175002 350007 116669 350008 175004 350009 31819

Решение:

Сортируем длины сторон по убыванию и жадно строим цепочку, начиная с самой большой коробки: очередную коробку берём, если её сторона хотя бы на 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