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

Решение:

Степени вершин схемы: A — 2, B — 3, C — 2, D — 2, E — 3, F — 4, G — 2.

Число звёздочек в строках таблицы: 1 — 2, 2 — 4, 3 — 2, 4 — 3, 5 — 2, 6 — 2, 7 — 3.

Вершины степени 2 — это A, C, D и G, в таблице им отвечают пункты 1, 3, 5 и 6. Заметим главное: на схеме C и G соединены друг с другом, то есть это единственная пара вершин степени 2, между которыми есть дорога. Действительно, A соединена с B и E (обе степени 3), а D — с B (степень 3) и F (степень 4), так что ни у A, ни у D соседей степени 2 нет.

Проверим пункты таблицы: пункт 1 соединён с 4-м и 7-м (степени 3 и 3), пункт 6 — со 2-м и 7-м (степени 4 и 3), а вот пункты 3 и 5 соединены между собой (и оба — с пунктом 2 степени 4).

Значит, вершинам C и G отвечают пункты 3 и 5. Записываем их в порядке возрастания.

Ответ: 35

Решение:

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

Все слагаемые выражения $\neg ( w \rightarrow z ) \lor ( \neg x \rightarrow \neg y ) \lor x$ должны быть нулевыми. Сразу $x = 0$, тогда $\neg x = 1$, и равенство $( \neg x \rightarrow \neg y ) = 0$ даёт $\neg y = 0$, то есть $y = 1$. Наконец, $\neg ( w \rightarrow z ) = 0$ равносильно $w \rightarrow z = 1$ и запрещает пару $w = 1,\ z = 0$. Наборов три:

w	x	y	z	F
0	0	1	0	0
0	0	1	1	0
1	0	1	1	0

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

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

from itertools import product


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


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


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 автомобиля») и фамилию клиента (связь по полю «ID клиента»).

Шаг 1. В таблице «Клиенты» находим ID Сачкова Х. Э. и ID Гудкова Н. Г.

Шаг 2. В таблице «Автомобили» отбираем машины марки Hyundai и выписываем их ID автомобиля.

Шаг 3. В таблице «Аренда» оставляем строки с этими автомобилями и датой аренды с 1 января по 30 июня включительно, а затем отдельно суммируем «Сумму аренды, руб.» по каждому из двух клиентов (формула СУММЕСЛИМН).

Шаг 4. У Сачкова Х. Э. одна поездка на 276 рублей. У Гудкова Н. Г. семь поездок: 178, 204, 205, 336, 183, 345 и 418 рублей, в сумме $178 + 204 + 205 + 336 + 183 + 345 + 418 = 1869$ рублей. Модуль разности: $|276 - 1869| = 1593$.

Ответ: 1593

Решение:

Известно: А — 101000, Б — 111100, В — 000. Кодовые слова нужны ещё двум буквам — Г и Д, причём как можно короче.

Свободных слов длины 1 нет: 0 является началом слова 000 (буква В), а 1 — началом слов 101000 и 111100.

Среди слов длины 2: 00 является началом слова 000, 10 — началом слова 101000, 11 — началом слова 111100. Свободно только одно слово — 01.

Значит, длину 2 может получить лишь одна из двух букв, а второй достанется слово длины не менее 3. Такое слово есть: например, 001 (оно не является началом ни одного из слов 101000, 111100, 000, и они не являются его началом). Подходит и 100, и 110.

Минимальная сумма длин: $2 + 3 = 5$.

Ответ: 5

Решение:

Обозначим $M=N-(N\bmod 4)$ — результат первого шага. Это ближайшее снизу число, кратное 4, и при переборе всех $N$ величина $M$ пробегает в точности все кратные четырём числа.

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

Итак, к записи $M$ всегда приписываются два разряда $p$ и 0, то есть $R=4M+2p$, где $p$ — чётность количества единиц в $M$.

Нужно наименьшее $R\gt 100$. Так как $p\le 1$, из $4M+2p\gt 100$ следует $4M\ge 99$, то есть $M\ge 25$; а $M$ кратно 4, поэтому $M\ge 28$. Величина $R=4M+2p$ растёт вместе с $M$, значит достаточно взять наименьшее допустимое $M=28$.

$M=28=11100_2$, единиц три, $p=1$: запись $11100$ превращается в $111001$, затем в $1110010$, то есть $R=1110010_2=114$.

Для сравнения, предыдущее кратное четырём $M=24=11000_2$ даёт $p=0$ и $R=96$ — это не больше 100.

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

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

Ответ: 114

Решение:

Соберём повороты между соседними отрезками. Внутри цикла между двумя шагами накапливается $60^\circ+30^\circ=90^\circ$; столько же получается перед командой Вперёд 11 ($60^\circ+30^\circ$) и в последнем цикле ($90^\circ$). Значит, Черепаха рисует пять отрезков длиной 8, 8, 11, 8 и 8, каждый раз поворачивая ровно на прямой угол.

Последний отрезок идёт в том же направлении, что и первый, и лежит с ним на одной прямой, продолжая её назад. Поэтому ломаная замыкается в прямоугольник со сторонами 11 и 8 с вершинами $(-1{,}5;\ 1{,}5\sqrt3)$, $(4;\ -4\sqrt3)$, $(4-4\sqrt3;\ -4-4\sqrt3)$, $(-1{,}5-4\sqrt3;\ -4+1{,}5\sqrt3)$ — приближённо $(-1{,}5;\,2{,}60)$, $(4;\,-6{,}93)$, $(-2{,}93;\,-10{,}93)$, $(-8{,}43;\,-1{,}40)$.

Площадь прямоугольника $11\cdot 8=88$, а всего целых точек в нём вместе с границей 89. Две из них — $(0;0)$ (начало движения) и $(-6;0)$ — лежат ровно на сторонах, а точки на линии считать не следует, поэтому остаётся $89-2=87$.

from math import cos, sin, radians

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

def R(a):
    global h
    h -= a

def F(n):
    global x, y
    x += n * cos(radians(h))
    y += n * sin(radians(h))
    P.append((x, y))

R(120)
for _ in range(2):
    R(30); F(8); R(60)
R(30); F(11)
for _ in range(2):
    R(90); F(8)

poly = [P[4], P[1], P[2], P[3]]      # вершины прямоугольника 11 x 8

def inside(px, py):
    d = []
    for i in range(4):
        ax, ay = poly[i]
        bx, by = poly[(i + 1) % 4]
        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, 20) for b in range(-20, 20)))

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

Решение:

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

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

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

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

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

W, H = 2560, 5040
V = 14175 * 1024 * 8  # отведённая память в битах
i = V // (W * H)      # максимальное целое число бит на пиксель
print(i, 2 ** i)      # 9 512

Ответ: 512

Решение:

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

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

• 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

Решение:

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

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

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

from collections import Counter

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

print(count)

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

Решение:

Открываем прилагаемый файл, ищем по всему тексту романа (Ctrl+F).

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

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

«Найти все» показывает 37 совпадений. По отдельности: «дверь» — 33 раза, «Дверь» — 4 раза, $33+4=37$.

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

import re

text = open('text.txt', encoding='utf-8').read()
print(len(re.findall(r'\bдверь\b', text)) + len(re.findall(r'\bДверь\b', text)))

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

Решение:

В идентификаторе используются 10 десятичных цифр и 300 символов специального алфавита, значит мощность алфавита составляет $10 + 300 = 310$ символов. На один символ нужно минимальное целое $i$, при котором $2^i \ge 310$. Так как $2^{8} = 256 \lt 310 \lt 512 = 2^{9}$, получаем $i = 9$ бит.

Один идентификатор из 404 символа занимает $404 \cdot 9 = 3636$ бит. Число байт должно быть целым и минимальным: $3636 = 8 \cdot 454 + 4$, поэтому под него отводится 455 байт.

Все 3072 идентификаторов занимают $3072 \cdot 455 = 1397760$ байт, то есть $1397760 : 1024 = 1365$ Кбайт.

import math

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

Ответ: 1365

Решение:

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

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

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

def rabota(s):
    while "31" in s or "411" in s or "1111" in s:
        if "31" in s:
            s = zamenit(s, "31", "1")
        if "411" in s:
            s = zamenit(s, "411", "13")
        if "1111" in s:
            s = zamenit(s, "1111", "4")
    return s

for n in range(4, 10000):
    s = rabota("4" + "1" * n)
    if sum(int(c) for c in s) == 36:
        print(n, s)
        break
# 514 413333413344

Первое подходящее значение — $n = 514$: остаётся строка 413333413344, сумма цифр которой равна 36. Ответ: 514

Решение:

IP-адрес 244.55.229.28, адрес сети 244.0.0.0.

Первый байт: $244 = 11110100_2$, в адресе сети он остался равен 244, значит первый байт маски равен 255 (8 единиц) — это максимум.

Второй байт: $55 = 00110111_2$, в адресе сети он равен 0, поэтому маска должна обнулить все единицы числа 55. Перебираем префиксные маски второго байта:

• $11000000_2 = 192$: $55 \wedge 192 = 0$ — подходит (2 единицы);
• $11100000_2 = 224$: $55 \wedge 224 = 00100000_2 = 32 \ne 0$ — не подходит.

Значит, во втором байте маски не более двух единиц, а третий и четвёртый байты нулевые.

Наибольшее число единиц: $8 + 2 = 10$ (маска 255.192.0.0).

ip  = [244, 55, 229, 28]
net = [244, 0, 0, 0]
val = lambda p: (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3]
best = 0
for k in range(33):
    m = ((1 << k) - 1) << (32 - k) & 0xFFFFFFFF
    if val(ip) & m == val(net):
        best = max(best, k)
print(best)      # 10

Ответ: 10

Решение:

Приведём все слагаемые к степеням девятки: $9 = 3^2$, $243 = 3^5$.

• $243^{540} = 3^{2700} = 9^{1350}$;
• $21 \cdot 3^{511} = 63 \cdot 3^{510} = 7 \cdot 9 \cdot 9^{255} = 7 \cdot 9^{256}$;
• $3 \cdot 3^{70} = 3 \cdot 9^{35}$;
• $200 = 2 \cdot 9^2 + 4 \cdot 9 + 2 = 242_9$.

Значит, $N = 9^{1350} - 6 \cdot 9^{530} + 7 \cdot 9^{256} - 3 \cdot 9^{35} - 242_9$.

Шаг 1. $9^{1350} - 6 \cdot 9^{530} = 9^{530}\left(9^{820} - 6\right)$. Число $9^{820} - 6$ в девятичной записи — это 819 восьмёрок и тройка. Поэтому в разрядах с 1349-го по 531-й стоят 819 восьмёрок, в разряде 530 — цифра 3, а младшие разряды пока нулевые.

Шаг 2. $7 \cdot 9^{256} - 3 \cdot 9^{35} = 9^{35}\left(7 \cdot 9^{221} - 3\right)$. Число $7 \cdot 9^{221} - 3$ — это цифра 6, затем 220 восьмёрок, затем 6. Появляются ещё 220 восьмёрок (разряды 255…36), а в разряде 35 оказывается цифра 6.

Шаг 3. Вычитаем $242_9$. Три младших разряда нулевые, поэтому происходит заём: цифра 6 в разряде 35 уменьшается до 5, разряды с 34-го по 3-й (их ровно 32) превращаются в восьмёрки, а $9^3 - 242_9 = 647_9$ даёт младшие цифры 6, 4, 7. Это ещё 32 восьмёрки.

Итого восьмёрок: $819 + 220 + 32 = 1071$.

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

n = 243**540 - 6*9**530 + 21*3**511 - 3*3**70 - 200
s = ''
while n:
    s = str(n % 9) + s
    n //= 9
print(s.count('8'))

Ответ: 1071

Решение:

Выражение $\neg\big(P \rightarrow Q\big)$ ложно при всех $x$ тогда и только тогда, когда импликация $P \rightarrow Q$ истинна при всех $x$, где $P = (x \in B) \lor (x \in C)$, а $Q = (x \in A)$.

Это означает, что любая точка объединения

$B \cup C = [30;\ 41] \cup [50;\ 56]$

должна попадать в отрезок $A$. Отрезок — связное множество, поэтому вместе с концами 30 и 56 он содержит и всё между ними. Наименьший подходящий отрезок — $[30;\ 56]$.

Его длина $56 - 30 = 26$.

Ответ: 26

Решение:

Число 43 нечётное, поэтому работает правило $F(n) = 3n + F(n-2)$: аргумент уменьшается на 2 и остаётся нечётным. Значит вся цепочка идёт только по нечётным числам, вплоть до $F(1) = 1$, а правило для чётных $n$ не используется.

$$F(43) = 3 \cdot 43 + F(41) = 3 \cdot 43 + 3 \cdot 41 + F(39) = \dots = 3 \cdot (43 + 41 + \dots + 3) + F(1).$$

В сумме $3 + 5 + \dots + 43$ ровно 21 слагаемое, её значение равно $\frac{(3 + 43) \cdot 21}{2} = 23 \cdot 21 = 483$.

Итого $F(43) = 3 \cdot 483 + 1 = 1449 + 1 = 1450$.

from functools import lru_cache

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

print(F(43))   # 1450

Ответ: 1450

Решение:

Считаем файл в список целых чисел и просмотрим все пары соседних элементов $(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])

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

Решение:

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

Решение:

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

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

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

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

• ходом «+1»: $S = 66$;
• ходом «+4»: $S = 63$;
• ход «×3» не подходит: 67 не делится на 3.

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

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

N = 202

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

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

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

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

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

Ответ: 63 66

Решение:

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

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

В1. Из позиции $(3,\ S)$ игру заканчивают ход «добавить два камня» ($S+5 \ge 118$) и удвоение большей кучи ($2S+3 \ge 118$). Второе условие слабее, поэтому В1 — это все $S \ge 58$.

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

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

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

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

N = 118

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))

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, 114) if lose2((3, s))))

Ответ: 53

Решение:

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

Подставим $t = 2$ и заполним столбец $F$:

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

Наибольшее значение равно 12 мс, условие «не более 12 мс» выполнено. При $t = 3$ общее время стало бы равно 13 мс, что больше 12, поэтому 2 — максимально возможное целое значение.

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

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

def total(t):
    finish = {}
    for i in sorted(data):
        dur, deps = data[i]
        if dur is None:
            dur = t
        finish[i] = max([finish[d] for d in deps], default=0) + dur
    return max(finish.values())

print(max(t for t in range(1, 1000) if total(t) <= 12))

Ответ: 2

Решение:

Обозначим через $R(x)$ количество программ, переводящих число $x$ в заданное конечное число. Из $x$ исполнитель может перейти либо в $x+1$ (команда 1), либо в $2x$ (команда 2), поэтому $$R(x)=R(x+1)+R(2x),$$ причём $R(\text{конечного числа})=1$ (пустая программа), а если $x$ уже больше конечного числа, то $R(x)=0$ — числа только растут.

Траектория обязана содержать 10, а 10 лежит между 1 и 20, поэтому каждая подходящая программа однозначно распадается на две независимые части: сначала $1\to 10$, потом $10\to 20$. По правилу произведения общее количество равно произведению количеств.

1) Из 1 в 10. Считаем $R$ от 10 вниз к 1 (удвоение из $x\ge 6$ сразу перескакивает через 10, поэтому там остаётся только «прибавить 1»):

$x$	10	9	8	7	6	5	4	3	2	1
$R(x)$	1	1	1	1	1	2	3	4	7	14

Например, $R(5)=R(6)+R(10)=1+1=2$, $R(2)=R(3)+R(4)=4+3=7$, $R(1)=R(2)+R(2)=14$. Итого 14 программ.

2) Из 10 в 20. Для любого $x\ge 11$ удвоение даёт больше 20, значит $R(x)=R(x+1)=1$ для всех $x=11,\dots,20$. А из 10 можно и прибавлять единицы, и сразу удвоить: $R(10)=R(11)+R(20)=1+1=2$.

Итого $14\cdot 2=28$.

from functools import lru_cache

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

print(count(1, 10) * count(10, 20))

Ответ: 28

Решение:

Запрещена только одна конфигурация — две буквы 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$, не равный 1, — это его наименьший простой делитель $p$, а наибольший делитель, не равный $n$, — это $n/p$. Действительно, если $d$ — делитель, то $n/d$ — тоже делитель, и наименьшему делителю соответствует наибольший. Значит $$F=\frac{n}{p}-p,$$ а если $n$ простое, то «средних» делителей нет и $F=0$.

Поэтому искать $p$ достаточно перебором до $\sqrt{n}$: для $n\approx 850\,000$ это менее 1000 шагов, и вся программа отрабатывает мгновенно.

Перебираем числа, большие 850 000, по возрастанию и выводим первые 6 таких, у которых $F\ne 0$ и $F$ делится на 5.

def F(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d - d
        d += 1
    return 0

n = 850000
found = 0
while found < 6:
    n += 1
    f = F(n)
    if f != 0 and f % 5 == 0:
        print(n, f)
        found += 1

Проверим пару строк вручную. Для $n=850004$ наименьший простой делитель $p=2$, значит $F=850004/2-2=425002-2=425000$ — делится на 5. Для $n=850025$ имеем $p=5$, $F=170005-5=170000$ — тоже делится на 5. А, например, 850001 в ответ не попало: у него $F$ на 5 не делится. Программа печатает шесть строк:

Число	$F$
850004	425000
850014	425005
850024	425010
850025	170000
850029	283340
850034	425015

Ответ: 850004 425000 850014 425005 850024 425010 850025 170000 850029 283340 850034 425015

Решение:

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

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

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

В прилагаемом файле $S = 99\,991$, $N = 9993$.

f = open('26.txt')
s, n = map(int, f.readline().split())
a = sorted(int(x) for x in f)

total = 0
k = 0
for x in a:
    if total + x <= s:
        total += x
        k += 1
    else:
        break

base = sum(a[:k - 1])                            # k-1 самых маленьких
big = max(x for x in a[k - 1:] if base + x <= s)  # самый большой, который ещё влезает
print(k, big)

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

3084 61

Ответ: 3084 61

Решение:

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

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

Файл A: сумма больших чисел равна $127341$ и делится на 3. Наименьшая ненулевая разность внутри пары, не кратная 3, равна $214$, поэтому ответ $127341 - 214 = 127127$.Файл B: сумма больших чисел равна $399762096$ и делится на 3. Наименьшая ненулевая разность внутри пары, не кратная 3, равна $16$, поэтому ответ $399762096 - 16 = 399762080$.Ответ: 127127 399762080