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

Отвечено 0 из 27

Задание №1

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

		Номер пункта
		1	2	3	4	5	6	7
Номер пункта	1			17		21
	2						25	19
	3	17				33
	4					14		28
	5	21		33	14		36
	6		25			36
	7		19		28

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта В в пункт Е и из пункта Д в пункт К. В ответе запишите целое число.

Правильный ответ

Пояснение

Решение:

Степени вершин схемы: А — 2, Б — 2, В — 2, Г — 4, Д — 2, Е — 2, К — 2.

Число заполненных клеток в строках таблицы: 1 — 2, 2 — 2, 3 — 2, 4 — 2, 5 — 4, 6 — 2, 7 — 2.

Степень 4 только у Г и только у пункта 5, поэтому Г = 5, а его соседи 1, 3, 4, 6 отвечают вершинам А, Б, В, Д.

На схеме А и Б соединены друг с другом (треугольник А—Б—Г), а В и Д — нет. В таблице среди пунктов 1, 3, 4, 6 дорога есть только между 1 и 3 (она равна 17). Значит, А и Б — это 1 и 3, а В и Д — это 4 и 6. Оставшиеся пункты 2 и 7 — это Е и К.

Дороги В—Е и Д—К — это как раз обе дороги, ведущие из пары {4, 6} в пару {2, 7}. В таблице их ровно две: 4—7 = 28 и 6—2 = 25. Какая из них В—Е, а какая Д—К, для суммы неважно.

Сумма: 28 + 25 = 53.

Ответ: 53

2
Задание №2
Миша заполнял таблицу истинности логической функции $F$

$\neg ( x \rightarrow w ) \lor ( y \rightarrow ( z \equiv w ) )$ ,

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

F

0 1 0 0

1 1 0

0 0 0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Правильный ответ
zwyx
Пояснение
Решение:

Дизъюнкция равна нулю только при нулевых слагаемых. Из $\neg(x \rightarrow w) = 0$ получаем $x \rightarrow w = 1$ , а из $y \rightarrow (z \equiv w) = 0$ — что $y=1$ и $z \ne w$ .

Подходящих наборов ровно три: $(w,x,y,z)$ равно $(0,0,1,1)$ , $(1,0,1,0)$ или $(1,1,1,0)$ .

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

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

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

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

from itertools import permutations, product def F(w, x, y, z): return not (not x or w) or (not y or (z == w)) rows = [t for t in product([0, 1], repeat=4) if not F(*t)] # наборы (w, x, y, z) с F = 0 frag = [[None, 0, 1, 0], [None, 1, 1, None], [0, 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

Ответ: zwyx
3
Задание №3
В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.
Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады июня 2021 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок, шт. занесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.

ID операции Дата ID магазина Артикул Тип операции Количество упаковок, шт. Цена руб./шт.

Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Заголовок таблицы имеет следующий вид.

Артикул Отдел Наименование товара Ед. изм. Количество в упаковке Поставщик

Таблица «Магазин» содержит информацию о местонахождении магазинов. Заголовок таблицы имеет следующий вид.

ID магазина Район Адрес

На рисунке приведена схема указанной базы данных.

Используя информацию из приведённой базы данных, определите на сколько увеличилось количество упаковок яиц диетических, имеющихся в наличии в магазинах Заречного района за период с 1 по 10 июня.
В ответе запишите только число.

52818_3.xlsx
Правильный ответ
966
Пояснение
Решение:

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

Шаг 1. В таблице «Магазин» отбираем магазины Заречного района и выписываем их ID магазина (их четыре).

Шаг 2. В таблице «Товар» находим строку «Яйцо диетическое» и запоминаем её артикул.

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

Шаг 4. Двумя формулами СУММЕСЛИМН считаем сумму столбца «Количество упаковок, шт.» отдельно по типу операции «Поступление» и по типу «Продажа»: 1420 и 454 упаковки. Увеличение: $1420 - 454 = 966$ упаковок.

Ответ: 966
4
Задание №4
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных
сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Правильный ответ
14
Пояснение
Решение:

Известно: Н — 1111, З — 110. Найдём свободные вершины двоичного дерева, то есть слова, которые можно добавить без нарушения условия Фано.

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

В ветви 1 свободна вершина 10 (2 знака).

В ветви 11: слово 110 занято буквой З; в ветви 111 слово 1111 занято буквой Н, свободна вершина 1110 (4 знака).

Получилось ровно три свободных места — 0, 10 и 1110 — как раз для трёх неизвестных букв А, К, Ч.

В слове КАЗАЧКА буква А встречается 3 раза, К — 2 раза, З — 1 раз, Ч — 1 раз. Самое короткое слово отдаём самой частой букве:

Буква Кодовое слово Длина Сколько раз Всего знаков
А 0 1 3 3
К 10 2 2 4
З 110 3 1 3
Ч 1110 4 1 4

Суммарно $3 + 4 + 3 + 4 = 14$ двоичных знаков.

Ответ: 14
5
Задание №5
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Из числа N вычитается остаток от деления N на 4.
2) Строится двоичная запись полученного результата.
3) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры построенной двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись является двоичной записью искомого числа R.
Укажите минимальное число R, большее 56, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Правильный ответ
66
Пояснение
Решение:

После первого шага получается число $M = N - (N \bmod 4)$ , кратное 4, поэтому его двоичная запись оканчивается двумя нулями. Любое кратное четырём число может получиться на этом шаге (достаточно взять $N = M$ ), так что дальше можно перебирать сразу значения M.

Разберёмся с двумя приписываемыми разрядами. Пусть в двоичной записи числа M ровно s единиц, тогда сумма её цифр равна s.

Первым приписывается разряд $s \bmod 2$ .

После этого сумма цифр становится равной $s + (s \bmod 2)$ — а это число всегда чётно, поэтому второй приписанный разряд всегда 0.

Итак, если единиц в записи M чётное число, справа приписывается 00, если нечётное — 10. Приписывание двух разрядов умножает число на 4, поэтому $R = 4M$ или $R = 4M + 2$ , причём M кратно 4, то есть R кратно 16 либо даёт при делении на 16 остаток 2.

Перебираем M, кратные четырём, и ищем первый результат, больший 56:

$M = 12 = 1100_2$ : единиц две, число чётное, приписываем 00, получаем $110000_2 = 48$ — не больше 56;

$M = 16 = 10000_2$ : единица одна, число нечётное, приписываем 10, получаем $1000010_2 = 66$ — больше 56.

Между 48 и 66 других результатов нет, потому что каждое следующее значение M кратно 4 и увеличивает R сразу на 16. Значит, минимальное $R \gt 56$ равно 66. Проверка программой:

res = set() for n in range(4, 1000): m = n - n % 4 s = bin(m)[2:] s += str(sum(map(int, s)) % 2) s += str(sum(map(int, s)) % 2) res.add(int(s, 2)) print(min(r for r in res if r > 56))

Программа печатает 66.

Ответ: 66
6
Задание №6
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки. Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:
Повтори 2 [Вперёд 8 Направо 90 Вперёд 18 Направо 90]
Поднять хвост
Вперёд 4 Направо 90 Вперёд 10 Налево 90
Опустить хвост
Повтори 2 [Вперёд 17 Направо 90 Вперёд 7 Направо 90]
Определите, сколько точек с целочисленными координатами будут находиться внутри объединения фигур, ограниченного заданными алгоритмом линиями, включая точки на линиях.
Правильный ответ
275
Пояснение
Решение:

Все повороты кратны $90^\circ$ , поэтому обе фигуры — прямоугольники со сторонами, параллельными осям. Достаточно найти их координаты.

Первый цикл: из $(0;0)$ вверх на 8 в $(0;8)$ , направо и вправо на 18 в $(18;8)$ , вниз на 8 в $(18;0)$ , влево на 18 обратно в $(0;0)$ . Это прямоугольник $[0;18] \times [0;8]$ .

Затем хвост поднят: вперёд 4 (вверх) в $(0;4)$ , направо и вперёд 10 в $(10;4)$ , налево — голова снова смотрит вверх. Второй цикл рисует прямоугольник $[10;17] \times [4;21]$ .

Нужны целые точки объединения, включая точки на линиях. В прямоугольнике целых точек $(x_2 - x_1 + 1)(y_2 - y_1 + 1)$ : в первом $19 \cdot 9 = 171$ , во втором $8 \cdot 18 = 144$ . Их пересечение — прямоугольник $[10;17] \times [4;8]$ , в нём $8 \cdot 5 = 40$ точек. По формуле включений-исключений получаем $171 + 144 - 40 = 275$ .

def pts(x1, x2, y1, y2): return (x2 - x1 + 1) * (y2 - y1 + 1) a = pts(0, 18, 0, 8) # 171 b = pts(10, 17, 4, 21) # 144 c = pts(10, 17, 4, 8) # 40 — пересечение print(a + b - c) # 275

Ответ: 275
7
Задание №7
Для хранения растрового изображения размером 360 х 512 пикселей отведено не более 240 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в палитре изображения?
Правильный ответ
1024
Пояснение
Решение:
Пусть цвет одного пикселя кодируется $i$ битами. Всего в изображении $360 \cdot 512 = 184320$ пикселей, значит файл (без заголовка) занимает $184320 \cdot i$ бит.
Переведём отведённую память в биты: $240 \cdot 1024 \cdot 8 = 1966080$ бит.
Файл должен поместиться в отведённую память: $184320 \cdot i \le 1966080$ , откуда $i \le \frac{1966080}{184320} \approx 10{,}67$ .
Число бит на пиксель — целое, поэтому наибольшее подходящее значение $i = 10$ .
При $i$ битах на пиксель можно закодировать $2^i$ различных цветов, поэтому в палитре может быть $2^{10} = 1024$ цветов.
W, H = 360, 512 V = 240 * 1024 * 8 # отведённая память в битах i = V // (W * H) # максимальное целое число бит на пиксель print(i, 2 ** i) # 10 1024
Ответ: 1024
8
Задание №8
Все пятибуквевнные слова, в составе которых могут быть только русские буквы М, А, С, Л, О, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
1. ААААА
2. ААААЛ
3. ААААМ
4. ААААО
5. ААААС
6. АААЛА
...

Под каким номером в списке идёт первое слово, которое содержит не более одной буквы А, ровно две буквы М, не содержит ни одной буквы Л?
Правильный ответ
319
Пояснение
Решение:

Буквы в алфавитном порядке: А, Л, М, О, С. Наименьшее подходящее слово строим жадно, слева направо ставя минимальную допустимую букву.

Условия: букв А не более одной, букв М ровно две, буквы Л нет совсем.

1-я буква — А (одна А разрешена);

2-я и 3-я — М: вторую А ставить нельзя, буква Л запрещена, значит следующая по алфавиту доступная буква — М, и обе нужные М выгодно поставить левее;

4-я и 5-я — О: А исчерпана, Л запрещена, М уже ровно две, поэтому минимальная доступная буква — О.

Получилось слово АММОО. Заменим буквы цифрами пятеричной системы (А=0, Л=1, М=2, О=3, С=4): АММОО → $02233_5$ , его значение $2 \cdot 5^3 + 2 \cdot 5^2 + 3 \cdot 5 + 3 = 250 + 50 + 15 + 3 = 318.$ Номер слова равен $318 + 1 = 319$ .

from itertools import product for n, w in enumerate(product('АЛМОС', repeat=5), 1): s = ''.join(w) if s.count('А') <= 1 and s.count('М') == 2 and 'Л' not in s: print(n, s) break

Ответ: 319
9
Задание №9
Откройте файл электронной таблицы, содержащей вещественные числа - результаты ежечасного измерения концентрации примесей в воде очистных установок на протяжении трёх месяцев. Найдите разность между минимальным значением концентрации примесей на протяжении трёх месяцев и средним арифметическим значением концентрации примесей в этот период времени. В ответе запишите только целую часть получившегося числа.

44053_9.xlsx

44053_9.xls

44053_9.ods

44053_9.csv
Правильный ответ
10
Пояснение
Решение:

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

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

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

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

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

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

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

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

Ответ: 10
10
Задание №10
В терминологии сетей ТСР/IP маской сети называется двоичное число, определяющее, какая часть IР-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IР-адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда — нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IР-адресу узла и маске.

Например, если IР-адрес узла равен 125.44.101.252, а маска равна 255.255.255.192, то адрес сети равен 125.44.101.192.

Для узла с IР-адресом 244.55.138.100 адрес сети равен 244.55.138.96. Чему равно наименьшее возможное значение последнего (самого правого) байта маски? Ответ запишите в виде десятичного числа.
Правильный ответ
224
Пояснение
Решение:

IP-адрес 244.55.138.100, адрес сети 244.55.138.96. Первые три байта совпадают, поэтому в маске они равны 255, а вопрос только о четвёртом байте.

Запишем последний байт: $100 = 01100100_2$ , в адресе сети $96 = 01100000_2$ . Маска должна сохранить разряды со значениями 64 и 32 и обнулить разряд со значением 4. Перебираем префиксные маски от меньших к большим:

$128 = 10000000_2$ : $100 \wedge 128 = 0 \ne 96$ — не подходит;

$192 = 11000000_2$ : $100 \wedge 192 = 01000000_2 = 64 \ne 96$ — не подходит;

$224 = 11100000_2$ : $100 \wedge 224 = 01100000_2 = 96$ — подходит.

Наименьшее возможное значение последнего байта маски равно 224 (маска 255.255.255.224). Для полноты: подходят также 240 и 248, а уже $252$ даёт $100 \wedge 252 = 100\ne 96$ .

for m in [0, 128, 192, 224, 240, 248, 252, 254, 255]: if 100 & m == 96: print(m) # 224 break

Ответ: 224
11
Задание №11
При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байта на один объект.
Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число — количество байт.
Правильный ответ
600
Пояснение
Решение:
Идентификатор набирается из 8-символьного набора А, В, C, D, Е, F, G, H, значит мощность алфавита составляет $8$ символов. Алфавит содержит ровно $2^{3} = 8$ символов, поэтому на один символ достаточно $i = 3$ бита.
Один идентификатор из 15 символов занимает $15 \cdot 3 = 45$ бит. Число байт должно быть целым и минимальным: $45 = 8 \cdot 5 + 5$ , поэтому под него отводится 6 байт.
Кроме идентификатора на один объект отводится ещё 24 байта дополнительных сведений, поэтому одна запись занимает $6 + 24 = 30$ байт.
Для 20 объектов потребуется $20 \cdot 30 = 600$ байт.
import math N = 8 # мощность алфавита i = math.ceil(math.log2(N)) # бит на один символ b = math.ceil(15 * i / 8) # байт на идентификатор print(20 * (b + 24)) # ответ в байтах
Ответ: 600

Буква	Кодовое слово	Длина	Сколько раз	Всего знаков
А	0	1	3	3
К	10	2	2	4
З	110	3	1	3
Ч	1110	4	1	4

Задание №12

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a₀, a₁, …, a_n–1}), включая специальный пустой символ a₀.
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q = {q₀, q₁, …, q_n–1}. В начальный момент времени головка находится в начальном состоянии q₀.
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может изменить символ в текущей ячейке и переместиться в соседнюю ячейку слева или справа от неё. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.

Программа работы исполнителя МТ задаётся в табличном виде.

	a₀	a₁	…	a_n–1
q₀	команда	команда	…	команда
q₁	команда	команда	…	команда
…	…	…	…	…
q_n–1	команда	команда	…	команда

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из трёх символов «L», «R», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.

Например, команда 0, L, q₃ выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q₃.

Приведём пример выполнения программы, заданной таблично.
На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «λ». В начальный момент времени головка находится на неизвестном расстоянии справа от самого правого символа «Z».

Программа

	λ	Z
q₀	λ, L, q₀	X, L, q₁
q₁	λ, L, q₁	X, L, q₂
q₂	λ, S, q₂	X, L, q₂

заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности символов «X».

Возможное начальное состояние исполнителя:

…	λ	λ	Z	Z	Z	Z	λ	λ	…
							▲ q₀

Конечное состояние исполнителя после завершения выполнения программы:

…	λ	λ	X	X	X	X	λ	λ	…
		▲ q₂

Выполните задание.
На ленте в соседних ячейках записано двоичное представление числа 1023 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.
Программа работы исполнителя:

	λ	0	1
q₀	λ, L, q₁
q₁	1, L, q₂	1, S, q₂	0, L, q₁
q₂	λ, S, q₂

Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.

Правильный ответ

1024

Пояснение

Число 1023 в двоичной системе – 1111111111₂ (десять единиц). Головка стоит в пустой ячейке справа от них в состоянии q₀.

Команда (q₀, λ) = «λ, L, q₁» переводит головку на самую правую единицу в состояние q₁.

Команда (q₁, 1) = «0, L, q₁» заменяет единицу нулём и сдвигает головку влево. Она выполняется десять раз подряд, и все единицы превращаются в нули.

Головка попадает на пустую ячейку слева. Команда (q₁, λ) = «1, L, q₂» записывает в неё единицу. Затем команда (q₂, λ) = «λ, S, q₂» завершает работу.

На ленте осталось 10000000000₂ = 1024. Программа прибавляет к двоичному числу единицу.

Ответ: 1024.

Задание №13

Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
А) Прибавить 2
В) Прибавить 10
Первая команда увеличивает число на экране на 2, вторая увеличивает это число на 10. Программа для исполнителя - это последовательность команд. Сколько существует программ, которые число 5 преобразуют в число 71?

Правильный ответ

5411

Пояснение

Решение:

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

$2 n + 10 k = 66.$

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

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

$k$ — команд В	$n$ — команд А	Количество программ $C_{n+k}^{\,k}$
0	33	$C_{33}^{0} = 1$
1	28	$C_{29}^{1} = 29$
2	23	$C_{25}^{2} = 300$
3	18	$C_{21}^{3} = 1330$
4	13	$C_{17}^{4} = 2380$
5	8	$C_{13}^{5} = 1287$
6	3	$C_{9}^{6} = 84$

Складываем: $1 + 29 + 300 + 1330 + 2380 + 1287 + 84 = 5411$ .

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

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 + 10):
        s += f(z, y)
    return s

print(f(5, 71))

Ответ: 5411

14
Задание №14
Значение арифметического выражения
$3^{2021} + 5 \cdot 3^{2000} + 3^{501} + 5 \cdot 3^{500} + 1$
записали в системе счисления с основанием 9. Сколько значащих нулей содержится в этой записи?
Правильный ответ
1007
Пояснение
Решение:
Основание системы счисления 9, а $9 = 3^{2}$ , поэтому удобно выразить всё через степени девятки:
$3^{2021} = 3\cdot 3^{2020} = 3\cdot 9^{1010}$ ;
$5\cdot 3^{2000} = 5\cdot 9^{1000}$ ;
$3^{501} + 5\cdot 3^{500} = 3\cdot 3^{500} + 5\cdot 3^{500} = 8\cdot 3^{500} = 8\cdot 9^{250}$ ;
$1 = 1\cdot 9^{0}$ .
Получаем $N = 3\cdot 9^{1010} + 5\cdot 9^{1000} + 8\cdot 9^{250} + 1$ . Все коэффициенты (3, 5, 8, 1) — допустимые девятеричные цифры и стоят в разных разрядах, значит переносов нет, и это и есть готовая запись числа в девятеричной системе.
Старший разряд — 1010-й, поэтому всего в записи $1011$ цифр, из которых ненулевых ровно четыре. Значащих нулей: $1011 - 4 = 1007$ .
def to_base(n, b): s = '' while n: s = str(n % b) + s n //= b return s n = 3**2021 + 5 * 3**2000 + 3**501 + 5 * 3**500 + 1 print(to_base(n, 9).count('0')) # 1007
Ответ: 1007
15
Задание №15
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула
$\neg ДЕЛ ( x , А ) \rightarrow ( ДЕЛ ( x , 54 ) \rightarrow \neg ДЕЛ ( 162 , x ) )$
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Правильный ответ
54
Пояснение
Решение:

Раскроем импликации: формула равносильна

$\text{ДЕЛ}(x, A) \lor \neg\text{ДЕЛ}(x, 54) \lor \neg\text{ДЕЛ}(162, x)$ .

Нарушить её могут только те $x$ , которые кратны 54 и при этом являются делителями числа 162. Делители $162 = 2 \cdot 3^4$ : 1, 2, 3, 6, 9, 18, 27, 54, 81, 162; кратны 54 среди них лишь $54$ и $162$ .

Для обоих должно быть истинно $\text{ДЕЛ}(x, A)$ , то есть $A$ делит и 54, и 162. Наибольшее такое $A$ — это $\text{НОД}(54, 162) = 54$ .

Ответ: 54
16
Задание №16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n — чётно;
F(n) = 2 × F(n − 2), если n > 1 и при этом n — нечётно.
Чему равно значение функции F(26)?
Правильный ответ
4122
Пояснение
Решение:
Число 26 чётное, поэтому $F(26) = 26 + F(25)$ . Осталось найти $F(25)$ .
Для нечётных $n \gt 1$ правило $F(n) = 2 \cdot F(n-2)$ уменьшает аргумент на 2, оставляя его нечётным, поэтому цепочка идёт только по нечётным числам: $F(25) = 2F(23) = 4F(21) = \dots = 2^{12} \cdot F(1)$ (от 25 до 1 ровно 12 шагов). Значит $F(25) = 2^{12} = 4096$ .
Итого $F(26) = 26 + 4096 = 4122$ .
from functools import lru_cache @lru_cache(None) def F(n): if n == 1: return 1 if n % 2 == 0: return n + F(n - 1) return 2 * F(n - 2) print(F(26)) # 4122
Ответ: 4122
17
Задание №17
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от -10000 до 10000 включительно. Определите и запишите в ответе сначала количество пар элементов последовательности, в которых оба числа оканчиваются на нечётные цифры, различные для элементов в паре, затем минимальное из произведений модулей элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

44118_17.txt
Правильный ответ
1020 17197
Пояснение
Решение:
Считаем файл в список целых чисел и просмотрим все пары соседних элементов $(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
18
Задание №18
Задание выполняется с использованием прилагаемых файлов.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных

1_18.ods

1_18.xls

1_18.xlsx
Правильный ответ
2400 852
Пояснение
Из файла читаем таблицу 20 × 20 значений монет и границы ячеек: утолщённые (thick) линии – внутренние стены, рамка таблицы (medium) – внешние стены.
Динамическим программированием по клеткам считаем максимальную и минимальную сумму пути из левой верхней клетки. Конечными являются клетки, у которых справа и снизу стена: (18; 16), (20; 12), (20; 19) и (20; 20). Пары (максимум; минимум) для них – (2323; 1371), (2090; 852), (2400; 1432), (2056; 1711).
Максимальная итоговая сумма 2400, минимальная 852.
Ответ: 2400 852.
19
Задание №19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда произведение количеств камней в кучах становится не менее 144. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что произведение количеств камней в кучах будет 144 или больше.

В начальный момент в первой куче был один камень, во второй куче — S камней; $1 \leq S \leq 142 .$

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Правильный ответ
36
Пояснение
Решение:

Позицию обозначаем (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
20
Задание №20
Условие игры

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в одну из куч (по своему выбору) два камня
– увеличить количество камней в куче в три раза.
Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (12, 7), (30, 7), (10, 9), (10, 21). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 136. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 136 или больше камней.
В начальный момент в первой куче было два камня, во второй куче — S камней; $1 \leq S \leq 132 .$
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от дальнейшей игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Для игры, описанной выше, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Правильный ответ
42 43
Пояснение
Решение:

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

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

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

S = 42. Позиция (2, 42): $2+3\cdot 42 = 128 \lt 136$ — сам Петя не выигрывает. Он добавляет два камня во вторую кучу: (2, 44), где $2+3\cdot 44 = 134$ . Любой ответ Вани проигрышен: (4, 44) даёт $4+132=136$ , (2, 46) даёт $2+138=140$ , (6, 44) даёт $6+132=138$ , (2, 132) — тем более; во всех случаях Петя вторым ходом утраивает бо́льшую кучу и набирает не менее 136 камней.

S = 43. Позиция (2, 43): $2+129=131 \lt 136$ . Теперь ход «+2 во вторую кучу» не годится: в позиции (2, 45) уже $2+135=137 \ge 136$ , и Ваня выигрывает сразу. Зато Петя может утроить первую кучу: (6, 43), где $6+3\cdot 43 = 135$ — проигрышная позиция. Ответы Вани: (8, 43) даёт $8+129=137$ , (6, 45) даёт $6+135=141$ , (18, 43) даёт $18+129=147$ , (6, 129) — тем более; всюду Петя заканчивает игру вторым ходом.

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

N = 136 A = 2 # камней в первой куче def moves(p): x, y = p return [(x + 2, y), (x, y + 2), (3 * x, y), (x, 3 * y)] def win1(p): # ходящий заканчивает игру своим ходом return any(x + y >= N for x, y in moves(p)) def lose1(p): # любой ход ходящего даёт победу сопернику return not win1(p) and all(win1(q) for q in moves(p)) def win2(p): # первым ходом не выигрывает, вторым — выигрывает return not win1(p) and any(lose1(q) for q in moves(p)) print([s for s in range(1, 133) if win2((A, s))][:2]) # [42, 43]

Ответ: 42 43
21
Задание №21
Условие игры

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней либо увеличить количество камней в куче в четыре раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 205. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, состоящую из 205 или более камней. В начальный момент в куче было S камней; $1 \leq S \leq 204 .$ Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Для игры, описанной выше, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
Правильный ответ
45
Пояснение
Решение:

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

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

$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 = 205 def moves(s): return [s + 1, s + 5, 4 * s] def over(s): return s >= N def win1(p): # ходящий выигрывает своим первым ходом return any(over(q) for q in moves(p)) def lose1(p): # соперник выигрывает своим первым ходом return not win1(p) and all(win1(q) for q in moves(p)) def win2(p): # ходящий выигрывает своим вторым ходом return not win1(p) and any(lose1(q) for q in moves(p)) def lose2(p): # соперник выигрывает первым или вторым ходом return not win1(p) and all(win1(q) or win2(q) for q in moves(p)) for s in range(1, 205): if lose2(s) and not lose1(s): print(s) break

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

$46$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $51$ . Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $52$ — в $208$ ; из $56$ — в $224$ ; из $204$ — в $205$ );

$50$ — здесь Ваня сразу выиграть не может, поэтому он отвечает ходом в $51$ . Эта позиция проигрышная для Пети: куда бы он ни пошёл, Ваня своим вторым ходом доводит игру до конца (из $52$ — в $208$ ; из $56$ — в $224$ ; из $204$ — в $205$ );

$180$ — Ваня выигрывает сразу: одним ходом он получает $720$ , а это уже не меньше 205.

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

Ответ: 45

Задание №22

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. В файле информация о процессах представлена в виде таблицы. В первой колонке таблицы указан идентификатор процесса (ID), во второй колонке таблицы — время его выполнения в миллисекундах, в третьей колонке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Время выполнения одного из процессов неизвестно и для данного процесса в соответствующей колонке обозначено как t.
Типовой пример организации данных в файле:

ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) А
1	4	0
2	3	0
3	t	1; 2
4	7	3

Определите максимальное возможное целочисленное t (время выполнения процесса), при котором выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, завершилось не более чем за 19 мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

44239_22.xlsx

44239_22.xls

44239_22.ods

Правильный ответ

Пояснение

Решение:

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

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

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

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

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

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

def total(t):
    finish = {}
    for i in sorted(data):
        dur, deps = data[i]
        if dur is None:
            dur = t
        finish[i] = max([finish[d] for d in deps], default=0) + dur
    return max(finish.values())

print(max(t for t in range(1, 1000) if total(t) <= 19))

Ответ: 9

23
Задание №23
В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

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

Числа в строке файла разделены ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле
```
100   12    1.0
6     7     7.0
6     1     1.0
1     7     5.5
7     100   2.0
4     100   8.0
1     100   12.0
1     4     2.5
```
Для приведённого примера верным ответом будет 7.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

repet-2027-inf23-24.txt
Правильный ответ
2460
Пояснение
Решение.

В файле 1097 рёбер. Рёбра ведут только из вершины с меньшим номером в вершину с большим, поэтому граф ациклический, а порядок 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]))

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

Ответ: 2460.
24
Задание №24
Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, символ Z встречается не более одного раза.
Для выполнения этого задания следует написать программу.

44250_24.txt
Правильный ответ
43
Пояснение
Решение:

Нужен самый длинный участок, в котором символ Z встречается не более одного раза. Разрежем файл символами Z на куски, состоящие только из X и Y: s.split('Z'). Тогда искомый участок — это либо один такой кусок (ноль символов Z), либо два соседних куска вместе с разделяющим их символом Z, то есть len(parts[i]) + 1 + len(parts[i+1]).

Остаётся перебрать все пары соседних кусков и взять максимум.

s = open('44250_24.txt').read().strip() parts = s.split('Z') ans = max(len(p) for p in parts) for i in range(len(parts) - 1): ans = max(ans, len(parts[i]) + 1 + len(parts[i + 1])) print(ans)

Можно и одним проходом «методом двух указателей»: двигаем правую границу окна, а при появлении в окне второго Z сдвигаем левую границу за первый Z.

s = open('44250_24.txt').read().strip() mx = 0 left = 0 zpos = [] for i, c in enumerate(s): if c == 'Z': zpos.append(i) if len(zpos) > 1: left = zpos.pop(0) + 1 if i - left + 1 > mx: mx = i - left + 1 print(mx)

Обе программы выводят 43.

Ответ: 43
25
Задание №25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну произвольную цифру;
- символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 9*?001?1, делящиеся на 12007 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце - соответствующие результаты деления этих чисел на 12007. Количество строк в таблице для ответа избыточно.
Правильный ответ
9098100131 757733 9201000121 766303 9303900111 774873 9406800101 783443 9681400191 806313 9784300181 814883 9887200171 823453 9990100161 832023
Пояснение
Решение:

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

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

from fnmatch import fnmatch for k in range(1, 10 ** 10 // 12007 + 1): n = 12007 * k if fnmatch(str(n), '9*?001?1'): print(n, k)

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

Число Частное от деления на 12007
9098100131 757733
9201000121 766303
9303900111 774873
9406800101 783443
9681400191 806313
9784300181 814883
9887200171 823453
9990100161 832023

Ответ: 9098100131 757733 9201000121 766303 9303900111 774873 9406800101 783443 9681400191 806313 9784300181 814883 9887200171 823453 9990100161 832023
26
Задание №26
Илье необходимо перенести файлы с одного компьютера на другой при помощи внешнего жесткого диска.
Объём диска может быть меньше, чем требуется для переноса всех файлов за один раз. Свободный объём на диске и размеры файлов известны.
По заданной информации об объёме файлов на компьютере и свободном объёме на диске определите максимальное число файлов, которые могут быть перенесены за один раз на внешний жёсткий диск, а также максимальный размер файла, записанного на этот диск, при условии, что перенесено наибольшее возможное число файлов.
Входные данные:
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 100 000) и N — количество файлов, которые надо перенести (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов указанных файлов (все числа натуральные не превышающие 100), каждое в отдельной строке.
Выходные данные:
Запишите в ответе два числа: сначала наибольшее число файлов, которые могут быть перенесены на внешний жёсткий диск за один раз, затем максимальный размер перенесённого файла, при условии, что перенесено наибольшее возможное число файлов. Если вариантов переноса несколько, выберите тот, при котором будет перенесён наибольший файл.
Пример входного файла:
100 4
80
30
50
40.
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов: 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера: 2 50.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

44345_26.txt
Правильный ответ
3105 75
Пояснение
Решение:

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

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

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

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

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)

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

3105 75

Ответ: 3105 75
27
Задание №27
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 37 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные:
Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар N $\left(1 \leq N \leq 100000\right) .$ Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла В.

Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1

Для указанных входных данных значением искомой длины должно быть число 33.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

44353_27_A.txt

44353_27_B.txt
Правильный ответ
639036 664014548
Пояснение
Решение:
Сначала забудем про делимость и возьмём из каждой пары большее число. Полученная сумма $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

Число	Частное от деления на 12007
9098100131	757733
9201000121	766303
9303900111	774873
9406800101	783443
9681400191	806313
9784300181	814883
9887200171	823453
9990100161	832023