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

Решение:

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

Оба слагаемых выражения $\neg ( x \lor ( w \rightarrow y ) ) \lor ( z \rightarrow x )$ равны нулю. Из $( z \rightarrow x ) = 0$ сразу получаем $z = 1$ и $x = 0$. Тогда $\neg ( x \lor ( w \rightarrow y ) ) = 0$ означает $x \lor ( w \rightarrow y ) = 1$, а поскольку $x = 0$, необходимо $w \rightarrow y = 1$, что запрещает лишь пару $w = 1,\ y = 0$. Итого:

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

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

from itertools import product


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


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


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

Ответ: xwyz

Решение:

Спрашивается масса полученного товара, поэтому нужны только операции с типом «Поступление», а количество упаковок надо перевести в массу через поле «Количество в упаковке» таблицы «Товар».

Шаг 1. В таблице «Магазин» отбираем магазины, у которых в адресе указан проспект Мира. Таких магазинов два — обратите внимание, что они находятся в разных домах, но район в условии не важен.

Шаг 2. В таблице «Товар» находим все виды зефира: зефир в шоколаде (250 г в упаковке), зефир ванильный (800 г), зефир воздушный (500 г) и зефир лимонный (1000 г). Выписываем их артикулы.

Шаг 3. В таблице «Движение товаров» оставляем строки с этими артикулами, магазинами из шага 1, типом операции «Поступление» и датой с 5 по 19 июня включительно. Суммируя «Количество упаковок» по каждому артикулу, получаем 1000, 1000, 1000 и 1200 упаковок соответственно.

Шаг 4. Переводим в граммы и складываем: $1000 \cdot 250 + 1000 \cdot 800 + 1000 \cdot 500 + 1200 \cdot 1000 = 2750000$ г. Переводим в килограммы: $2750000 : 1000 = 2750$ кг.

Ответ: 2750

Решение:

По условию нужно, наоборот, нарушить условие Фано: кодовое слово буквы Д должно быть началом одного из имеющихся кодов либо один из имеющихся кодов должен быть началом слова Д. При этом слово должно содержать больше одного знака и не совпадать с кодами 01, 10, 11 и 000.

Ищем самое короткое слово, поэтому начинаем с длины 2. Всего таких слов четыре: 00, 01, 10 и 11. Слова 01, 10 и 11 уже используются для букв А, Б и В, поэтому остаётся только слово 00.

Проверяем: слово 00 является началом кода 000 буквы Г, значит условие Фано нарушается — как и требуется. Слово состоит из двух знаков и ни с одним из имеющихся кодов не совпадает, поэтому оно и есть ответ.

Ответ: 00

Решение:

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

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

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

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

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

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

Ответ: 61

Решение:

Первый цикл: две итерации [Направо 90 Вперёд 1 Направо 90 Вперёд 11] уже возвращают Черепаху в исходную точку с исходным направлением, поэтому шесть итераций — это один и тот же прямоугольник, обведённый три раза. Его вершины: $(0;0)$, $(1;0)$, $(1;-11)$, $(0;-11)$, то есть $0\le x\le 1$, $-11\le y\le 0$. Целых точек в нём вместе с границей $2\cdot 12=24$.

При поднятом хвосте Черепаха переходит: Вперёд 3 — в $(0;3)$, Направо 90 — голова смотрит вправо, Вперёд 5 — в $(5;3)$. Второй цикл Повтори 10 [Вперёд 12 Направо 90] рисует квадрат со стороной 12, который замыкается уже после четырёх итераций; десять итераций обводят тот же квадрат два с половиной раза. Его вершины: $(5;3)$, $(17;3)$, $(17;-9)$, $(5;-9)$, то есть $5\le x\le 17$, $-9\le y\le 3$, и целых точек в нём $13\cdot 13=169$.

Фигуры не пересекаются и даже не касаются: у первой $x\in[0;1]$, у второй $x\in[5;17]$. Поэтому в объединении $24+169=193$ точки.

Ответ: 193

Решение:

Объём несжатой звукозаписи равен $V = k \cdot f \cdot b \cdot t$, где $k$ — число каналов, $f$ — частота дискретизации, $b$ — разрешение (число бит на отсчёт), $t$ — длительность.

Фрагмент тот же, поэтому $t$ не изменилась, и достаточно посмотреть, во сколько раз изменился каждый из остальных множителей:

• было 2 канала (стерео), стало 1 (моно) — уменьшение в 2 раза;
• разрешение (глубина кодирования) выросло в 2,5 раза;
• частота дискретизации выросла в 4 раза.

Значит объём файла умножился на $\frac{1}{2} \cdot 2{,}5 \cdot 4 = 5$, и новая запись занимает $39 \cdot 5 = 195$ Мбайт.

size = 39          # Мбайт, первая запись
k = 0.5 * 2.5 * 4  # во сколько раз изменился объём
print(size * k)    # 195.0

Ответ: 195

Решение:

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

Все степени $8^k$ при $k \ge 1$ чётны, поэтому чётность числа $n-1$ определяется только его последней цифрой. Номер нечётный $\Leftrightarrow$ число $n-1$ чётно $\Leftrightarrow$ последняя буква слова имеет чётный код, то есть слово оканчивается на А, И, М или О.

Считаем слова, у которых последняя буква — одна из А, И, М, О, первая — не Н, и букв О не больше одной.

• Последняя буква О. Тогда среди первых четырёх букв буквы О нет: первая — любая из 6 (не Н и не О), остальные три — любые из 7 (не О). Это $6 \cdot 7^3 = 2058$ слов.
• Последняя буква А, И или М (3 варианта). Среди первых четырёх букв не более одной О:
  ни одной О — $6 \cdot 7^3 = 2058$;
  ровно одна О: либо первая буква О — $1 \cdot 7^3 = 343$, либо О на одной из позиций 2–4 — $3 \cdot 6 \cdot 7^2 = 882$; всего $343 + 882 = 1225$.
  На один вариант последней буквы приходится $2058 + 1225 = 3283$ слова, на три — $3 \cdot 3283 = 9849$.

Итого $2058 + 9849 = 11907$.

from itertools import product

count = 0
for n, w in enumerate(product('АГИЛМНОФ', repeat=5), 1):
    s = ''.join(w)
    if n % 2 == 1 and s[0] != 'Н' and s.count('О') <= 1:
        count += 1
print(count)

Ответ: 11907

Решение:

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

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

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

В англоязычной версии редактора это =AVERAGE(B2:Y92)-MIN(B2:Y92). Получаем $10{,}4653\ldots - 0{,}3 = 10{,}1653\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.1653...

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

Решение:

Откроем файл с текстом повести и воспользуемся поиском (Ctrl+F). Вводим шапка и включаем режим «Только слово целиком»: иначе будут посчитаны формы «шапках», «шапками», «шапкам» и т. п., которые по условию не учитываются. Флажок «Учитывать регистр» не ставим — годятся и «шапка», и «Шапка».

Редактор находит 4 вхождения именно словоформы «шапка»: «…и шапка в золоте…», «…и шапка заломлена набекрень…», «…у кого шапка…», «Разлетелась медная шапка…».

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

import re

text = open('text.txt', encoding='cp1251').read()
matches = re.findall(r'(?<![А-Яа-яЁё])[Шш]апка(?![А-Яа-яЁё])', text)
print(len(matches))   # 4

Ответ: 4

Решение:

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

Один идентификатор из 108 символов занимает $108 \cdot 7 = 756$ бит. Число байт должно быть целым и минимальным: $756 = 8 \cdot 94 + 4$, поэтому под него отводится 95 байт.

Все 25 600 идентификаторов занимают $25600 \cdot 95 = 2432000$ байт, то есть $2432000 : 1024 = 2375$ Кбайт.

import math

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

Ответ: 2375

Решение:

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

Приоритет у замены (2222, 11): она выполняется, пока в строке есть четыре подряд идущие двойки, и только если их нет — работает замена (1111, 22). Вначале двоек нет, поэтому четвёрки единиц превращаются в пары двоек, дальше замены чередуются, и результат проще получить моделированием.

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

s = "1" * 91
while "2222" in s or "1111" in s:
    if "2222" in s:
        s = zamenit(s, "2222", "11")
    else:
        s = zamenit(s, "1111", "22")
print(s)   # 22111

Проверка на коротких строках: начиная с $k=8$ единиц результат периодичен с периодом 6, и при $k = 13,\ 19,\ 25,\ \ldots$ получается 22111. Здесь $91 = 13 + 6 \cdot 13$, что согласуется с ответом программы. Ответ: 22111

Решение:

В маске 255.255.254.0 ровно $8+8+7=23$ единицы, и 30 & 254 = 30, поэтому адрес сети — 200.192.30.0. Свободных битов $32-23=9$, а всего адресов $2^9=512$.

Общая для всех адресов часть 11001000110000000001111 содержит 14 нулей — число чётное, и на чётность итога она не влияет. Значит суммарное количество нулей нечётно ровно тогда, когда нечётно количество нулей среди 9 свободных битов. Разобьём наборы на пары, отличающиеся последним битом: в каждой паре подходит ровно один набор, поэтому ответ — половина сети, $512/2 = 256$.

ip = [200, 192, 30, 0]
mask = [255, 255, 254, 0]

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

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

Ответ: 256

Решение:

Основание системы счисления 9, а $9 = 3^{2}$, поэтому удобно выразить всё через степени девятки:

• $3^{2021} = 3\cdot 3^{2020} = 3\cdot 9^{1010}$;
• $5\cdot 3^{2000} = 5\cdot 9^{1000}$;
• $3^{501} + 5\cdot 3^{500} = 3\cdot 3^{500} + 5\cdot 3^{500} = 8\cdot 3^{500} = 8\cdot 9^{250}$;
• $1 = 1\cdot 9^{0}$.

Получаем $N = 3\cdot 9^{1010} + 5\cdot 9^{1000} + 8\cdot 9^{250} + 1$. Все коэффициенты (3, 5, 8, 1) — допустимые девятеричные цифры и стоят в разных разрядах, значит переносов нет, и это и есть готовая запись числа в девятеричной системе.

Старший разряд — 1010-й, поэтому всего в записи $1011$ цифр, из которых ненулевых ровно четыре. Значащих нулей: $1011 - 4 = 1007$.

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

n = 3**2021 + 5 * 3**2000 + 3**501 + 5 * 3**500 + 1
print(to_base(n, 9).count('0'))     # 1007

Ответ: 1007

Решение:

Дизъюнкция $(\text{ДЕЛ}(x, 2) \rightarrow \neg \text{ДЕЛ}(x, 3)) \lor (x + A \ge 100)$ ложна только тогда, когда ложны оба слагаемых.

Первая скобка — импликация; она ложна ровно тогда, когда $x$ делится на 2 и при этом не выполняется $\neg \text{ДЕЛ}(x, 3)$, то есть когда $x$ делится и на 2, и на 3 — иначе говоря, когда $x$ кратно 6.

Значит вторая скобка $x + A \ge 100$ обязана быть истинной для всех $x$, кратных 6 (при остальных $x$ формула истинна и без неё).

Условие $x + A \ge 100$ тем жёстче, чем меньше $x$. Наименьшее натуральное кратное шести — это $x = 6$, откуда $6 + A \ge 100$, то есть $A \ge 94$.

При $A = 94$ для любого кратного 6 числа $x \ge 6$ выполнено $x + 94 \ge 100$, значит наименьшее подходящее значение равно 94.

for A in range(1, 200):
    if all((x % 2 != 0 or x % 3 != 0) or x + A >= 100
           for x in range(1, 10000)):
        print(A)   # 94
        break

Ответ: 94

Решение:

Число 26 чётное, поэтому $F(26) = 26 + F(25)$. Осталось найти $F(25)$.

Для нечётных $n \gt 1$ правило $F(n) = 2 \cdot F(n-2)$ уменьшает аргумент на 2, оставляя его нечётным, поэтому цепочка идёт только по нечётным числам: $F(25) = 2F(23) = 4F(21) = \dots = 2^{12} \cdot F(1)$ (от 25 до 1 ровно 12 шагов). Значит $F(25) = 2^{12} = 4096$.

Итого $F(26) = 26 + 4096 = 4122$.

from functools import lru_cache

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

print(F(26))   # 4122

Ответ: 4122

Решение:

Задача решается одним проходом по файлу, но сначала нужно вычислить «планку» — максимальный элемент последовательности, оканчивающийся на 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}$.

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

В приложенном файле поле имеет размер $20\times20$. Вертикальные стены (нельзя идти вправо) стоят:

• между 4-м и 5-м столбцами — в строках 12–16;
• между 7-м и 8-м столбцами — в строках 4–19;
• между 12-м и 13-м столбцами — в строках 2–11;
• между 17-м и 18-м столбцами — в строках 11–18;
• между 19-м и 20-м столбцами — в строках 5–10.

Горизонтальные стены (нельзя идти вниз) стоят между 4-й и 5-й строками в столбцах 16–19, между 11-й и 12-й строками в столбцах 10–12, между 16-й и 17-й строками в столбцах 2–4, между 18-й и 19-й строками в столбцах 13–17 и между 19-й и 20-й строками в столбцах 5–7.

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

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

# стена снизу от клетки (i, j); строки и столбцы нумеруются с нуля
def wall_down(i, j):
    return ((i == 3 and 15 <= j <= 18) or (i == 10 and 9 <= j <= 11) or
            (i == 15 and 1 <= j <= 3) or (i == 17 and 12 <= j <= 16) or
            (i == 18 and 4 <= j <= 6))

# стена справа от клетки (i, j)
def wall_right(i, j):
    return ((j == 11 and 1 <= i <= 10) or (j == 6 and 3 <= i <= 18) or
            (j == 18 and 4 <= i <= 9) or (j == 16 and 10 <= i <= 17) or
            (j == 3 and 11 <= i <= 15))

MX = [[0] * N for i in range(N)]   # максимум, накопленный к клетке
MN = [[0] * N for i in range(N)]   # минимум
for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            MX[i][j] = MN[i][j] = a[0][0]
            continue
        v = []
        if i > 0 and not wall_down(i - 1, j):
            v.append((MX[i - 1][j], MN[i - 1][j]))
        if j > 0 and not wall_right(i, j - 1):
            v.append((MX[i][j - 1], MN[i][j - 1]))
        MX[i][j] = max(x for x, y in v) + a[i][j]
        MN[i][j] = min(y for x, y in v) + a[i][j]

best_max = 0
best_min = 10 ** 9
for i in range(N):
    for j in range(N):
        # клетка конечная, если справа и снизу от неё стена (или край поля)
        if (j == N - 1 or wall_right(i, j)) and (i == N - 1 or wall_down(i, j)):
            best_max = max(best_max, MX[i][j])
            best_min = min(best_min, MN[i][j])
print(best_max, best_min)

Конечных клеток оказывается пять; накопленные в них суммы такие:

Наибольшая из всех итоговых сумм — 2255 (правая нижняя клетка), наименьшая — 820 (клетка в 16-й строке и 4-м столбце).

Ответ: 2255 820

Решение:

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

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

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

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

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

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

def moves(p):
    x, y = p
    return [(x + 1, y), (2 * x, y), (x, y + 1), (x, 2 * y)]

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

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

Ответ: 18

Решение:

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

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

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

• $(15,\ 43)$ — Петя удваивает вторую кучу: $15 + 86 = 101$;
• $(14,\ 44)$ — Петя удваивает вторую кучу: $14 + 88 = 102$;
• $(28,\ 43)$ — Петя удваивает вторую кучу: $28 + 86 = 114$;
• $(14,\ 86)$ — Петя добавляет камень: $14 + 87 = 101$.

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

• $(9,\ 46)$ — Петя удваивает вторую кучу: $9 + 92 = 101$;
• $(8,\ 47)$ — Петя удваивает вторую кучу: $8 + 94 = 102$;
• $(16,\ 46)$ — Петя удваивает вторую кучу: $16 + 92 = 108$;
• $(8,\ 92)$ — Петя добавляет камень: $8 + 93 = 101$.

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

N = 101

def moves(p):
    a, b = p
    return [(a + 1, b), (a, b + 1), (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, 94) if win2((7, s))][:2])   # два наименьших

Ответ: 43 46

Решение:

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

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

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

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, 201):
    if lose2(s) and not lose1(s):
        print(s)
        break

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

• $99$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $100$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $101$ — в $202$; из $200$ — в $201$);
• $196$ — Ваня выигрывает сразу: одним ходом он получает $392$, а это уже не меньше 201.

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

Ответ: 98

Решение:

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

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

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

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

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

Ответ: 9

Решение:

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

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

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

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

print(f(1, 7) * f(7, 30))

Получаем $f(1, 7) = 2$ и $f(7, 30) = 29$, то есть всего $2 \cdot 29 = 58$ программ. Ответ: 58

Решение:

Из букв A, C, D, F, O гласные — это A и O, согласные — C, D, F. Нас интересует самая длинная цепочка вида «согласная+гласная», «согласная+гласная», … — то есть участок чётной длины, разбитый на пары, каждая из которых состоит из согласной и следующей за ней гласной. В ответе нужно указать количество таких пар.

Идём по файлу с позиции $i$. Если s[i] — согласная, а s[i+1] — гласная, то это очередная пара цепочки: увеличиваем счётчик и перескакиваем через оба символа (i += 2). Иначе цепочка обрывается: обнуляем счётчик и сдвигаемся на один символ.

s = open('59133_24.txt').read().strip()
glas = 'AO'

mx = cur = 0
i = 0
while i < len(s) - 1:
    if s[i] not in glas and s[i + 1] in glas:
        cur += 1
        i += 2
    else:
        cur = 0
        i += 1
    if cur > mx:
        mx = cur

print(mx)

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

Решение:

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

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

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

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

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

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

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

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

Решение:

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

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

Файл A: сумма больших чисел равна $650905$; она даёт остаток $13$ при делении на 33, то есть уже не делится на 33 — уменьшать ничего не нужно, ответ $650905$.Файл B: сумма больших чисел равна $666122358$ и делится на 33. Наименьшая ненулевая разность внутри пары, не кратная 33, равна $1622$, поэтому ответ $666122358 - 1622 = 666120736$.Ответ: 650905 666120736