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

Решение:

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

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

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

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

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

from itertools import product, permutations

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

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

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

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

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

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

Ответ: yxwz

Решение:

Сумма набирается по таблице «Аренда», к строкам которой надо добавить сведения об автомобиле (по полю «ID автомобиля») и о клиенте (по полю «ID клиента»).

Шаг 1. В таблице «Клиенты» находим Сушкина Л. Н. и запоминаем его ID клиента.

Шаг 2. В таблице «Автомобили» ставим фильтр: Марка = «Nissan», Тип двигателя = «дизельный». Подходят семь машин — выписываем их ID автомобиля.

Шаг 3. В таблице «Аренда» оставляем строки, у которых ID клиента — из шага 1, ID автомобиля — из списка шага 2, а дата аренды попадает в первое полугодие, то есть с 1 января по 30 июня включительно.

Шаг 4. Таких операций оказывается четыре, на суммы 389, 205, 450 и 180 рублей. Складываем: $389 + 205 + 450 + 180 = 1224$ рубля. В таблице это делается формулой СУММЕСЛИМН или суммой отфильтрованного столбца «Сумма аренды, руб.».

Ответ: 1224

Решение:

Условие Фано нарушается, если новое кодовое слово является началом одного из используемых слов или одно из используемых слов является началом нового.

Заняты слова А — 00, Б — 01, В — 10, Г — 11, то есть все четыре двоичных слова длины 2. Слово из одного символа брать нельзя (символов должно быть больше одного), а совпадать с уже используемыми словами новое слово тоже не должно — значит, среди слов длины 2 подходящих нет.

Переходим к словам длины 3. Наименьшее числовое значение у слова 000. Проверяем его: слово 00 (буква А) является началом слова 000, поэтому условие Фано нарушается — это то, что требуется.

Значит, самое короткое подходящее слово с минимальным числовым значением — 000.

Ответ: 000

Решение:

Алгоритм просто удваивает каждый разряд двоичной записи $N$. Если запись $N$ содержит $m$ разрядов, то запись $R$ содержит ровно $2m$ разрядов, причём она составлена из пар 11 и 00.

Чем короче запись $R$, тем меньше само число, поэтому сначала подбираем минимально возможную длину, а затем — минимальное число такой длины.

При $m=3$ (то есть $N$ от 4 до 7) запись $R$ шестиразрядная, и самое большое такое значение — $N=7\to 111111_2=63$. Оно не больше 63, поэтому шести разрядов не хватает.

Значит, нужно $m\ge 4$. Наименьшее восьмиразрядное $R$ получается из наименьшего четырёхразрядного $N=8=1000_2$:

$1000_2\to 11000000_2=192$.

def alg(n):
    return int(''.join(c * 2 for c in bin(n)[2:]), 2)

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

Ответ: 192

Решение:

Команда «Налево 270» — это то же самое, что «Направо 90», поэтому все повороты фактически кратны $90^\circ$, и обе фигуры — прямоугольники со сторонами, параллельными осям.

Первый цикл: из $(0;0)$ вверх на 23, вправо на 30, вниз на 23, влево на 30 — прямоугольник $[0;30] \times [0;23]$.

Затем хвост поднят: «Назад 4» при голове, смотрящей вверх, опускает Черепаху в $(0;-4)$; «Налево 270» разворачивает её вправо, вперёд 1 — точка $(1;-4)$; «Налево 90» снова направляет голову вверх. Второй цикл рисует прямоугольник $[1;29] \times [-4;4]$.

Пересечение: по горизонтали общая часть $[1;29]$, по вертикали $[0;4]$, то есть прямоугольник $[1;29] \times [0;4]$. Точки на линиях считаем, поэтому целых точек $(29 - 1 + 1) \cdot (4 - 0 + 1) = 29 \cdot 5 = 145$.

r1 = {(x, y) for x in range(0, 31) for y in range(0, 24)}
r2 = {(x, y) for x in range(1, 30) for y in range(-4, 5)}
print(len(r1 & r2))   # 145

Ответ: 145

Решение:

Всего пикселей: $512\cdot 750=384000$.

Сжатый файл занимает 80 Кбайт, а файл оригинала больше него на 65%, то есть $80\cdot 1{,}65=132$ Кбайт.

Переведём размер оригинала в биты: $132\cdot 1024\cdot 8=1081344$ бит.

На один пиксель приходится $\dfrac{1081344}{384000}=2{,}816$ бит. Глубина цвета $i$ — целое число бит, а из $i\le 2{,}816$ получаем максимум $i=2$.

Количество цветов $N=2^{i}=2^{2}=4$.

Ответ: 4

Решение:

Букв семь, в алфавитном порядке: А, Е, И, К, Л, П, Р. Слово с номером $n$ — это число $n-1$ в семеричной системе счисления (А=0, Е=1, И=2, К=3, Л=4, П=5, Р=6).

Так как основание 7 нечётно, чётность $n-1$ зависит от суммы всех цифр, поэтому просто перебираем все $7^6 = 117\,649$ слов и отбираем те, у которых номер чётный, первая буква не К, а букв И не менее двух.

from itertools import product

count = 0
for n, w in enumerate(product('АЕИКЛПР', repeat=6), 1):
    s = ''.join(w)
    if n % 2 == 0 and s[0] != 'К' and s.count('И') >= 2:
        count += 1
print(count)

Программа выводит 10892. Ответ: 10892

Решение:

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

Задача сводится к одной формуле. В любую свободную ячейку (например, AA1) запишем:

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

Функция МАКС даёт наибольшую концентрацию за все три месяца, СРЗНАЧ — среднее арифметическое всех 2184 значений. В англоязычной версии редактора это =MAX(B2:Y92)-AVERAGE(B2:Y92). Получаем $22{,}4 - 10{,}450\ldots = 11{,}9497\ldots$ Целая часть этого числа равна 11. То же самое на Python (для CSV-версии файла):

import csv

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

print(max(values) - sum(values) / len(values))   # 11.9497...

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

Решение:

Выпишем по рисунку все дороги (стрелки):

А → Б, А → Г, Б → Д, В → А, В → Б, В → Г, В → Д, Г → Е, Г → Ж, Д → Е, Д → И, Д → Л, Е → В, Е → Л, Ж → Е, И → Л, К → Ж, Л → Ж, Л → К.

Нужны замкнутые маршруты Е → … → Е, в которых Е не встречается внутри, а каждый промежуточный город — не более одного раза. Из Е выходят только две дороги: в В и в Л, поэтому разберём два случая.

1) Первый шаг Е → Л. Из Л: Л → Ж → Е и Л → К → Ж → Е — 2 маршрута.

2) Первый шаг Е → В. Посчитаем сначала два вспомогательных числа.

• Из Г в Е: Г → Е и Г → Ж → Е — 2 способа.
• Из Д в Е: Д → Е (1 способ); Д → Л →… и Д → И → Л →…, а из Л в Е ведут 2 маршрута (через Ж и через К, Ж). Итого $1+2+2=5$ способов.

Из В выходят четыре дороги:

• В → Г →… → Е — 2;
• В → Д →… → Е — 5;
• В → Б → Д →… → Е — 5;
• В → А, а из А либо А → Г (2), либо А → Б → Д (5) — всего 7.

Значит, во втором случае $2+5+5+7=19$ маршрутов.

Всего $19+2=21$.

g = {
    'А': ['Б', 'Г'],
    'Б': ['Д'],
    'В': ['А', 'Б', 'Г', 'Д'],
    'Г': ['Е', 'Ж'],
    'Д': ['Е', 'И', 'Л'],
    'Е': ['В', 'Л'],
    'Ж': ['Е'],
    'И': ['Л'],
    'К': ['Ж'],
    'Л': ['Ж', 'К'],
}

total = 0

def go(v, used):
    global total
    for u in g[v]:
        if u == 'Е':          # вернулись в Е - маршрут готов
            total += 1
        elif u not in used:   # промежуточный город - не более одного раза
            go(u, used | {u})

go('Е', set())
print(total)                  # 21

Ответ: 21

Решение:

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

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

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

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

import math

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

Ответ: 13

Решение:

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

Приоритет у замены (11, 555): пока в строке есть хотя бы две подряд идущие единицы, работает только она. Из 2022 единиц получается $2022 : 2 = 1011$ групп «555», то есть $1011 \cdot 3 = 3033$ пятёрки, и ни одной единицы.

Дальше работает только замена (555, 5), каждое её выполнение уменьшает количество пятёрок на 2. Число 3033 нечётное, поэтому цепочка $3033 \to 3031 \to \ldots \to 3 \to 1$ заканчивается одной пятёркой (при одной пятёрке цепочка 555 уже не находится).

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

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

Ответ: 5

Решение:

Команда А увеличивает число на $2$, команда В — на $7$; порядок команд на итоговое число не влияет, важно лишь, сколько раз использована каждая. Всего надо прибавить $51 - 7 = 44$. Если команда А использована $n$ раз, а команда В — $k$ раз, то

$$2 n + 7 k = 44.$$

Отсюда подходят только $k = 0, 2, 4, 6$ (при остальных $k$ остаток $44 - 7k$ не делится на $2$ нацело или отрицателен).

Программа — это последовательность команд, поэтому при фиксированных $n$ и $k$ количество программ равно числу способов расставить $k$ команд В среди всех $n + k$ команд, то есть $C_{n+k}^{\,k}$.

Складываем: $1 + 136 + 495 + 7 = 639$.

Тот же результат даёт короткая программа:

from functools import lru_cache

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

print(f(7, 51))

Ответ: 639

Решение:

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

• $1x2x3x4x5_{25}$: $1+2+3+4+5 + 4x = 15 + 4x$;
• $2x024_{25}$: $2+x+0+2+4 = 8 + x$;
• $1x099_{25}$: $1+x+0+9+9 = 19 + x$.

Всего $42 + 6x \equiv 0 \pmod{24}$, то есть $6x \equiv 6 \pmod{24}$, откуда $x \equiv 1 \pmod{4}$. В алфавите 25-ричной системы подходят $x = 1, 5, 9, 13, 17, 21$; наибольшее — $x = 21$.

Подставляем $x=21$ и делим сумму на 24:

b = 25

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

for x in range(b - 1, -1, -1):           # ищем наибольшее x
    s = (num([1, x, 2, x, 3, x, 4, x, 5])
         + num([2, x, 0, 2, 4])
         + num([1, x, 0, 9, 9]))
    if s % 24 == 0:
        print(x, s // 24)                # 21 11727433732
        break

Ответ: 11727433732

Решение:

Конъюнкция $(x \lt A) \land (y \lt A) \land (x \cdot y \gt 1200)$ истинна, только когда истинны все три множителя. Тождественная ложность означает, что не существует целых положительных $x, y$, для которых одновременно

$x \lt A$, $y \lt A$ и $x \cdot y \gt 1200$.

Для целых $x \lt A$, $y \lt A$ верно $x \le A - 1$ и $y \le A - 1$, поэтому наибольшее достижимое произведение равно $(A - 1)^{2}$. Такой пары нет тогда и только тогда, когда

$$(A - 1)^{2} \le 1200.$$

Так как $34^{2} = 1156 \le 1200$, а $35^{2} = 1225 \gt 1200$, получаем $A - 1 \le 34$, то есть $A \le 35$. При $A = 35$ максимум произведения равен $34 \cdot 34 = 1156$, условие $x \cdot y \gt 1200$ невыполнимо и конъюнкция тождественно ложна; при $A = 36$ пара $x = y = 35$ даёт $1225 \gt 1200$ и делает выражение истинным.

best = 0
for A in range(0, 100):
    if not any(x < A and y < A and x * y > 1200
               for x in range(1, A + 1) for y in range(1, A + 1)):
        best = A
print(best)   # 35

Ответ: 35

Решение:

Числа $F(2024)$ и $F(2022)$ огромны, но выражение подобрано так, что они сократятся. Раскроем соотношение $F(n) = 3n + 2 F(n - 1)$ два раза.

$$F(2024) = 3 \cdot 2024 + 2 F(2023) = 6072 + 2 F(2023),$$

$$F(2023) = 3 \cdot 2023 + 2 F(2022) = 6069 + 2 F(2022).$$

Подставим второе равенство в первое:

$$F(2024) = 6072 + 2 \cdot (6069 + 2 F(2022)) = 6072 + 12138 + 4 F(2022) = 18210 + 4 F(2022).$$

Значит $F(2024) - 4 \cdot F(2022) = 18210$. Базовое значение $F(1) = 3$ на ответ не влияет.

def F(n):
    r = 3
    for i in range(2, n + 1):
        r = 3 * i + 2 * r
    return r

print(F(2024) - 4 * F(2022))   # 18210

Ответ: 18210

Решение:

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

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

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

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

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

print(count, best)   # 1020 17197

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

Решение:

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

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

В приложенном файле поле имеет размер $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])

Программа выводит 463 730: минимальная сумма равна 463, максимальная — 730. По условию в ответе сначала записывают минимальную сумму, затем максимальную. Ответ: 463 730

Решение:

Из кучи в $S$ камней ход «добавить камень» даёт $S+1$, ход «удвоить» даёт $2S$. Так как $2S \ge S+1$ при любом $S \ge 1$, выиграть одним ходом можно тогда и только тогда, когда $2S \ge 201$, то есть при $S \ge 101$.

Поэтому условие «Петя не может выиграть за один ход» означает $S \le 100$.

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

• после хода «+1» получается $S+1$, нужно $S+1 \ge 101$, то есть $S \ge 100$;
• после хода «×2» получается $2S$, нужно $2S \ge 101$, то есть $S \ge 51$.

Вместе с $S \le 100$ остаётся единственное значение $S = 100$.

Проверка: из кучи в 100 камней Петя получает 101 или 200 камней — до 201 не хватает ни в одном случае. Из 101 камней Ваня удваивает и получает 202 камней, из 200 камней Ваня добавляет один камень и получает 201 камней. И то и другое не меньше 201, значит Ваня выигрывает своим первым ходом при любом ходе Пети.

Тот же ответ даёт перебор:

N = 201

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

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

for s in range(1, N):
    # сам выиграть не может, но любой его ход отдаёт победу сопернику
    if not win1(s) and all(win1(t) for t in moves(s)):
        print(s)                  # 100

Ответ: 100

Решение:

Напомним условия игры: перед игроками две кучи камней, за ход можно добавить в одну из куч (по своему выбору) два камня либо увеличить количество камней в одной из куч вдвое; игра заканчивается, когда суммарное количество камней в кучах становится не менее $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

Решение:

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

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

В1. Из позиции $(2,\ S)$ игру заканчивают ходы $S+4 \ge 136$, $S+6 \ge 136$ и утроение второй кучи $3S+2 \ge 136$. Самое слабое — последнее условие, поэтому В1 — это все $S \ge 45$.

П1 для начальной позиции — единственное значение $S = 44$; В2 — значения $S = 42$, $S = 43$.

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

При $S = 41$ четыре хода Пети дают позиции $(2,\ 43)$ (В2), $(4,\ 41)$ (В2), $(6,\ 41)$ (В2), $(2,\ 123)$ (В1). Все они для Вани выигрышны не позже второго хода, но три из них — только вторым ходом, поэтому гарантированно выиграть первым ходом Ваня не может. Полный перебор подтверждает, что меньших значений $S$ с таким свойством нет.

Перебор всех $S$ удобно сделать программой:

N = 136

def moves(p):
    a, b = p
    return [(a + 2, b), (a, b + 2), (3 * a, b), (a, 3 * 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))

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

print(min(s for s in range(1, 133) if lose2((2, s))))

Ответ: 41

Решение:

Сначала для каждого процесса вычисляем время старта и время окончания. Независимый процесс стартует в момент 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

Решение.

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

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

Решение:

Условие «ни одна буква не стоит рядом с буквой, а цифра — с цифрой» означает, что на искомом участке буквы и цифры строго чередуются: любые два соседних символа должны быть разного типа. Конкретные значения (Q, R, W или 1, 2, 4) роли не играют — важен только тип символа.

Значит, достаточно одного прохода: если тип очередного символа отличается от типа предыдущего, серия продолжается, иначе начинается новая серия длины 1. Тип удобно определять методом isdigit().

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

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

print(mx)

Программа выводит 17 — это длина самого длинного чередующегося участка «буква-цифра-буква-…». Ответ: 17

Решение:

У целого числа $n$ наименьший делитель, отличный от единицы, — это его наименьший простой делитель $p$. Ему в пару идёт наибольший делитель, отличный от самого числа, равный $n/p$. Значит, оба «крайних» делителя находятся за один проход: достаточно перебрать $d$ от 2 до $\sqrt{n}$ и остановиться на первом, который делит $n$. Если такого $d$ нет, число простое, промежуточных делителей у него нет.

Значение $M = n/p - p$ оканчивается на 18 — это условие на две последние цифры, то есть m % 100 == 18. Перебираем числа, начиная с 860001, по возрастанию и останавливаемся, набрав пять подходящих.

def M(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d - d      # наибольший делитель минус наименьший
        d += 1
    return 0                       # n простое: делителей нет

n = 860000
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m % 100 == 18:      # M оканчивается на 18
        print(n, m)
        found += 1

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

860040 430018
860163 286718
860219 27718
860240 430118
860440 430218

Ответ: 860040 430018 860163 286718 860219 27718 860240 430118 860440 430218

Решение:

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

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

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

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

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

2172 50

Ответ: 2172 50

Решение:

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

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

Алгоритм линейный: один проход по файлу, в котором накапливаются $S$ и $d_{\min}$.

def solve(name, m):
    f = open(name)
    n = int(f.readline())
    s = 0                       # сумма больших чисел из каждой пары
    best = 10**9                # минимальная «допустимая» разность
    for _ in range(n):
        a, b = map(int, f.readline().split())
        s += max(a, b)
        d = abs(a - b)
        if d > 0 and d % m != 0:
            best = min(best, d)
    if s % m != 0:
        return s
    return s - best

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

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