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

Решение:
Обратим внимание, что вершина C является уникальной, так как её степень равна 6, следовательно, ей соответствует пункт под номером 1. В силу симметрии графа пары вершин A и B, D и H, а также E и F являются взаимозаменяемыми. Допустим, что пункты 2 и 6 — это вершины A и B, поскольку только они обладают степенью 2. В таком случае вершинам D и H будут соответствовать номера 7 и 4 (либо наоборот, 4 и 7 соответственно).

Ответ: 47

Источник: ФИПИ

Решение:

Функция $F = x \land (y \rightarrow z) \land (\neg y \rightarrow (\neg z \equiv w))$ — это конъюнкция, поэтому разберём, когда она равна 1. Прежде всего обязательно $x = 1$. Дальше два случая:

• если $y = 1$, то из $y \rightarrow z$ следует $z = 1$, а третья скобка выполняется автоматически (её посылка $\neg y = 0$);
• если $y = 0$, то вторая скобка истинна, а третья требует $w = \neg z$, то есть $z$ и $w$ должны быть различны.

Значит, единица получается ровно в четырёх наборах $(x, y, z, w)$: $(1,1,1,0)$, $(1,1,1,1)$, $(1,0,0,1)$, $(1,0,1,0)$.

Шаг 1. Находим столбец x. В первых двух строках фрагмента $F = 1$, значит, в них $x = 1$. В первой строке нули стоят в столбцах 3 и 4 — там $x$ стоять не может. Во второй строке нули стоят в столбцах 2 и 3 — там $x$ тоже стоять не может. Остаётся единственный вариант: $x$ — первый столбец.

Шаг 2. Находим столбец y. В первой строке фрагмента среди $y, z, w$ уже видно два нуля (столбцы 3 и 4), во второй — тоже два (столбцы 2 и 3). Из четырёх «единичных» наборов два нуля среди $y, z, w$ есть только у $(1,0,0,1)$ и $(1,0,1,0)$. В первой строке фрагмента второй столбец равен 1, а во второй строке он равен 0, так что это разные наборы — то есть первая и вторая строки в каком-то порядке и есть эти два набора.

В обоих наборах $y = 0$, а $z$ и $w$ принимают в них разные значения. Столбец 3 равен нулю в обеих строках, поэтому $y$ — третий столбец.

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

Итого порядок столбцов: $x$, $z$, $y$, $w$.

Тот же ответ даёт короткая программа, перебирающая все 24 расстановки переменных по столбцам:

from itertools import permutations, product

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

frag = [((None, None, 0, 0), 1),
        ((None, 0, 0, None), 1),
        ((1, None, 1, 1), 0)]

def fits(pat, row):
    return all(p is None or p == v for p, v in zip(pat, row))

for p in permutations('xyzw'):
    table = []
    for vals in product([0, 1], repeat=4):
        d = dict(zip(p, vals))
        table.append((vals, int(bool(F(d['x'], d['y'], d['z'], d['w'])))))
    for tri in permutations(table, 3):
        if all(fits(pat, row) and val == f
               for (pat, val), (row, f) in zip(frag, tri)):
            print(''.join(p))
            break

Ответ: xzyw

Решение:

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

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

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

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

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

Ответ: 1099

Решение:

Известно: А — 00, Б — 01, В — 100, Г — 1011. Найдём свободные вершины дерева.

• Ветвь 0 занята целиком: 00 — А, 01 — Б.
• В ветви 10: слово 100 — это В; в ветви 101 слово 1011 — это Г, свободна вершина 1010.
• Ветвь 11 свободна целиком.

Свободные места: 11 (2 знака) и 1010 (4 знака). Кодовые слова нужны двум буквам — Д и Е. Варианты с наименьшей суммарной длиной:

• занять оба свободных места: 11 и 1010 — длины 2 и 4, сумма 6, произведение $2 \cdot 4 = 8$;
• разбить вершину 11 на 110 и 111 — длины 3 и 3, сумма 6, произведение $3 \cdot 3 = 9$.

Любое дальнейшее удлинение слов только увеличивает сумму, поэтому наименьшее количество двоичных знаков равно 6. Из двух способов, дающих 6 знаков, минимальное произведение длин — 8.

Ответ: 8

Решение:

Пусть $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\lt 369$. Рассмотрим все четыре случая.

• $r=1$: $4N+2\lt 369\Rightarrow N\le 91$. Наибольшее число вида $4k+1$, не превосходящее 91, — это $N=89$, для него $R=358$.
• $r=2$: $16N+4\lt 369\Rightarrow N\le 22$. Подходит $N=22$, $R=356$.
• $r=3$: $16N+6\lt 369\Rightarrow N\le 22$. Наибольшее число вида $4k+3$ — это $N=19$, $R=310$.
• $r=0$: $16N\lt 369\Rightarrow N\le 23$. Подходит $N=20$, $R=16\cdot 20+4=324$.

Наибольшее из чисел 89, 22, 19, 20 — это 89.

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(max(n for n in range(1, 1000) if alg(n) < 369))

Ответ: 89

Решение:

Повтори 2 [Вперёд 15 Налево 90 Вперёд 20 Налево 90]: из $(0;0)$ вверх на 15, влево на 20, вниз на 15, вправо на 20. Первый прямоугольник: $-20\le x\le 0$, $0\le y\le 15$; голова снова смотрит вдоль оси $Oy$.

С поднятым хвостом: Направо 90 — голова вдоль $Ox$; Назад 7 даёт $(-7;0)$; Налево 90 — голова снова вдоль $Oy$; Вперёд 9 даёт $(-7;9)$.

Повтори 2 [Вперёд 17 Направо 90 Вперёд 15 Направо 90] из точки $(-7;9)$ рисует второй прямоугольник: $-7\le x\le 8$, $9\le y\le 26$.

Считаем целые точки объединения вместе с границами:

• первый прямоугольник: $21\cdot 16=336$ точек;
• второй прямоугольник: $16\cdot 18=288$ точек;
• пересечение $-7\le x\le 0$, $9\le y\le 15$: $8\cdot 7=56$ точек.

$336+288-56=568$.

Ответ: 568

Решение:

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

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

Файл должен поместиться в отведённую память: $1600000 \cdot i \le 17203200$, откуда $i \le \frac{17203200}{1600000} \approx 10{,}75$.

Число бит на пиксель — целое, поэтому наибольшее подходящее значение $i = 10$.

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

W, H = 1000, 1600
V = 2100 * 1024 * 8  # отведённая память в битах
i = V // (W * H)     # максимальное целое число бит на пиксель
print(i, 2 ** i)     # 10 1024

Ответ: 1024

Решение:

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

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

from itertools import product

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

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

Решение:

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

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

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

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

import csv

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

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

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

Решение:

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

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

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

«Найти все» показывает 7 совпадений (варианта «Словами» с прописной буквы в тексте нет).

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

import re

text = open('text.txt', encoding='utf-8').read()
print(len(re.findall(r'\bсловами\b', text)))

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

Решение:

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

Один идентификатор из 285 символов занимает $285 \cdot 11 = 3135$ бит. Число байт должно быть целым и минимальным: $3135 = 8 \cdot 391 + 7$, поэтому под него отводится 392 байта.

Все 1152 идентификаторов занимают $1152 \cdot 392 = 451584$ байта, то есть $451584 : 1024 = 441$ Кбайт.

import math

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

Ответ: 441

Решение:

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

Замена (12, 221) переставляет единицу на одну позицию вправо (за стоящую справа двойку) и добавляет ещё одну двойку. Справа от единицы вначале 70 двоек, поэтому эта замена выполнится ровно 70 раз: единица окажется в конце строки, а двоек станет $70 + 70 = 140$.

После этого цепочка 12 не находится, но единица есть, поэтому выполняется замена (1, 2): двоек становится 141, и программа останавливается.

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

s = "1" + "2" * 70
while "12" in s or "1" in s:
    if "12" in s:
        s = zamenit(s, "12", "221")
    elif "1" in s:
        s = zamenit(s, "1", "2")
print(s.count("2"))   # 141

Ответ: 141

Решение:

Сначала находим саму сеть: её адрес — поразрядная конъюнкция адреса узла и маски. В маске 255.255.255.240 ровно $24+4=28$ единиц, и 192 & 240 = 192, поэтому адрес сети — 132.72.244.192. Свободных битов $32-28=4$, значит в сети $2^4=16$ адресов: от 132.72.244.192 до 132.72.244.207.

Теперь смотрим на неизменную часть двоичной записи — первые 28 битов одинаковы у всех адресов сети. Третий байт 244 = 11110100 целиком лежит в этом префиксе и уже содержит четыре единицы подряд. Значит цепочка из трёх единиц найдётся в записи каждого адреса, и условию удовлетворяют все 16 адресов сети.

ip = [132, 72, 244, 192]
mask = [255, 255, 255, 240]

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 '111' in s:
        cnt += 1
print(cnt)

Ответ: 16

Решение:

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

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

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

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

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

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

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

Ответ: 597

Решение:

Выражение $\neg(x \in A) \rightarrow ((x \in B) \equiv (x \in C))$ ложно только тогда, когда $x \notin A$, а принадлежности отрезкам $B$ и $C$ различны. Поэтому отрезок $A$ должен накрывать все точки, где $B$ и $C$ «расходятся», — их симметрическую разность.

Для $B = [4; 18]$ и $C = [12; 40]$:

• в $B$, но не в $C$: $4 \le x \lt 12$;
• в $C$, но не в $B$: $18 \lt x \le 40$.

Крайние точки этого множества — 4 слева и 40 справа, значит отрезок $A$ обязан содержать весь промежуток $[4; 40]$.

Наименьший подходящий отрезок — $A = [4; 40]$, его длина равна $40 - 4 = 36$.

def ok(a, b, step=0.5):
    for i in range(0, 200):
        x = i * step
        A = a <= x <= b
        B = 4 <= x <= 18
        C = 12 <= x <= 40
        if not (A or (B == C)):
            return False
    return True

print(ok(4, 40))      # True
print(ok(4.5, 40))    # False

Ответ: 36

Решение:

Применим правило $F(n) = n \cdot (n-1) \cdot F(n-1)$ три раза подряд:

$$F(123) = 123 \cdot 122 \cdot F(122) = 123 \cdot 122 \cdot 122 \cdot 121 \cdot F(121) = 123 \cdot 122 \cdot 122 \cdot 121 \cdot 121 \cdot 120 \cdot F(120).$$

Значит частное не зависит от самого $F(120)$:

$$\frac{F(123)}{F(120)} = 123 \cdot 122^{2} \cdot 121^{2} \cdot 120 = 15006 \cdot 14762 \cdot 14520 = 3216449665440.$$

print(123 * 122 * 122 * 121 * 121 * 120)   # 3216449665440

Ответ: 3216449665440

Решение:

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

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

Решение:

Позиция игры описывается одним числом $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

Решение:

Напомним игру: позиция (x, y) — две кучи; своим ходом игрок добавляет в одну из куч два камня либо удваивает одну из куч; игра заканчивается, когда в кучах суммарно окажется не менее 122 камней. В начале первая куча — 3 камня, вторая — S камней.

За один ход сумма растёт на 2, на x или на y, значит игрок заканчивает игру своим ходом тогда и только тогда, когда $x+y+\max(x,\,y,\,2) \ge 122$. В интересующих нас позициях вторая куча больше, поэтому условие принимает вид $x+2y \ge 122$.

Чтобы выиграть вторым ходом, Петя должен передать Ване проигрышную позицию: из неё Ваня закончить игру не может, но любой его ход отдаёт победу Пете. Слабейший ход Вани — «+2» в первую кучу, после него нужно $x+2+2y \ge 122$, то есть $x+2y \ge 120$; а чтобы сам Ваня не выиграл, нужно $x+2y \le 121$. Итак, проигрышные позиции — те, где $x+2y$ равно 120 или 121 (остальные ходы Вани увеличивают сумму ещё сильнее, так что после них Петя тем более заканчивает игру).

S = 57. Позиция (3, 57): $3+2\cdot 57 = 117 \lt 122$ — сам Петя не выигрывает. Он добавляет два камня во вторую кучу: (3, 59), где $3+2\cdot 59 = 121$. Любой ответ Вани проигрышен: (5, 59) даёт $5+118=123$, (3, 61) даёт $3+122=125$, (6, 59) даёт $6+118=124$, (3, 118) — тем более; во всех случаях Петя вторым ходом удваивает бо́льшую кучу и набирает не менее 122 камней. (Годится и ход «удвоить первую кучу»: (6, 57), где $6+114=120$.)

S = 58. Позиция (3, 58): $3+116=119 \lt 122$. Петя добавляет два камня в первую кучу: (5, 58), где $5+2\cdot 58 = 121$ — снова проигрышная позиция. Другие ходы не годятся: после (3, 60) получается $3+120=123$, после (6, 58) — $6+116=122$, то есть Ваня выигрывает сразу; ход (3, 116) очевидно проигрышный.

Меньших значений нет, что подтверждает перебор:

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

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

def win1(p):                      # ходящий заканчивает игру своим ходом
    return any(x + y >= N for x, y 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))

print([s for s in range(1, 118) if win2((A, s))][:2])   # [57, 58]

Ответ: 57 58

Решение:

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

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

• $W_1$ — ходящий выигрывает своим первым ходом, то есть одним ходом заканчивает игру;
• $L_1$ — ходящий сразу выиграть не может, а любой его ход отдаёт сопернику позицию из $W_1$; значит, соперник выигрывает своим первым ходом;
• $W_2$ — ходящий сразу выиграть не может, но у него есть ход в $L_1$, поэтому он выигрывает своим вторым ходом;
• $L_2$ — ходящий сразу выиграть не может, и каждый его ход ведёт в $W_1$ или в $W_2$; значит, соперник выигрывает первым или вторым своим ходом.

Первым ходит Петя, поэтому два условия задачи вместе означают: стартовая позиция принадлежит $L_2$, но не принадлежит $L_1$ — иначе Ваня гарантированно выигрывал бы первым ходом. Нужно наименьшее такое $S$. Проще всего перебрать все $S$ программой, вычисляя $W_1$, $L_1$, $W_2$, $L_2$ прямо по этим определениям:

N = 144

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

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

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

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

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

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

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

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

• $(2;\ 69)$ — Ваня выигрывает сразу: одним ходом он получает $(3;\ 69)$, а это уже не меньше 144;
• $(1;\ 70)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(1;\ 71)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(2;\ 71)$ — в $(3;\ 71)$; из $(1;\ 72)$ — в $(2;\ 72)$; из $(1;\ 142)$ — в $(2;\ 142)$);
• $(1;\ 138)$ — Ваня выигрывает сразу: одним ходом он получает $(2;\ 138)$, а это уже не меньше 144.

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

Ответ: 69

Решение:

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

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

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

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

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

finish = {}
for i in sorted(data):
    dur, deps = data[i]
    finish[i] = max([finish[d] for d in deps], default=0) + dur

print(max(finish.values()))

Наибольшее значение в последнем столбце равно 17 мс (его даёт процесс 8) — это и есть минимальное время выполнения всей совокупности процессов. Ответ: 17

Решение:

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

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

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

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

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

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

$x$	18	17	16	15	14	13	12	11	10
$R(x)$	1	0	1	2	3	4	5	6	7

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

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

from functools import lru_cache

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

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

Ответ: 98

Решение:

Алфавитный порядок для наших символов — это X, Y, Z. Значит «обратный алфавитный порядок» означает, что каждый следующий символ не идёт в алфавите позже предыдущего: $s_i\le s_{i-1}$ (нестрогое неравенство, потому что повторы разрешены). Для символов это обычное сравнение строк в Python.

Достаточно одного прохода по файлу: храним длину текущей подходящей серии cur. Если очередной символ не больше предыдущего, серия продолжается (cur += 1), иначе серия обрывается и новая начинается с текущего символа (cur = 1). Максимум из всех значений cur и есть ответ.

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

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

print(mx)

Программа выводит 19: в файле есть 19 подряд идущих символов, образующих невозрастающую цепочку (например, несколько Z, затем несколько Y, затем несколько X), а 20 таких подряд нет. Ответ: 19

Решение:

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

Число	$F$
850003	121422
850005	283332
850006	425001
850012	425004
850015	169998
850018	425007

Ответ: 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$ и $N$, далее идут $N$ объёмов посылок.

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)

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

629 50

Ответ: 629 50

Решение:

Из пункта с $t$ пробирками уезжает $w=\lceil t/36 \rceil$ контейнеров: контейнер вмещает не более 36 пробирок и вскрывается только в лаборатории, поэтому «недогруженный» контейнер всё равно нужен. В Python это удобно записать как -(-t // 36).

Если лабораторию открыть в пункте с номером $x_j$, то стоимость доставки равна $$C(j)=\sum_{i} w_i\,|x_i-x_j|.$$ Перебирать все пункты и для каждого считать сумму — это $O(N^2)$, для файла B слишком долго. Раскроем модуль: пункты слева от $j$ дают $x_j\sum_{i\lt j} w_i-\sum_{i\lt j} w_i x_i$, пункты справа дают $\sum_{i\gt j} w_i x_i-x_j\sum_{i\gt j} w_i$. Пункты в файле уже перечислены в порядке возрастания номера, поэтому, идя по ним слева направо и поддерживая четыре величины — $\sum w_i$ и $\sum w_i x_i$ слева и справа, — мы вычисляем $C(j)$ за $O(1)$ для каждого пункта, а весь ответ — за $O(N)$.

def solve(name, cap=36):
    f = open(name)
    n = int(f.readline())
    x = [0] * n          # номера пунктов (они же расстояния от нулевой отметки)
    w = [0] * n          # число контейнеров в пункте
    for i in range(n):
        a, b = map(int, f.readline().split())
        x[i] = a
        w[i] = -(-b // cap)          # округление вверх: ceil(b / cap)
    wt = sum(w)
    xwt = sum(w[i] * x[i] for i in range(n))
    wl = 0               # сумма весов слева от текущего пункта
    xwl = 0              # сумма w*x слева от текущего пункта
    best = None
    for i in range(n):
        wr = wt - wl - w[i]
        xwr = xwt - xwl - w[i] * x[i]
        cost = x[i] * wl - xwl + xwr - x[i] * wr
        if best is None or cost < best:
            best = cost
        wl += w[i]
        xwl += w[i] * x[i]
    return best

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

Проверка на примере из условия (вместимость 96): числа контейнеров равны $2,3,1,1,1,2$, минимум достигается в пункте 2 и равен $2+0+3+5+6+16=32$ — совпадает с пояснением к заданию.Для файла A минимум равен $51\,063$ (лаборатория в пункте $563$), для файла B — $5\,634\,689\,219\,329$.Ответ: 51063 5634689219329