Вариант 9 · Август 2026

Решение:

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

Здесь функция равна единице, значит истинны оба сомножителя выражения $\neg ( y \rightarrow ( z \equiv w ) ) \land ( x \rightarrow z )$. Из $\neg ( y \rightarrow ( z \equiv w ) ) = 1$ следует, что импликация ложна, то есть $y = 1$ и $z \ne w$. Условие $x \rightarrow z = 1$ запрещает пару $x = 1,\ z = 0$. При $z = 1,\ w = 0$ переменная $x$ любая, при $z = 0,\ w = 1$ обязательно $x = 0$. Наборы:

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

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

from itertools import product


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


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


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

Ответ: wzyx

Решение:

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

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

Шаг 2. В таблице «Препараты» находим Зиртек. Артикулов с таким названием несколько, и они отличаются числом таблеток в упаковке (7, 10 и 20). По условию нужна только упаковка на 7 таблеток — берём соответствующий ей артикул.

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

Шаг 4. Прирост: $1151 - 52 = 1099$ упаковок.

Ответ: 1099

Решение:

Условие Фано означает, что ни одно кодовое слово не является началом другого. Удобно представлять коды как пути в двоичном дереве: занятое кодовое слово «закрывает» всю ветку под собой, и новые слова можно брать только из свободных веток.

Разберём ветку, начинающуюся с нуля. Под словом 00 стоят оба возможных продолжения — 000 (А) и 001 (Б); под словом 010 — оба продолжения 0100 (Г) и 0101 (В); само слово 011 занято буквой Д. Значит вся ветка 0 закрыта полностью, свободных слов в ней нет.

В ветке, начинающейся с единицы, занято только слово 101 (Е). Слово 10 брать нельзя — оно является началом кода 101, а вот слово 100 свободно, и свободна вся ветка 11. Коротких слов длины 2 всего четыре: 00 — начало кодов А и Б, 01 — начало кодов В, Г и Д, 10 — начало кода Е, и только 11 не конфликтует ни с чем.

Поэтому одну из букв кодируем словом 11 длиной 2 знака, а короче двух знаков для второй буквы уже ничего не остаётся: все однобуквенные слова 0 и 1 являются началами занятых кодов, а единственное свободное слово длины 2 мы уже использовали. Ближайшее свободное слово для второй буквы — 100 длиной 3 знака (оно не начинается с 11 и не является началом ни одного из известных кодов). Суммарная длина равна $2+3=5$.

Тот же ответ даёт полный перебор пар кодовых слов:

from itertools import product

known = ['000', '001', '0101', '0100', '011', '101']

def fano(codes):
    return all(i == j or not codes[j].startswith(codes[i])
               for i in range(len(codes)) for j in range(len(codes)))

best = 99
for n1 in range(1, 6):
    for n2 in range(1, 6):
        for p in product('01', repeat=n1):
            for q in product('01', repeat=n2):
                zh, ze = ''.join(p), ''.join(q)
                if zh != ze and fano(known + [zh, ze]):
                    best = min(best, n1 + n2)
print(best)

Ответ: 5

Решение:

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

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

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

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

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

• $r=1$: $4N+2\ge 1025\Rightarrow N\ge 256$. Наименьшее число вида $4k+1$ — это $N=257$.
• $r=2$: $16N+4\ge 1025\Rightarrow N\ge 64$. Наименьшее число вида $4k+2$ — это $N=66$, $R=16\cdot 66+4=1060$.
• $r=3$: $16N+6\ge 1025\Rightarrow N\ge 64$. Наименьшее число вида $4k+3$ — это $N=67$, $R=1078$.
• $r=0$: $N=64$ даёт $R=16\cdot 64+0=1024$ — ровно на единицу меньше нужного, не подходит. Следующее кратное четырём $N=68$ даёт $R=16\cdot 68+4=1092$.

Наименьшее из чисел 257, 66, 67, 68 — это 66.

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

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

Ответ: 66

Решение:

Внутренний цикл Повтори 2 [Вперёд 10 Направо 90 Вперёд 10 Направо 90] рисует квадрат $10\times 10$ и возвращает Черепаху в исходную точку с исходным направлением.

Затем с поднятым хвостом Вперёд 10 Направо 90 Вперёд 5 Налево 90 сдвигает её на $(+5;+10)$, голова снова вдоль оси $Oy$.

Значит рисуются три квадрата: $[0;10]\times[0;10]$, $[5;15]\times[10;20]$ и $[10;20]\times[20;30]$.

Соседние квадраты не накладываются, а лишь примыкают друг к другу: первый и второй — по отрезку $y=10$, $5\le x\le 10$; второй и третий — по отрезку $y=20$, $10\le x\le 15$. Каждый такой общий отрезок длины 5 оказывается внутри объединения и убирает из суммарного периметра по 5 у каждого из двух квадратов, то есть 10 на пару.

Итого $3\cdot 40-10-10=100$.

Проверка прямым обходом границы: $(0;0)$, $(10;0)$, $(10;10)$, $(15;10)$, $(15;20)$, $(20;20)$, $(20;30)$, $(10;30)$, $(10;20)$, $(5;20)$, $(5;10)$, $(0;10)$ и назад в $(0;0)$; сумма длин $10+10+5+10+5+10+10+10+5+10+5+10=100$.

Ответ: 100

Решение:

Объём несжатой звукозаписи: $V = k \cdot f \cdot b \cdot t$, где $k = 4$ (квадро — четыре канала), $f = 96$ кГц $= 96000$ отсчётов в секунду, $b = 24$ бита на отсчёт, $t = 7$ с.

$V = 4 \cdot 96000 \cdot 24 \cdot 7 = 64512000$ бит.

Скорость модема уже дана в битах в секунду, переводить ничего не нужно: $\frac{64512000}{14400} = 4480$ с.

k, f, b, t = 4, 96000, 24, 7   # каналы, частота, разрешение, длительность
bits = k * f * b * t           # объём записи в битах
print(bits, bits // 14400)     # 64512000 4480

Ответ: 4480

Решение:

Кодовое слово состоит из трёх позиций. Буква К должна встретиться ровно один раз, поэтому сначала выберем для неё позицию — это можно сделать $3$ способами.

Каждая из двух оставшихся позиций заполняется любой из четырёх букв Ш, О, Л, А: букву К туда ставить нельзя, иначе она встретится больше одного раза. Это даёт $4^2 = 16$ вариантов.

По правилу произведения общее количество слов равно $3 \cdot 4^2 = 3 \cdot 16 = 48$.

from itertools import product

count = 0
for w in product('ШКОЛА', repeat=3):
    if w.count('К') == 1:
        count += 1
print(count)   # 48

Ответ: 48

Решение:

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

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

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

В англоязычной версии редактора это =AVERAGE(B2:Y92)-MIN(B2:Y92). Получаем $10{,}4502\ldots - 0{,}3 = 10{,}1502\ldots$ Целая часть равна 10. То же самое на 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(sum(values) / len(values) - min(values))   # 10.1502...

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

Решение:

Открываем файл и выделяем текст II главы — фрагмент от заголовка «II» до заголовка «III».

Нужны вхождения сочетания букв, которые не являются отдельным словом, поэтому делаем два поиска.

1. «тому», регистр не учитываем, «Только слово целиком» выключено — все вхождения сочетания букв: 5.
2. Тот же поиск с включённым «Только слово целиком» — отдельное слово «тому»/«Тому» в этой главе не встречается ни разу: 0.

Значит, внутри других слов сочетание встречается $5-0=5$ раз: «потому» (2 раза), «Поэтому», «этому», «голубоватому».

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

import re

text = open('glava2.txt', encoding='utf-8').read()
vsego = len(re.findall('тому', text)) + len(re.findall('Тому', text))
otdelno = len(re.findall(r'\bтому\b', text)) + len(re.findall(r'\bТому\b', text))
print(vsego - otdelno)

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

Решение:

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

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

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

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

Ответ: 4352

Решение:

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

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

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

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

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

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

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

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

Ответ: 2

Решение:

Маска 255.255.254.0 оставляет свободными 1 младший бит третьего байта и весь четвёртый байт.

Левые два байта: $253 = 11111101_2$ — 7 единиц, $112 = 01110000_2$ — 3 единицы, значит $L = 10$.

Правые два байта: третий байт равен $169 \wedge 254 = 168 = 10101000_2$ (3 единицы) плюс свободный бит $k_1\in\{0,1\}$; четвёртый байт даёт $k_8$ единиц. Итого $R = 3 + k_1 + k_8$.

Условие $R\ge L$ даёт $3 + k_1 + k_8 \ge 10$, то есть $k_1 + k_8 \ge 7$.

• $k_1 = 0$: нужно $k_8\ge 7$, это $C_8^7 + C_8^8 = 8 + 1 = 9$;
• $k_1 = 1$: нужно $k_8\ge 6$, это $C_8^6 + C_8^7 + C_8^8 = 28 + 8 + 1 = 37$.

Всего $9 + 37 = 46$.

ones = lambda x: bin(x).count('1')
count = 0
for b3 in (168, 169):
    for b4 in range(0, 256):
        if ones(b3) + ones(b4) >= ones(253) + ones(112):
            count += 1
print(count)      # 46

Ответ: 46

Решение:

Переведём все слагаемые в степени восьмёрки: $4^{2022}=2^{4044}=8^{1348}$, $6\cdot 4^{522}=6\cdot 2^{1044}=6\cdot 8^{348}$, $5\cdot 64^{510}=5\cdot 8^{1020}$, $3\cdot 2^{330}=3\cdot 8^{110}$, $100 = 144_8$. Тогда

$$N = 8^{1348} + 5\cdot 8^{1020} - 6\cdot 8^{348} - 3\cdot 8^{110} - 144_8.$$

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

1, затем 327 нулей, затем 4, затем 671 семёрка, затем 1, затем 237 семёрок, затем 4, затем 107 семёрок, затем 6, 3, 4.

Количество семёрок: $671 + 237 + 107 = 1015$.

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

def to_base(n, b):
    s = ''
    while n:
        s = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n % b] + s
        n //= b
    return s

n = 4**2022 - 6 * 4**522 + 5 * 64**510 - 3 * 2**330 - 100
print(to_base(n, 8).count('7'))     # 1015

Ответ: 1015

Решение:

Дизъюнкция ложна только тогда, когда ложны все три слагаемых. Значит выражение $(x \ge A) \lor (y \ge A) \lor (x \cdot y \le 270)$ не является тождественно истинным ровно тогда, когда найдутся целые положительные $x, y$, для которых

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

Нужно взять наибольшее $A$, при котором такой пары не существует.

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

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

Так как $16^{2} = 256 \le 270$, а $17^{2} = 289 \gt 270$, получаем $A - 1 \le 16$, то есть $A \le 17$. При $A = 17$ любое произведение не больше $16 \cdot 16 = 256 \le 270$ — выражение истинно; при $A = 18$ пара $x = y = 17$ даёт $289 \gt 270$ и обращает выражение в 0.

best = 0
for A in range(0, 100):
    if all(x >= A or y >= A or x * y <= 270
           for x in range(1, A + 1) for y in range(1, A + 1)):
        best = A
print(best)   # 17

Ответ: 17

Решение:

Значения считаем по порядку, начиная с $F(0) = F(1) = 1$. Для чётных $n \gt 1$ значение просто удваивается, для нечётных используем $F(n) = 3 + F(n-1) \cdot F(n-2) - F(n-1) - F(n-2)$ (удобно свернуть его как $F(n) = \bigl(F(n-1) - 1\bigr)\bigl(F(n-2) - 1\bigr) + 2$).

$F(2) = 2 \cdot 1 = 2$; $F(3) = 3 + 2 \cdot 1 - 2 - 1 = 2$; $F(4) = 2 \cdot 2 = 4$; $F(5) = 3 + 4 \cdot 2 - 4 - 2 = 5$; $F(6) = 10$; $F(7) = 3 + 10 \cdot 5 - 10 - 5 = 38$; $F(8) = 76$; $F(9) = 3 + 76 \cdot 38 - 76 - 38 = 2777$; $F(10) = 5554$; $F(11) = 3 + 5554 \cdot 2777 - 5554 - 2777 = 15415130$; $F(12) = 2 \cdot 15415130 = 30830260$.

from functools import lru_cache

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

print(F(12))   # 30830260

Ответ: 30830260

Решение:

Задача решается одним проходом по файлу, но сначала нужно вычислить «планку» — максимальный элемент последовательности, оканчивающийся на 13. Число оканчивается на 13 тогда и только тогда, когда остаток от его деления на 100 равен 13. Для данного файла эта планка равна 98413.

Дальше перебираем все тройки идущих подряд элементов (то есть окна вида $a_i, a_{i+1}, a_{i+2}$) и проверяем два условия: ровно два числа тройки трёхзначные, то есть лежат в диапазоне от 100 до 999, и сумма всех трёх чисел не превосходит найденной планки. Считаем такие тройки и параллельно запоминаем наибольшую из их сумм.

Подходящих троек оказывается 959, а наибольшая сумма среди них равна 97471.

a = [int(line) for line in open('17.txt')]

limit = max(x for x in a if x % 100 == 13)   # 98413

count = 0
best = 0
for i in range(len(a) - 2):
    t = a[i:i + 3]
    if sum(100 <= x <= 999 for x in t) == 2 and sum(t) <= limit:
        count += 1
        best = max(best, sum(t))

print(count, best)   # 959 97471

Ответ: 959 97471

Решение:

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

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

В этом варианте внутренних стен нет: Робот ограничен только границами квадрата. Поле в приложенном файле имеет размер $10\times10$, поэтому пересчёт идёт по обычным формулам, без дополнительных проверок.

Скопируем содержимое таблицы в текстовый файл 18.txt (числа разделены пробелами или знаками табуляции) и обработаем его программой.

f = open('18.txt')
a = [[int(x) for x in s.split()] for s in f]
N = len(a)

# внутренних стен нет
def wall_down(i, j):
    return False

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

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

Решение:

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

Ходы: $s\to s+1$, $s\to s+5$ и $s\to 4s$. Игра заканчивается одним ходом, если $s+1\ge205$ ($s\ge204$), или $s+5\ge205$ ($s\ge200$), или $4s\ge205$ ($s\ge51{,}25$, для целого $s$ — $s\ge52$). Значит, из позиции $s\ge52$ ходящий выигрывает одним ходом.

Нужно $S\le51$ (Петя не выигрывает сразу) и одновременно $S+1\ge52$, $S+5\ge52$, $4S\ge52$, то есть $S\ge51$, $S\ge47$ и $S\ge13$. Остаётся $S=51$.

Проверка: из 51 Петя получает 52, 56 или 204 — все не меньше 52, поэтому Ваня заканчивает игру своим ходом. Сам Петя выиграть сразу не мог: $52\lt205$, $56\lt205$, $204\lt205$.

def win1(s):
    return s + 1 >= 205 or s + 5 >= 205 or 4 * s >= 205

for S in range(1, 205):
    if not win1(S) and win1(S + 1) and win1(S + 5) and win1(4 * S):
        print(S)

Ответ: 51

Решение:

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

Так как $2S \ge S+1$, игрок выигрывает одним ходом тогда и только тогда, когда $2S \ge 301$, то есть при $S \ge 151$.

Найдём проигрышную позицию — такую кучу, из которой ходящий сам выиграть не может, но любой его ход отдаёт победу сопернику. Оба хода должны попадать в зону $\ge 151$; слабее ход «+1», он требует $S+1 \ge 151$, то есть $S \ge 150$. Вместе с $S \le 150$ (иначе игрок выиграл бы сам) получаем единственную такую кучу: 150 камней. Действительно, из 150 камней получаются 151 и 300 камней — до 301 не хватает; зато из 151 камней соперник удваивает и получает 302, а из 300 камней добавляет камень и получает 301.

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

• ходом «+1»: $S+1 = 150$, то есть $S = 149$;
• ходом «×2»: $2S = 150$, то есть $S = 75$.

Оба значения меньше 151, так что за один ход Петя действительно не выигрывает, а после его хода в позицию «150 камней» Ваня вынужден отдать победу: как бы он ни сходил, Петя следующим ходом добирает кучу до 301. Меньших подходящих значений нет: из кучи, где меньше 75 камней, позицию «150 камней» одним ходом не получить.

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

N = 301

def moves(s):
    return [s + 1, 2 * 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])   # [75, 149]

Ответ: 75 149

Решение:

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

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

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

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

def over(s):
    return s >= N

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

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

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

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

for s in range(1, 29):
    if lose2(s) and not lose1(s):
        print(s)
        break

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

• $13$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $14$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $15$ — в $30$; из $28$ — в $29$);
• $24$ — Ваня выигрывает сразу: одним ходом он получает $48$, а это уже не меньше 29.

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

Ответ: 12

Решение:

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

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

Наибольшее значение равно 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

Решение:

Все команды только увеличивают число на экране, поэтому траектория строго возрастает и ни одно число не может встретиться в ней дважды.

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

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$: $f(x, x) = 1$ (пустая программа), $f(x, y) = 0$ при $x \gt y$ (число уже «перескочило» цель, а уменьшать команды не умеют). В остальных случаях перебираем первую команду («прибавить 2», «умножить на 2» или «умножить на 3»):

$$f(x, y) = f(x + 2,\, y) + f(2x,\, y) + f(3x,\, y).$$

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 * 2, x * 3):
        s += f(z, y)
    return s

print(f(1, 6) * f(6, 24))

Получаем $f(1, 6) = 5$ и $f(6, 24) = 8$, то есть всего $5 \cdot 8 = 40$ программ. Ответ: 40

Решение:

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

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

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

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

print(mx)

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

Решение:

Ключевое наблюдение: наименьший делитель числа $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$ делится на 3.

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 % 3 == 0:
        print(n, f)
        found += 1

Проверим пару строк вручную. Для $n=850003$ наименьший простой делитель $p=7$, значит $F=850003/7-7=121429-7=121422$, и $121422=3\cdot 40474$ — делится на 3. Для $n=850015$ имеем $p=5$, $F=170003-5=169998$ — тоже кратно 3. Программа печатает шесть строк:

Ответ: 850003 121422 850005 283332 850006 425001 850012 425004 850015 169998 850018 425007

Решение:

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

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

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

В прилагаемом файле $S = 8200$, $N = 970$.

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)

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

568 50

Ответ: 568 50

Решение:

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

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

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

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

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

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

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

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

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

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