Вариант 6 · Октябрь 2026

Решение:

Дизъюнкция равна нулю только тогда, когда равно нулю каждое слагаемое. Значит во всех трёх строках $z=0$, выражение $w \equiv y$ ложно, то есть $w \ne y$, и $\neg x \land y = 0$, то есть $x=1$ или $y=0$.

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

Так как $z=0$ везде, в столбце переменной $z$ не может быть единиц. Единицы есть в первом, втором и четвёртом столбцах, значит $z$ — третий столбец.

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

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

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

from itertools import permutations, product

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

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

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

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

Ответ: xyzw

Решение:

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

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

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

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

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

Ответ: 1453717

Решение:

Условие Фано нарушается, если новое кодовое слово является началом одного из используемых слов или одно из используемых слов является началом нового.

Заняты слова А — 00, Б — 01, В — 10, Г — 11, то есть все четыре двоичных слова длины 2. Слово из одного символа брать нельзя (символов должно быть больше одного), а совпадать с уже используемыми словами новое слово тоже не должно — значит, среди слов длины 2 подходящих нет.

Переходим к словам длины 3. Наименьшее числовое значение у слова 000. Проверяем его: слово 00 (буква А) является началом слова 000, поэтому условие Фано нарушается — это то, что требуется.

Значит, самое короткое подходящее слово с минимальным числовым значением — 000.

Ответ: 000

Решение:

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

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

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

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

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

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

Ответ: 61

Решение:

Алгоритм чертит два прямоугольника, а вопрос сводится к площади их общей части. Первая команда «Повтори 2» из начала координат при голове, направленной вверх, рисует прямоугольник со сторонами 8 (вверх) и 18 (вправо): его вершины — $(0;0)$, $(0;8)$, $(18;8)$, $(18;0)$.

С поднятым хвостом Черепаха проходит 4 вверх, поворачивает направо и проходит 10 вправо, то есть попадает в точку $(10;4)$; поворот налево снова направляет её голову вверх. Вторая команда «Повтори 2» чертит прямоугольник со сторонами 17 (вверх) и 7 (вправо): $(10;4)$, $(10;21)$, $(17;21)$, $(17;4)$.

Пересечение прямоугольников задаётся общими промежутками по осям: по $x$ это $[10;17]$, по $y$ — $[4;8]$. Значит, общая часть — прямоугольник $7\times4$, его площадь $7\cdot4=28$.

x1, x2 = max(0, 10), min(18, 17)   # общий отрезок по x: 10..17
y1, y2 = max(0, 4), min(8, 21)     # общий отрезок по y: 4..8
print((x2 - x1) * (y2 - y1))       # 28

Ответ: 28

Палитра 2²³ цветов – это 23 бита на пиксель. Исходный снимок: 1024 · 768 · 23 = 18 087 936 бит. Сжатый: 800 · 600 · 22 = 10 560 000 бит.

Экономия на одном снимке 7 527 936 бит, на 100 снимках 752 793 600 бит = 94 099 200 байт = 91 893,75 Кбайт. Целая часть – 91 893.

Ответ: 91893.

Решение:

Буквы в алфавитном порядке: А, В, О, П, Р. Слова четырёхбуквенные, поэтому со всякой фиксированной первой буквы начинается ровно $5^3 = 125$ слов.

Перед словами, начинающимися с П, идут все слова на А, В и О — это $3 \cdot 125 = 375$ слов. Значит, первое слово на букву П (это ПААА) имеет номер $375 + 1 = 376$.

То же самое через перевод в пятеричную систему (А=0, В=1, О=2, П=3, Р=4): ПААА → $3000_5 = 3 \cdot 125 = 375$, номер $375 + 1 = 376$.

from itertools import product

for n, w in enumerate(product('АВОПР', repeat=4), 1):
    if w[0] == 'П':
        print(n, ''.join(w))
        break

Ответ: 376

Решение:

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

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

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

В англоязычной версии редактора это =AVERAGE(B2:Y92)-MIN(B2:Y92).

Получаем $10{,}4502\ldots - 0{,}3 = 10{,}1502\ldots$ Целая часть равна 10.

То же самое на Python (для CSV-версии файла):

import csv

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

print(sum(values) / len(values) - min(values))   # 10.1502...

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

Ответ: 10

Решение:

Маска — это несколько единиц подряд, а затем нули. Там, где в маске стоит единица, бит адреса сети совпадает с битом адреса узла; там, где ноль, бит адреса сети обязан быть нулевым. Запишем оба адреса в двоичном виде:

узел: 01111111.01110110.10000111.11111100
сеть: 01111111.01110110.10000110.00000000

Первое расхождение — в восьмом бите третьего байта (24-й бит адреса): у узла там 1, у сети 0. Этот бит уже должен попасть в нулевую часть маски, поэтому единиц в маске не больше 23. С другой стороны, последняя единица адреса сети стоит в 23-м бите, и она обязана попасть в единичную часть маски, значит единиц не меньше 23. Остаётся единственная возможность — 23 единицы (маска 255.255.254.0).

def ip(a, b, c, d):
    return ((a * 256 + b) * 256 + c) * 256 + d

node = ip(127, 118, 135, 252)
net = ip(127, 118, 134, 0)
for k in range(33):              # k — число единиц в маске
    mask = 2 ** 32 - 2 ** (32 - k)
    if (node & mask) == net:
        print(k)                 # 23

Ответ: 23

Решение:

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

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

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

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

import math

N = 52                        # мощность алфавита
i = math.ceil(math.log2(N))   # бит на один символ
b = math.ceil(7 * i / 8)      # байт на пароль
print(500 // 20 - b)          # доп. сведения, байт

Ответ: 19

Решение:

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

Посмотрим, как меняется количество единиц. Замена (11111, 15) убирает пять единиц и добавляет одну, то есть уменьшает число единиц ровно на 4, а замена (15, 1) число единиц не меняет (она лишь убирает пятёрку). Значит остаток количества единиц при делении на 4 сохраняется в течение всей работы программы.

Каждая пятёрка появляется только в паре «15», и после неё всегда стоит единица, поэтому в конце работы (когда не найдено ни 11111, ни 15) пятёрок в строке не остаётся вовсе, а единиц остаётся от 1 до 4. Так как $65 = 4 \cdot 16 + 1$, останется ровно одна единица.

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

s = "1" * 65
while "11111" in s or "15" in s:
    if "11111" in s:
        s = zamenit(s, "11111", "15")
    else:
        s = zamenit(s, "15", "1")
print(s)   # 1

Ответ: 1

Решение:

Обозначим через $R(x)$ количество программ, переводящих число $x$ в заданное конечное число. Из $x$ исполнитель может перейти либо в $x+1$ (команда 1), либо в $2x$ (команда 2), поэтому $$R(x)=R(x+1)+R(2x),$$ причём $R(\text{конечного числа})=1$ (пустая программа), а если $x$ уже больше конечного числа, то $R(x)=0$ — числа только растут.

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

1) Из 1 в 10. Считаем $R$ от 10 вниз к 1 (удвоение из $x\ge 6$ сразу перескакивает через 10, поэтому там остаётся только «прибавить 1»):

Например, $R(5)=R(6)+R(10)=1+1=2$, $R(2)=R(3)+R(4)=4+3=7$, $R(1)=R(2)+R(2)=14$. Итого 14 программ.

2) Из 10 в 20. Для любого $x\ge 11$ удвоение даёт больше 20, значит $R(x)=R(x+1)=1$ для всех $x=11,\dots,20$. А из 10 можно и прибавлять единицы, и сразу удвоить: $R(10)=R(11)+R(20)=1+1=2$.

Итого $14\cdot 2=28$.

from functools import lru_cache

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

print(count(1, 10) * count(10, 20))

Ответ: 28

Решение:

Приведём всё к степеням четвёрки: $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

Решение:

Обозначим $P = \text{ТРЕУГ}(x, 11, 18)$, $Q = \neg(\text{МАКС}(x, 5) \gt 15)$, $R = \text{ТРЕУГ}(x, A, 5)$. Формула имеет вид $\neg((P \equiv Q) \land R)$ и тождественно истинна тогда и только тогда, когда при каждом натуральном $x$, для которого $P$ и $Q$ совпадают, значение $R$ ложно.

Находим $P$. Невырожденный треугольник со сторонами $x$, 11 и 18 существует, когда $x + 11 \gt 18$ и $11 + 18 \gt x$, то есть при $7 \lt x \lt 29$. Значит $P = 1$ при $8 \le x \le 28$.

Находим $Q$. При $x \le 5$ имеем $\text{МАКС}(x, 5) = 5$, иначе $\text{МАКС}(x, 5) = x$. Поэтому условие $\text{МАКС}(x, 5) \gt 15$ равносильно $x \gt 15$, и $Q = 1$ при $x \le 15$.

Сравним $P$ и $Q$ по участкам:

Итак, $R = \text{ТРЕУГ}(x, A, 5)$ должно быть ложно при всех $x$ из отрезка $[8; 15]$ и при всех $x \ge 29$.

Треугольник со сторонами $x$, $A$ и 5 существует, когда $x + 5 \gt A$ и $A + 5 \gt x$, то есть при $A - 5 \lt x \lt A + 5$.

Условие «$R$ ложно при всех $x \ge 29$» требует $A + 5 \le 29$, откуда $A \le 24$.

Проверим $A = 24$: треугольник существует лишь при $19 \lt x \lt 29$, а точки $8 \le x \le 15$ и $x \ge 29$ в этот промежуток не попадают. Значит $A = 24$ подходит и является наибольшим.

def treug(a, b, c):
    a, b, c = sorted((a, b, c))
    return a + b > c

best = 0
for A in range(1, 100):
    if all(not ((treug(x, 11, 18) == (not (max(x, 5) > 15))) and treug(x, A, 5))
           for x in range(1, 1000)):
        best = A
print(best)   # 24

Ответ: 24

Решение:

Считать $F(2024)$ и $F(2022)$ по отдельности не нужно: в разности почти всё сократится. Раскроем соотношение $F(n) = 2n + 1 + F(n - 1)$ два раза.

$$F(2024) = 2 \cdot 2024 + 1 + F(2023) = 4049 + F(2023),$$

$$F(2023) = 2 \cdot 2023 + 1 + F(2022) = 4047 + F(2022).$$

Подставим второе равенство в первое:

$$F(2024) = 4049 + 4047 + F(2022) = 8096 + F(2022).$$

Отсюда $F(2024) - F(2022) = 8096$. Обратите внимание: базовое значение $F(1) = 5$ в ответ не входит вовсе.

def F(n):
    r = 5
    for i in range(2, n + 1):
        r = 2 * i + 1 + r
    return r

print(F(2024) - F(2022))   # 8096

Ответ: 8096

Решение:

Достаточно перебрать все целые числа отрезка $[1016;\ 7937]$ и проверить четыре условия: число делится на 3, но не делится ни на 7, ни на 17, ни на 19, ни на 27. (Условие «не делится на 27» отсеивает часть кратных 3.)

count = 0
last = 0
for n in range(1016, 7938):
    if n % 3 == 0 and n % 7 != 0 and n % 17 != 0 and n % 19 != 0 and n % 27 != 0:
        count += 1
        last = n          # числа идут по возрастанию, поэтому последнее и есть максимальное

print(count, last)   # 1568 7935

Максимум можно найти и вручную, спускаясь от правого конца отрезка: 7937 и 7936 не делятся на 3, а $7935 = 3 \cdot 2645$ делится на 3 и при этом не делится ни на 7 ($7935 = 7 \cdot 1133 + 4$), ни на 17 ($7935 = 17 \cdot 466 + 13$), ни на 19 ($7935 = 19 \cdot 417 + 12$), ни на 27 ($7935 = 27 \cdot 293 + 24$). Значит наибольшее число — 7935.

В электронных таблицах то же самое делается формулой: в столбце A — числа от 1016 до 7937, в столбце B — проверка =ЕСЛИ(И(ОСТАТ(A1;3)=0; ОСТАТ(A1;7)<>0; ОСТАТ(A1;17)<>0; ОСТАТ(A1;19)<>0; ОСТАТ(A1;27)<>0);A1;0), затем СЧЁТЕСЛИ и МАКС по столбцу B.

Ответ: 1568 7935

Решение:

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

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

Решение:

Позицию обозначаем (x, y), а следить будем за произведением $xy$. Посмотрим, как его меняет ход: $(x+1)y = xy+y \le 2xy$ и $x(y+1) = xy+x \le 2xy$ (ведь $x \ge 1$ и $y \ge 1$), а удвоение любой кучи даёт ровно $2xy$. Значит одним ходом произведение увеличивается не более чем вдвое, и удвоение кучи этот максимум как раз даёт.

Отсюда: игрок заканчивает игру своим ходом тогда и только тогда, когда $2xy \ge 144$, то есть когда $xy \ge 72$.

В начальной позиции (1, S) произведение равно $S$. После хода Пети оно не больше $2S$, после ответного хода Вани — не больше $4S$. Значит Ваня способен закончить игру своим первым ходом тогда и только тогда, когда $4S \ge 144$, то есть при $S \ge 36$.

Проверим $S = 36$. Сам Петя не выигрывает: максимум, что он может, — довести произведение до $2\cdot36 = 72$, а нужно 144. Но если он удвоит вторую кучу, возникнет позиция (1, 72) с произведением 72; Ваня удваивает её ещё раз и получает (1, 144) с произведением 144 — игра закончена, выиграл Ваня.

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

N = 144

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, 143):
    p = (1, s)
    # сам Петя выиграть не может, но неудачным ходом дарит победу Ване
    if not win1(p) and any(win1(q) for q in moves(p)):
        print(s)                  # 36
        break

Ответ: 36

Решение:

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

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

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

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

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

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

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

N = 301

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

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

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

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

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

Ответ: 75 149

Решение:

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

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

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

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, 54):
    p = (5, s)
    if over(p):
        break
    if lose2(p) and not lose1(p):
        print(s)
        break

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

• $(6;\ 23)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(12;\ 23)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(13;\ 23)$ — в $(13;\ 46)$; из $(24;\ 23)$ — в $(48;\ 23)$; из $(12;\ 24)$ — в $(12;\ 48)$; из $(12;\ 46)$ — в $(13;\ 46)$);
• $(10;\ 23)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(10;\ 24)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(11;\ 24)$ — в $(11;\ 48)$; из $(20;\ 24)$ — в $(40;\ 24)$; из $(10;\ 25)$ — в $(10;\ 50)$; из $(10;\ 48)$ — в $(11;\ 48)$);
• $(5;\ 24)$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $(10;\ 24)$. Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $(11;\ 24)$ — в $(11;\ 48)$; из $(20;\ 24)$ — в $(40;\ 24)$; из $(10;\ 25)$ — в $(10;\ 50)$; из $(10;\ 48)$ — в $(11;\ 48)$);
• $(5;\ 46)$ — Ваня выигрывает сразу: одним ходом он получает $(5;\ 92)$, а это уже не меньше 59.

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

Ответ: 23

Решение:

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

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

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

# данные из прилагаемого файла: 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

Решение.

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

Значит, кратчайшие расстояния считаются одним проходом по вершинам в порядке возрастания номера. Заведём массив d, положим d[1] = 0, остальные — «бесконечность», и для каждой вершины по очереди пробуем улучшить расстояния до её соседей.

edges = []
for line in open('23.txt'):
    a, b, w = line.split()
    edges.append((int(a), int(b), float(w)))

INF = float('inf')
d = [INF] * 101
d[1] = 0
for v in range(1, 101):
    if d[v] == INF:
        continue
    for a, b, w in edges:
        if a == v and d[v] + w < d[b]:
            d[b] = d[v] + w

print(int(d[100]))

Программа печатает 845. Задание просит целую часть длины, поэтому дробная часть отбрасывается.

Ответ: 845.

Цифры 14-ричной системы – это символы 0–9, A, B, C, D; чётные цифры – 0, 2, 4, 6, 8, A, C. Разбиваем файл на максимальные цепочки из допустимых символов; чем длиннее запись, тем больше число, поэтому ищем самую длинную подстроку, начинающуюся с ненулевой цифры и заканчивающуюся чётной цифрой.

Самая длинная цепочка допустимых символов расположена в начале файла и имеет длину 2600. Она начинается с нуля (значащие цифры начинаются со второго символа), а последняя чётная цифра стоит на позиции 2599. Значит запись числа содержит 2598 значащих цифр.

Ответ: 2598.

Решение:

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

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

Проверим пару строк вручную. Для $n=850004$ наименьший простой делитель $p=2$, значит $F=850004/2-2=425002-2=425000$ — делится на 5. Для $n=850025$ имеем $p=5$, $F=170005-5=170000$ — тоже делится на 5. А, например, 850001 в ответ не попало: у него $F$ на 5 не делится.

Программа печатает шесть строк:

Ответ: 850004 425000 850014 425005 850024 425010 850025 170000 850029 283340 850034 425015

Решение:

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

Почему жадность верна: если пропустить самую большую доступную коробку, цепочка не удлинится (её всегда можно поставить снаружи), а «потолок» для следующих коробок только опустится. Двигаясь сверху вниз, мы на каждом шаге оставляем максимально возможный запас, поэтому одновременно получаем и наибольшее количество коробок, и наибольшую возможную сторону самой маленькой из них — ею оказывается последняя взятая коробка.

f = open('26.txt')
n = int(f.readline())
a = sorted((int(x) for x in f), reverse=True)

cnt = 0
last = None
for x in a:
    if last is None or x <= last - 3:
        cnt += 1
        last = x
print(cnt, last)

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

2767 51

Ответ: 2767 51

Решение:

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

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

Файл A: сумма больших чисел равна $639036$; она даёт остаток $9$ при делении на 37, то есть уже не делится на 37 — уменьшать ничего не нужно, ответ $639036$.

Файл B: сумма больших чисел равна $664021240$ и делится на 37. Наименьшая ненулевая разность внутри пары, не кратная 37, равна $6692$, поэтому ответ $664021240 - 6692 = 664014548$.

Ответ: 639036 664014548