Вариант 8 · Сентябрь 2026

Решение:

Конъюнкция равна единице, только если истинны все множители: $y=1$; из $\neg(x \equiv w)$ следует $x \ne w$; а $z \lor \neg w$ означает, что при $w=1$ обязательно $z=1$.

Таких наборов ровно три: $(w,x,y,z)$ равно $(0,1,1,0)$, $(0,1,1,1)$ или $(1,0,1,1)$.

Во всех строках $y=1$, поэтому в столбце $y$ не может быть нулей. Нули есть в первом, третьем и четвёртом столбцах, значит $y$ — второй столбец.

Столбцы $w$ и $x$ всюду различаются, а в первой строке первый и третий столбцы оба равны 0 — такой парой они быть не могут. Значит один из столбцов $w$, $x$ — обязательно четвёртый, а переменной $z$ достаётся первый или третий столбец.

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

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

Тот же результат даёт перебор всех 24 расстановок переменных по столбцам:

from itertools import permutations, product

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

rows = [t for t in product([0, 1], repeat=4) if F(*t)]   # наборы (w, x, y, z) с F = 1

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

for cols in permutations('wxyz'):        # cols[i] — переменная в i-м столбце
    for order in permutations(rows, 3):  # какой набор какой строке фрагмента
        val = [dict(zip('wxyz', t)) for t in order]
        if all(frag[r][i] is None or frag[r][i] == val[r][cols[i]]
               for r in range(3) for i in range(4)):
            print(''.join(cols))
            break

Ответ: zywx

Решение:

Сумма набирается по таблице «Аренда», к строкам которой надо добавить сведения об автомобиле (по полю «ID автомобиля») и о клиенте (по полю «ID клиента»).

Шаг 1. В таблице «Клиенты» находим Сушкина Л. Н. и запоминаем его ID клиента.

Шаг 2. В таблице «Автомобили» ставим фильтр: Марка = «Nissan», Тип двигателя = «дизельный». Подходят семь машин — выписываем их ID автомобиля.

Шаг 3. В таблице «Аренда» оставляем строки, у которых ID клиента — из шага 1, ID автомобиля — из списка шага 2, а дата аренды попадает в первое полугодие, то есть с 1 января по 30 июня включительно.

Шаг 4. Таких операций оказывается четыре, на суммы 389, 205, 450 и 180 рублей. Складываем: $389 + 205 + 450 + 180 = 1224$ рубля. В таблице это делается формулой СУММЕСЛИМН или суммой отфильтрованного столбца «Сумма аренды, руб.».

Ответ: 1224

Решение:

Здесь, в отличие от обычной постановки, нужно, наоборот, нарушить условие Фано: код буквы Д должен быть началом какого-то из уже имеющихся кодов либо какой-то имеющийся код должен быть началом кода буквы Д. Дополнительно слово должно быть длиннее одного знака и не совпадать с кодами 00, 01, 10 и 111.

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

Проверяем его: слово 11 является началом кода 111 буквы Г, значит условие Фано действительно нарушается. Все требования выполнены, и других кандидатов длины 2 нет, так что выбирать наименьшее числовое значение не из чего.

Ответ: 11

Решение:

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

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

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

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

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

• $r=1$: $4N+2\ge 1088\Rightarrow N\ge 272$. Наименьшее число вида $4k+1$ — это $N=273$.
• $r=2$: $16N+4\ge 1088\Rightarrow N\ge 68$. Наименьшее число вида $4k+2$ — это $N=70$, $R=1124$.
• $r=3$: $16N+6\ge 1088\Rightarrow N\ge 68$. Наименьшее число вида $4k+3$ — это $N=71$, $R=1142$.
• $r=0$: $N=64$ даёт $R=1024$ — мало; следующее кратное четырём $N=68$ даёт $R=16\cdot 68+4=1092\ge 1088$ — подходит.

Обратим внимание на «ловушку»: $N=66$ даёт $R=1060$, а $N=67$ даёт $R=1078$ — оба меньше 1088. Наименьшее из чисел 273, 70, 71, 68 — это 68.

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

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

Ответ: 68

Решение:

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

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

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

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

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

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

Ответ: 100

Решение:

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

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

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

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

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

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

Ответ: 8

Решение:

Букв восемь, в алфавитном порядке: А, Г, И, Л, М, Н, О, Ф. Слово с номером $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

Решение:

В файле 6400 строк, в каждой шесть натуральных чисел. Строка подходит, если выполнены оба условия:

• ровно одно значение встречается в строке ровно два раза, а остальные четыре числа попарно различны — то есть среди шести чисел ровно одно «двойное» и ровно четыре «одиночных»;
• среднее арифметическое четырёх неповторяющихся чисел не превосходит суммы повторяющихся чисел; повторяющееся число $x$ стоит дважды, поэтому их сумма равна $2x$.

Проще всего перебрать строки программой, подсчитывая, сколько раз встречается каждое число (класс Counter):

import csv
from collections import Counter

count = 0
for row in csv.reader(open('data.csv'), delimiter=';'):
    nums = [int(x) for x in row]
    c = Counter(nums)
    twice = [v for v, k in c.items() if k == 2]   # значения, встречающиеся 2 раза
    once = [v for v, k in c.items() if k == 1]    # значения, встречающиеся 1 раз
    if len(twice) == 1 and len(once) == 4:
        if sum(once) / 4 <= 2 * twice[0]:
            count += 1
print(count)   # 2241

Условие len(twice) == 1 and len(once) == 4 как раз и означает «ровно одно число повторяется ровно два раза, остальные различны»: оно отбрасывает строки, где какое-то число встречается три и более раз или где повторяющихся пар несколько. Программа находит 2241 подходящую строку. Ответ: 2241

Решение:

Маска подсети — это 32-битное число, в котором сначала идут только единицы, а потом только нули: единицы отмечают биты адреса сети, нули — биты номера узла. Поэтому маска полностью задаётся длиной префикса, и перебрать нужно всего 33 варианта. Ключевое свойство конъюнкции: единица в адресе сети может стоять только там, где единицы есть и в адресе узла, и в маске.

Требуется сосчитать, сколько разных масок переводят данный адрес узла именно в этот адрес сети. Третьи байты двоично: узел 162 = 10100010, сеть 128 = 10000000.

Условий два. Единица сети на 1-й позиции требует единицы в маске. А единицы узла на 3-й и 7-й позициях в адресе сети погашены, значит там маска обязана иметь нули. Так как маска — это сплошной блок единиц, третий байт может быть только 10000000 (128) или 11000000 (192): уже байт 11100000 (224) сохранил бы единицу на 3-й позиции и дал бы третий байт сети 160.

ip = [168, 73, 162, 138]
net = [168, 73, 128, 0]

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

n, w = to_int(ip), to_int(net)
good = []
for k in range(33):                        # длина префикса маски
    m = (0xFFFFFFFF << (32 - k)) & 0xFFFFFFFF
    if n & m == w:
        good.append(m)
print(len(good))

Подходят ровно две маски: 255.255.128.0 и 255.255.192.0.Ответ: 2

Решение:

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

Один пароль из 9 символов занимает $9 \cdot 6 = 54$ бита. Число байт должно быть целым и минимальным: $54 = 8 \cdot 6 + 6$, поэтому под него отводится 7 байт.

На всех пользователей отведено одинаковое число байт, поэтому на одного пользователя приходится $1800 : 90 = 20$ байт.

Из них 7 байт занимает пароль, значит на дополнительные сведения остаётся $20 - 7 = 13$ байт.

import math

N = 26 + 26 + 10              # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(9 * i / 8)      # байт на пароль
print(1800 // 90 - b)         # доп. сведения, байт

Ответ: 13

Решение:

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

Здесь на каждом шаге цикла сначала выполняется заменить(111, 1), а затем одна из замен 21 → 12 или 12 → 1. Прогон на коротких строках «22 + $k$ единиц + 22» показывает, что начиная с $k=8$ результаты повторяются с периодом 8: $k=8$ — 121222, $k=9$ — 1212122, $k=10$ — 12121122, $k=11$ — 1122122, $k=12$ — 11221122, $k=13$ — 1121222, $k=14$ — 11212122, $k=15$ — 112121122, $k=16$ — снова 121222.

Так как $2024 = 8 \cdot 253$, то есть $2024$ кратно 8, ответ такой же, как при $k=8$ и $k=16$, — строка 121222.

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

s = "22" + "1" * 2024 + "22"
while "2111" in s or "1112" in s:
    s = zamenit(s, "111", "1")
    if "21" in s:
        s = zamenit(s, "21", "12")
    else:
        s = zamenit(s, "12", "1")
print(s)   # 121222

Ответ: 121222

Решение:

Обе команды только уменьшают число на экране, поэтому траектория строго убывает и одно и то же число не может встретиться в ней дважды. Значит, каждая подходящая программа однозначно разбивается на две независимые части: сначала число $31$ превращается в $12$, затем $12$ превращается в $2$. По правилу умножения искомое количество равно произведению количеств программ для этих двух участков.

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$. Если $x = y$, подходит только пустая программа, то есть $f(x, x) = 1$; если $x \lt y$, то $f(x, y) = 0$ — увеличивать число команды не умеют. Иначе первая команда переводит $x$ либо в $x - 1$, либо в $\left\lfloor x/2 \right\rfloor$, поэтому

$$f(x, y) = f(x - 1,\, y) + f\big(\left\lfloor x/2 \right\rfloor,\, y\big).$$

from functools import lru_cache

@lru_cache(None)
def f(x, y):          # сколько программ переводят число x в число y
    if x == y:
        return 1      # пустая программа
    if x < y:
        return 0      # число стало меньше нужного - обратно уже не вернуть
    return f(x - 1, y) + f(x // 2, y)

print(f(31, 12) * f(12, 2))

Получаем $f(31, 12) = 9$ и $f(12, 2) = 19$, то есть всего $9 \cdot 19 = 171$ программ. Ответ: 171

Решение:

Приведём выражение $49^7 + 7^{21} - 7$ к степеням семёрки: $49^7 = \left(7^2\right)^7 = 7^{14}$, поэтому $N = 7^{21} + 7^{14} - 7$.

Разберёмся с разностью: $7^{14} - 7 = 7\left(7^{13} - 1\right)$. Число $7^{13} - 1$ в семеричной системе — это 13 шестёрок, а умножение на 7 приписывает справа один ноль. Значит $7^{14} - 7$ записывается как 13 шестёрок и ноль.

Слагаемое $7^{21}$ ставит единицу в 21-м разряде и не задевает младшие разряды. Итоговая запись выглядит так:

$1\underbrace{0\ldots0}_{7}\underbrace{6\ldots6}_{13}0$

Шестёрок ровно 13.

n = 49**7 + 7**21 - 7
s = ''
while n:
    s = str(n % 7) + s
    n //= 7
print(s, s.count('6'))

Ответ: 13

Решение:

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

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

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

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

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

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

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

Ответ: 15

Решение:

Нечётная ветка использует сразу два предыдущих значения, поэтому считаем таблицу подряд, начиная с базы $F(1) = 1$.

Правила: при чётном $n$ берём $F(n) = n + F(n - 1)$; при нечётном $n \gt 1$ берём $F(n) = F(n - 1) + 2 F(n - 2)$.

Проверим первые шаги: $F(2) = 2 + 1 = 3$, $F(3) = 3 + 2 \cdot 1 = 5$, $F(4) = 4 + 5 = 9$, $F(5) = 9 + 2 \cdot 5 = 19$. Последний шаг: $F(19) = F(18) + 2 F(17) = 16411 + 2 \cdot 16393 = 49197$.

import sys
sys.setrecursionlimit(10000)

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

print(F(19))   # 49197

Ответ: 49197

Решение:

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

В приложенном файле поле имеет размер $20\times20$; стены обозначены утолщёнными линиями. Внутренних стен две:

• вертикальная — между 6-м и 7-м столбцами, в строках с 4-й по 15-ю (из этих клеток 6-го столбца нельзя пойти вправо);
• горизонтальная — между 17-й и 18-й строками, в столбцах с 12-го по 17-й (из этих клеток 17-й строки нельзя пойти вниз).

Скопируем содержимое таблицы в текстовый файл 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 == 16 and 11 <= j <= 16

# стена справа от клетки (i, j)
def wall_right(i, j):
    return j == 5 and 3 <= i <= 14

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

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

Программа выводит 721 640: максимальная сумма равна 721, минимальная — 640. Ответ: 721 640

Решение:

Позиция игры — пара чисел $(a,b)$. За один ход можно прибавить 2 камня к одной из куч или удвоить одну из куч. Игра заканчивается, когда суммарное количество камней достигает 142.

Из позиции $(a,b)$ ходящий заканчивает игру, если $a+b+2\ge142$, или $2a+b\ge142$, или $a+2b\ge142$, то есть если $(a+b)+\max(a,b,2)\ge142$: выгоднее всего удвоить бо́льшую кучу. Нужно наименьшее $S$, при котором у Пети есть ход, не заканчивающий игру, после которого Ваня выигрывает сразу.

Из начальной позиции $(2,S)$ Петя может получить позиции $(4,S)$ (и прибавление 2, и удвоение первой кучи дают одно и то же), $(2,S+2)$ и $(2,2S)$. Самая опасная — $(2,2S)$: Ваня удваивает вторую кучу ещё раз и получает сумму $2+4S$. Условие $2+4S\ge142$ даёт $4S\ge140$, то есть $S\ge35$.

Другие ходы требуют большего $S$: из $(2,S+2)$ сумма после хода Вани равна $2S+6\ge142$, откуда $S\ge68$; из $(4,S)$ — $4+2S\ge142$, $S\ge69$.

Проверим $S=35$. Петя ходит $(2,35)\to(2,70)$: сумма 72, игра продолжается. Ваня удваивает: $(2,140)$, сумма $142\ge142$ — победа первым ходом. Сам Петя выиграть сразу не мог: $2+35+35=72\lt142$. При $S\lt35$ такая ситуация невозможна.

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

def win1(p):
    return any(x + y >= 142 for x, y in moves(p))

for S in range(1, 139):
    if any(x + y < 142 and win1((x, y)) for x, y in moves((2, S))):
        print(S)
        break

Ответ: 35

Решение:

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

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

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

• $(15,\ 31)$ — Петя удваивает вторую кучу: $15 + 62 = 77$;
• $(14,\ 32)$ — Петя удваивает вторую кучу: $14 + 64 = 78$;
• $(28,\ 31)$ — Петя удваивает вторую кучу: $28 + 62 = 90$;
• $(14,\ 62)$ — Петя добавляет камень: $14 + 63 = 77$.

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

• $(9,\ 34)$ — Петя удваивает вторую кучу: $9 + 68 = 77$;
• $(8,\ 35)$ — Петя удваивает вторую кучу: $8 + 70 = 78$;
• $(16,\ 34)$ — Петя удваивает вторую кучу: $16 + 68 = 84$;
• $(8,\ 68)$ — Петя добавляет камень: $8 + 69 = 77$.

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

N = 77

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, 70) if win2((7, s))][:2])   # два наименьших

Ответ: 31 34

Решение:

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

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

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

def moves(p):
    a, b = p
    return [(a + 2, b), (2 * a, b), (a, b + 2), (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, 139):
    p = (2, s)
    if over(p):
        break
    if lose2(p) and not lose1(p):
        print(s)
        break

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

• $(4;\ 66)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(8;\ 66)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(10;\ 66)$ — в $(10;\ 132)$; из $(16;\ 66)$ — в $(16;\ 132)$; из $(8;\ 68)$ — в $(8;\ 136)$; из $(8;\ 132)$ — в $(10;\ 132)$);
• $(2;\ 68)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(4;\ 68)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(6;\ 68)$ — в $(6;\ 136)$; из $(8;\ 68)$ — в $(8;\ 136)$; из $(4;\ 70)$ — в $(4;\ 140)$; из $(4;\ 136)$ — в $(6;\ 136)$);
• $(2;\ 132)$ — Ваня выигрывает сразу: одним ходом он получает $(2;\ 264)$, а это уже не меньше 142.

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

Ответ: 66

Решение:

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

Для данных из файла получается такое расписание (12 процессов):

Теперь идём по шкале времени по одной миллисекунде и считаем, сколько процессов активно в каждый момент. Четыре процесса одновременно работают на двух участках: с 0 до 3 мс это процессы 1, 2, 9 и 10, а с 9 до 13 мс — процессы 4, 5, 11 и 12. Больше четырёх процессов не работает никогда.

Складываем длины этих участков: $3 + 4 = 7$ мс.

rows = [(1, 4, []), (2, 3, []), (3, 5, [1, 2]), (4, 7, [3]),
        (5, 6, [3]), (6, 2, [5]), (7, 5, [4, 6]), (8, 2, [7]),
        (9, 7, []), (10, 8, []), (11, 6, [9]), (12, 6, [10])]

dur = {i: t for i, t, d in rows}
dep = {i: d for i, t, d in rows}
start, finish = {}, {}

def calc(i):
    if i not in finish:
        start[i] = max([calc(j) for j in dep[i]], default=0)
        finish[i] = start[i] + dur[i]
    return finish[i]

for i in dur:
    calc(i)

total = 0
for t in range(max(finish.values())):        # такты по 1 мс
    if sum(start[i] <= t < finish[i] for i in dur) == 4:
        total += 1
print(total)   # 7

Ответ: 7

Решение.

Граф ориентированный и ациклический, веса рёбер положительны, поэтому кратчайший путь ищется алгоритмом Дейкстры (или динамикой по вершинам в топологическом порядке).

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

import heapq

edges = {}
for line in open('23.txt'):
    parts = line.split()
    if len(parts) != 3:
        continue
    a, b, w = int(parts[0]), int(parts[1]), float(parts[2])
    edges.setdefault(a, []).append((b, w))

dist = {1: 0.0}
queue = [(0.0, 1)]
while queue:
    d, u = heapq.heappop(queue)
    if d > dist.get(u, float('inf')):
        continue
    for v, w in edges.get(u, []):
        if d + w < dist.get(v, float('inf')):
            dist[v] = d + w
            heapq.heappush(queue, (dist[v], v))

print(int(dist[100]))

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

Решение:

Алфавитный порядок для наших символов — это 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

Решение:

Перебирать подряд все числа до $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 чисел.

Ответ: 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$ — наибольшая из всех возможных, поэтому если она не делится на 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