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

Решение:
Обратим внимание, что пункт E является уникальным объектом со степенью 2, следовательно, в таблице ему соответствует строка под номером 3. Аналогично, пункт D — это единственная вершина, имеющая степень 5, что позволяет однозначно сопоставить ей номер 6. В силу симметрии графа, вершины C и G, а также A и F, являются взаимозаменяемыми парами. Допустим, что пунктам C и G соответствуют номера 1 и 2 в произвольном порядке. В таком случае для вершин A и F остаются позиции 7 и 5. Последняя нераспределенная вершина B, таким образом, получает номер 4.

Ответ: 34

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

Решение:

Функция $F = \neg(x \rightarrow y) \lor \neg z \lor w$ — это дизъюнкция, поэтому удобно смотреть, когда она равна 0: все три слагаемых должны быть нулями, то есть одновременно $x \rightarrow y = 1$, $z = 1$ и $w = 0$.

Во всех трёх строках фрагмента $F = 0$, значит, в каждой из них $z = 1$, $w = 0$ и не бывает $x = 1$ при $y = 0$.

Шаг 1. Находим столбец z. В столбце переменной $z$ должны стоять единицы во всех трёх строках. Третий столбец во всех строках равен 0 — не подходит. Четвёртый столбец равен 1, 0, 0 — не подходит. Второй столбец в третьей строке равен 0 — не подходит. Остаётся первый столбец: $z$ — первый столбец (и в нём всюду единицы).

Шаг 2. Находим столбец w. В столбце $w$ должны стоять нули во всех трёх строках. Четвёртый столбец содержит единицу, поэтому $w$ — это либо второй, либо третий столбец.

Шаг 3. Отбрасываем лишние варианты. Здесь важно, что Миша выписал три различные строки таблицы.

• Пусть $w$ — второй столбец. Тогда $x$ и $y$ стоят в третьем и четвёртом столбцах. Если $x$ — четвёртый, то в первой строке $x = 1$, а $y$ — третий столбец, там 0; получается $x \rightarrow y = 0$ и $F = 1$ — противоречие. Если же $x$ — третий столбец, а $y$ — четвёртый, то во второй и третьей строках все четыре значения оказываются равны 1, 0, 0, 0, то есть строки совпадают — тоже противоречие.
• Значит, $w$ — третий столбец, а $x$ и $y$ стоят во втором и четвёртом. Если $x$ — второй, а $y$ — четвёртый, то во второй строке $y = 0$, поэтому $x = 0$; в третьей строке тоже $y = 0$, а $x$ во втором столбце задан нулём. Обе строки снова превращаются в 1, 0, 0, 0 — совпадение, чего быть не может.

Остаётся единственный вариант: $x$ — четвёртый столбец, $y$ — второй. Проверим его: в первой строке $z = 1$, $x = 1$, значит, $y = 1$; во второй $x = 0$, и $y$ можно взять равным 1; в третьей $x = 0$, $y = 0$. Получаются три различные строки, и во всех $F = 0$.

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

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

from itertools import permutations, product

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

frag = [((None, None, 0, 1), 0),
        ((None, None, 0, 0), 0),
        ((None, 0, 0, 0), 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

Ответ: zywx

Решение:

Нужная величина складывается из строк таблицы «Готовый товар», поэтому к ней надо «подтянуть» сведения из двух справочников: о ткани — по полю «ID ткани», о модели — по полю «ID товара».

Шаг 1. В таблице «Ткани» включаем фильтр: Цвет = «красный», Сырьё = «хлопок», Плотность $\ge 195$ г/м². Условию удовлетворяют три ткани — бархат (405 г/м²), вельвет (410 г/м²) и джинса (420 г/м²). Выписываем их ID ткани.

Шаг 2. В таблице «Продукция» отбираем все модели, в наименовании которых есть слово «платье» (платье прямое, платье миди, платье-халат, платье-сарафан и т. д.). Категория потребителей в условии не ограничена, поэтому берём и детские, и женские модели.

Шаг 3. В таблице «Готовый товар» функцией ВПР добавляем к каждой строке цвет, сырьё и плотность ткани (по «ID ткани») и наименование модели (по «ID товара»), а затем оставляем строки, у которых ткань из шага 1 и наименование из шага 2. Таких строк 27.

Шаг 4. Стоимость одной строки равна произведению количества на складе и отпускной цены. Итоговую сумму удобно получить формулой СУММПРОИЗВ по двум столбцам отобранных строк (или добавить столбец с произведением и просуммировать его). Получается 1453717 рублей.

Ответ: 1453717

Решение:

Условие Фано означает, что ни одно кодовое слово не является началом другого. Перебираем кандидатов для буквы И по возрастанию длины, а внутри одной длины — по возрастанию числового значения.

Длина 1. Слово 0 — начало кода 000 (буква А); слово 1 — начало кода 101 (буква З). Не подходят.

Длина 2. Слово 00 — начало 000; 01 — начало 010 (Б); 10 — начало 101 (З); 11 — начало 11011 (Е) и 11010 (Ж). Не подходит ни одно.

Длина 3. Слово 000 занято буквой А; 001 — начало кода 00100 (Г); 010 занято буквой Б; 011 — начало кода 01111 (Д); 100 — начало кода 10001 (В); 101 занято буквой З; 110 — начало кодов 11011 и 11010. Остаётся слово 111: ни один имеющийся код с него не начинается и ни один код не является его началом. Оно подходит.

Ответ: 111

Решение:

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

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

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

Условие $R\lt 64$ даёт $4M\le 4M+2p\lt 64$, то есть $M\lt 16$. С учётом кратности четырём получаем $M\le 12$.

Проверим $M=12=1100_2$: единиц две, $p=0$, запись $1100\to 11000\to 110000$, то есть $R=48\lt 64$ — подходит. Следующее значение $M=16=10000_2$ даёт $p=1$ и $R=4\cdot 16+2=66$ — уже не подходит.

Значит, $N-(N\bmod 4)=12$. Этому равенству удовлетворяют $N=12,\ 13,\ 14,\ 15$; наибольшее из них — 15.

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

print(max(n for n in range(1, 1000) if alg(n) < 64))

Ответ: 15

Решение:

Хвост поднят, поэтому Вперёд 100 Направо 90 Вперёд 100 только переводит Черепаху в точку $(100;100)$. После Направо 45 голова смотрит под углом $-45^{\circ}$ к оси $Ox$, и хвост опускается.

Цикл замыкается за два повтора: рисуется прямоугольник $20\times 30$, повёрнутый на $45^{\circ}$, с вершинами $(100;100)$, $(100+10\sqrt{2};\,100-10\sqrt{2})$, $(100-5\sqrt{2};\,100-25\sqrt{2})$, $(100-15\sqrt{2};\,100-15\sqrt{2})$.

Все стороны имеют угловые коэффициенты $\pm 1$, поэтому в переменных $s=x+y$ и $d=x-y$ условие «строго внутри» становится совсем простым:

$$200-30\sqrt{2}\lt s\lt 200,\qquad 0\lt d\lt 20\sqrt{2}.$$

Так как $30\sqrt{2}\approx 42{,}43$ и $20\sqrt{2}\approx 28{,}28$, подходят целые $s=158,159,\dots,199$ (42 значения) и $d=1,2,\dots,28$ (28 значений).

Пара $(s;d)$ отвечает целой точке $x=\dfrac{s+d}{2}$, $y=\dfrac{s-d}{2}$ тогда и только тогда, когда $s$ и $d$ одной чётности. Среди значений $s$ — 21 чётное и 21 нечётное, среди значений $d$ — 14 чётных и 14 нечётных.

Итого $21\cdot 14+21\cdot 14=588$. Проверим программой:

from math import sin, cos, radians

P = [(0.0, 0.0)]
x = y = 0.0
a = 90.0                      # голова смотрит вдоль оси Oy

def F(n):                     # Вперёд n
    global x, y
    x = round(x + n * cos(radians(a)), 9)   # round убирает шум float
    y = round(y + n * sin(radians(a)), 9)
    P.append((x, y))

def R(m):                     # Направо m
    global a
    a -= m

F(100); R(90); F(100); R(45)  # хвост поднят - это не рисуется
P = [(x, y)]                  # опустили хвост
for i in range(2):            # прямоугольник замыкается за 2 повторения
    F(20); R(90); F(30); R(90)

def inside(px, py):           # фигура выпуклая, обход по часовой стрелке
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        if (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1) >= -1e-9:
            return False      # точка на линии или снаружи
    return True

xs = [p[0] for p in P]; ys = [p[1] for p in P]
print(sum(inside(px, py)
          for px in range(int(min(xs)) - 1, int(max(xs)) + 2)
          for py in range(int(min(ys)) - 1, int(max(ys)) + 2)))

Ответ: 588

Решение:

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

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

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

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

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

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

Ответ: 128

Решение:

Пятизначное восьмеричное число — это набор из пяти цифр $0\ldots7$, у которого первая цифра не ноль. Нужно, чтобы цифра 4 встречалась ровно дважды и чтобы у каждой четвёрки оба соседа были чётными. Обратите внимание: сама цифра 4 чётная, поэтому две четвёрки рядом стоять могут.

Условие короче всего проверить полным перебором всех $8^5 = 32\,768$ наборов.

from itertools import product

count = 0
for d in product(range(8), repeat=5):
    if d[0] == 0:
        continue
    if d.count(4) != 2:
        continue
    ok = True
    for i in range(5):
        if d[i] == 4:
            if i > 0 and d[i - 1] % 2 == 1:
                ok = False
            if i < 4 and d[i + 1] % 2 == 1:
                ok = False
    if ok:
        count += 1
print(count)

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

Решение:

Откроем файл. В строке 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). В окне поиска вводим красавица и обязательно включаем режим «Только слово целиком» — иначе редактор посчитает и формы «красавицу», «красавицей», «красавицы», которые по условию учитывать не нужно. Флажок «Учитывать регистр» ставить не надо: подходят и «красавица», и «Красавица».

Поиск целого слова находит 6 отдельных вхождений. Кроме того, слово входит в состав сложного существительного «дочка-красавица», написанного через дефис, — по условию такие вхождения тоже учитываются. Дефис считается границей слова, поэтому это седьмое вхождение.

Итого $6 + 1 = 7$.

Проверка программой: границей слова считаем всё, кроме русских букв, поэтому дефис границу образует, а окончания «-у», «-ей» — нет.

import re

text = open('text.txt', encoding='cp1251').read()
matches = re.findall(r'(?<![А-Яа-яЁё])[Кк]расавица(?![А-Яа-яЁё])', text)
print(len(matches))   # 7

Ответ: 7

Решение:

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

Один идентификатор из 331 символ занимает $331 \cdot 10 = 3310$ бит. Число байт должно быть целым и минимальным: $3310 = 8 \cdot 413 + 6$, поэтому под него отводится 414 байт.

Все 1536 идентификаторов занимают $1536 \cdot 414 = 635904$ байта, то есть $635904 : 1024 = 621$ Кбайт.

import math

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

Ответ: 621

Решение:

В строке встречаются только цифры 8 и 2, поэтому весь процесс описывается двумя правилами: пока есть цепочка 2222, она заменяется на 88, иначе первая слева цепочка 8888 заменяется на 22.

Посмотрим, что происходит со строкой из $n$ восьмёрок при $n\ge 8$:

• цепочки 2222 нет, поэтому заменяется 8888 на 22: получаем 22 и $n-4$ восьмёрок;
• двух двоек мало для цепочки 2222, снова срабатывает 8888 → 22: получаем 2222 и $n-8$ восьмёрок;
• теперь есть 2222, она заменяется на 88: получаем 88 и $n-8$ восьмёрок, то есть ровно $n-6$ восьмёрок.

Итак, пока восьмёрок не меньше восьми, их количество каждый раз уменьшается на 6. Начиная с 70, получаем цепочку

70 → 64 → 58 → 52 → 46 → 40 → 34 → 28 → 22 → 16 → 10 → 4.

Осталось 4 восьмёрки. Цепочки 2222 нет, срабатывает замена 8888 → 22, после чего в строке 22 ни одной из искомых цепочек нет и цикл завершается.

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

s = '8' * 70
while '2222' in s or '8888' in s:
    if '2222' in s:
        s = s.replace('2222', '88', 1)
    else:
        s = s.replace('8888', '22', 1)
print(s)      # 22

Ответ: 22

Решение:

IP-адрес 44.44.229.28, адрес сети 44.44.224.0. Маска состоит из идущих подряд единиц, а затем нулей.

Первые два байта адреса и сети совпадают, поэтому в маске они могут быть равны 255.255 — это 16 единиц.

Третий байт: $229 = 11100101_2$, в адресе сети $224 = 11100000_2$. Проверяем префиксные маски третьего байта:

• $11100000_2 = 224$: $229 \wedge 224 = 224$ — подходит (3 единицы);
• $11110000_2 = 240$: $229 \wedge 240 = 224$ — подходит (4 единицы, так как четвёртый бит числа 229 нулевой);
• $11111000_2 = 248$: $229 \wedge 248 = 224$ — подходит (5 единиц);
• $11111100_2 = 252$: $229 \wedge 252 = 11100100_2 = 228 \ne 224$ — не подходит.

Значит, в третьем байте маски не более 5 единиц. Так как третий байт маски не равен 255, четвёртый байт обязан быть нулевым.

Наибольшее число единиц: $8 + 8 + 5 + 0 = 21$ (маска 255.255.248.0).

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

Ответ: 21

Решение:

Приведём всё к степеням четвёрки: $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\big(P \rightarrow Q\big)$ ложно при всех $x$ тогда и только тогда, когда сама импликация $P \rightarrow Q$ истинна при всех $x$, где $P = (x \in B) \lor (x \in C)$, а $Q = (x \in A)$.

Импликация истинна всюду, если из $P$ следует $Q$, то есть если отрезок $A$ содержит всё объединение

$B \cup C = [10;\ 15] \cup [20;\ 27]$.

Так как $A$ — отрезок (связное множество), он обязан содержать и промежуток между $B$ и $C$. Наименьший отрезок, включающий обе части, — это $[10;\ 27]$.

Его длина $27 - 10 = 17$.

Ответ: 17

Решение:

Сначала найдём $F(2)$, которое входит в правило для нечётных $n$: число 2 чётное и $2 \gt 1$, поэтому $F(2) = 3 \cdot F(1) = 3$. Значит при нечётном $n \gt 1$ правило принимает вид $F(n) = 5n + F(n-1) + 3$.

Каждое значение зависит только от предыдущего, поэтому просто идём по возрастанию $n$:

$F(1) = 1$, $F(2) = 3 \cdot 1 = 3$, $F(3) = 5 \cdot 3 + 3 + 3 = 21$, $F(4) = 3 \cdot 21 = 63$, $F(5) = 5 \cdot 5 + 63 + 3 = 91$, $F(6) = 3 \cdot 91 = 273$ и так далее.

n	F(n)
1	1
2	3
3	21
4	63
5	91
6	273
7	311
8	933
9	981
10	2943
11	3001
12	9003
13	9071
14	27213
15	27291
16	81873
17	81961
18	245883
19	245981
20	737943
21	738051
22	2214153
23	2214271

Последний шаг: $F(23) = 5 \cdot 23 + F(22) + 3 = 115 + 2214153 + 3 = 2214271$.

from functools import lru_cache

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

print(F(23))   # 2214271

Ответ: 2214271

Решение:

Читаем файл в список и перебираем пары соседних элементов $(a_i,\ a_{i+1})$.

Последнюю цифру берём как остаток от деления модуля числа на 10: у отрицательных чисел в Python обычный остаток даёт не ту цифру (например, $-9578 \bmod 10 = 2$, а оканчивается число на 8).

Пара подходит, если у обоих чисел последние цифры совпадают и нечётны. Среди таких пар ищем максимальное произведение модулей.

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

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

print(count, best)   # 227 96784219

Получаем 227 пар, наибольшее произведение модулей — 96784219.Ответ: 227 96784219

Решение:

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

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

В приложенном файле поле имеет размер $16\times16$. Единственная внутренняя стена (утолщённая линия) — горизонтальная, между 6-й и 7-й строками в столбцах с 5-го по 10-й: в эти клетки 7-й строки нельзя попасть сверху, только слева.

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

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

# стена снизу от клетки (i, j); строки и столбцы нумеруются с нуля
def wall_down(i, j):
    return i == 5 and 4 <= j <= 9

# стена справа от клетки (i, j) — вертикальных внутренних стен нет
def wall_right(i, j):
    return False

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

print(MN[N - 1][N - 1], MX[N - 1][N - 1])

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

Решение:

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

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

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

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

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

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

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

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

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

Ответ: 18

Решение:

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

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

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

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

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

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

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

N = 202

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

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

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

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

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

Ответ: 63 66

Решение:

Как и в предыдущих пунктах, из кучи в $n$ камней ($n \le 128$) ходящий выигрывает одним ходом ровно при $n \ge 65$, а позиция 64 проигрышна для того, кто из неё ходит: она ведёт только в 65 или 128, откуда соперник побеждает.

Чтобы у Вани вообще была стратегия, Петя не должен выигрывать первым ходом, то есть $S \le 64$. После хода Пети куча равна $m = S + 1$ или $m = 2S$, и для каждого из этих двух вариантов Ваня должен побеждать не позже своего второго хода. Это возможно в двух случаях: либо $m \ge 65$ и Ваня выигрывает сразу, либо Ваня может перевести игру в проигрышную позицию 64, то есть $m + 1 = 64$ или $2m = 64$, что даёт $m = 63$ или $m = 32$.

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

Перебираем: $2S$ чётно, поэтому равенство $2S = 63$ невозможно, остаётся либо $2S = 32$ (то есть $S = 16$, но тогда $S + 1 = 17$ не подходит ни под один случай), либо $2S \ge 65$, то есть $S \ge 33$. При $S \ge 33$ число $S + 1$ должно быть равно 63 или быть не меньше 65, откуда $S = 62$ или $S \ge 64$. Значение $S = 64$ отпадает: там оба хода Пети дают 65 и 128, и Ваня выигрывает уже первым ходом, что запрещено вторым условием.

Остаётся $S = 62$. Проверка: Петя получает 63 или 124. Из 124 Ваня выигрывает сразу удвоением (248), а из 63 сразу выиграть не может (64 и 126 меньше 129), зато ходит в 64, после чего Петя вынужден отдать 65 или 128, и Ваня побеждает вторым ходом.

def win_now(s):
    return s + 1 >= 129 or 2 * s >= 129

def loses(s):        # ходящий из s проигрывает: любой его ход дарит победу сопернику
    return not win_now(s) and all(win_now(m) for m in (s + 1, 2 * s))

for s in range(1, 129):
    if win_now(s):
        continue
    two = all(win_now(m) or loses(m + 1) or loses(2 * m) for m in (s + 1, 2 * s))
    one = all(win_now(m) for m in (s + 1, 2 * s))
    if two and not one:
        print(s)     # 62
        break

Ответ: 62

Решение:

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

Решение:

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

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

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

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

$k$ — команд В	$n$ — команд А	Количество программ $C_{n+k}^{\,k}$
0	22	$C_{22}^{0} = 1$
2	15	$C_{17}^{2} = 136$
4	8	$C_{12}^{4} = 495$
6	1	$C_{7}^{6} = 7$

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

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

from functools import lru_cache

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

print(f(5, 49))

Ответ: 639

Решение:

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

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

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

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

print(mx)

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

Решение:

Перебирать подряд все числа до $10^{10}$ не нужно: искомое число обязано делиться на 31007, поэтому переберём сразу кратные $n=31007k$ — их всего $\lfloor 10^{10}/31007\rfloor=322507$, это мгновенно.

Проверку маски удобно поручить модулю fnmatch: в его шаблонах ? означает ровно один символ, а * — любую, в том числе пустую, последовательность символов, то есть ровно то, что написано в условии. Число превращаем в строку и сравниваем с маской 1*34?5?9.

from fnmatch import fnmatch

for k in range(1, 10 ** 10 // 31007 + 1):
    n = 31007 * k
    if fnmatch(str(n), '1*34?5?9'):
        print(n, k)

Маска 1*34?5?9 читается так: первая цифра 1, дальше произвольный (возможно, пустой) кусок, затем 34, любая цифра, 5, любая цифра и 9 в конце. Программа находит 5 чисел.

Число	Частное от деления на 31007
1260341529	40647
1291348529	41647
1300340559	41937
1331347559	42937
1371346589	44227

Ответ: 1260341529 40647 1291348529 41647 1300340559 41937 1331347559 42937 1371346589 44227

Решение:

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

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

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

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

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)

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

3098 80

Ответ: 3098 80

Решение:

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

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

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

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

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

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