Вариант 2026 года. С 2027 года структура экзамена изменилась: нумерация заданий и баллы даны по КИМ 2026 года, поэтому итог считается приблизительно.

Реальный вариант ЕГЭ 2026 №1

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

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

Номер пункта 1 2 3 4 5 6 7

1 4 5

2 4 8 9 6

3 10 7

4 11

5 8 11 12

6 9 10 12 13

7 5 6 7 13

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта В в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.
Правильный ответ
9
Пояснение
В графе степени вершин равны: А – 1, Б – 3, В – 4, Г – 2, Д – 4, Е – 4, К – 2.
В таблице числа заполненных клеток в строках равны: 1 – 2, 2 – 4, 3 – 2, 4 – 1, 5 – 3, 6 – 4, 7 – 4.
Единственная вершина степени 1 – это А, значит А = 4. Единственная вершина степени 3 – это Б, значит Б = 5. Проверка: клетка (4; 5) заполнена, дорога А–Б есть.
Соседи пункта 5 в таблице: 2, 4, 6. Пункт 4 – это А, значит В и Д (соседи Б в графе) – это 2 и 6. Тогда третья вершина степени 4, то есть Е, соответствует пункту 7.
Клетка (2; 6) таблицы содержит число 9. При любом из двух возможных сопоставлений (В = 2, Д = 6 или В = 6, Д = 2) дорога В–Д – это дорога между пунктами 2 и 6.
Ответ: 9.
2
Задание №2
#949481 баллПостроение таблицы истинности
Миша заполнял таблицу истинности логической функции F
$( ( z \rightarrow x ) \rightarrow ( x \equiv y ) ) \lor \neg w ,$
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

F

0 1 0 0

0 0 0

1 1 0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция задана выражением ¬x ∨ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

F

0 1 0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Правильный ответ
yxwz
Пояснение
Функция $F = ( ( z \rightarrow x ) \rightarrow ( x \equiv y ) ) \lor \neg w$ равна 0 только тогда, когда $w = 1$ и $( z \rightarrow x ) \rightarrow ( x \equiv y )$ равно 0, то есть когда $z \rightarrow x = 1$ и $x \ne y$ .
Значит, во всех строках фрагмента $w = 1$ . Во второй строке первый столбец равен 0, поэтому первый столбец – не w. В третьей строке второй и третий столбцы равны 1, а $x \ne y$ , поэтому среди второго и третьего столбцов ровно один из них – w или z.
Полный перебор 24 вариантов расстановки w, x, y, z по столбцам оставляет единственный вариант yxwz: строки фрагмента получаются равными (y, x, w, z) = (1, 0, 1, 0), (0, 1, 1, 0) и (0, 1, 1, 1). Все три строки различны, и в каждой F = 0.
Ответ: yxwz.
3
Задание №3
#949491 баллБазы данных
В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.
Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады июня 2025 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок внесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.

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

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

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

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

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

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

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

1_3.ods
Правильный ответ
445
Пояснение
В таблице «Товар» крахмалу картофельному соответствует артикул 42; единица измерения – килограмм, количество в упаковке – 0,5.
В таблице «Магазин» к Октябрьскому району относятся магазины M1, M5, M6, M10 и M15.
В таблице «Движение товаров» оставляем строки с артикулом 42, типом операции «Поступление», магазином из Октябрьского района и датой с 1 по 8 июня. Таких строк пять: 180, 180, 180, 180 и 170 упаковок, всего 890 упаковок.
Общий вес: 890 × 0,5 = 445 кг.
Ответ: 445.
4
Задание №4
#949501 баллПрефиксные коды, условие Фано
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: A, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Буква Кодовое слово Буква Кодовое слово

A 00 F 1001

B S 1100

C 010 X 1010

D 011 Y 1101

E 1011 Z 111

Укажите кратчайшее кодовое слово для буквы B, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Правильный ответ
1000
Пояснение
Заняты коды 00, 010, 011, 1001, 1010, 1011, 1100, 1101, 111.
Слова длины 1: 0 – начало 00; 1 – начало 111. Не подходят.
Слова длины 2: 00 занято; 01 – начало 010; 10 – начало 1001; 11 – начало 111. Не подходят.
Слова длины 3: 000 и 001 начинаются с кода 00; 010 и 011 заняты; 100 – начало 1001; 101 – начало 1010; 110 – начало 1100; 111 занято. Не подходят.
Слова длины 4, начинающиеся с 0, невозможны: любое из них начинается с 00, 010 или 011. Наименьшее подходящее слово длины 4 – 1000: ни одно из имеющихся кодовых слов не является его началом, и оно само не является началом ни одного из них.
Ответ: 1000.
5
Задание №5
#949511 баллАнализ простейших алгоритмов
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 6₁₀ = 110₂ результатом является число 1000₂ = 8₁₀, а для исходного числа 4₁₀ = 100₂ это число 1101₂ = 13₁₀.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, не превышающее 19. В ответе запишите это число в десятичной системе счисления.
Правильный ответ
12
Пояснение
Если двоичная запись N состоит из k разрядов, то запись R состоит из k + 1 разряда и начинается с 1. При k = 5 получаем R ≥ 10000₂ = 32 > 19, поэтому N < 16.
Перебираем N от 15 вниз:
N = 15 = 1111₂, сумма цифр 4 чётная: 11110 → 10110₂ = 22;
N = 14 = 1110₂, сумма 3 нечётная: 11101 → 11101₂ = 29;
N = 13 = 1101₂, сумма 3 нечётная: 11011 → 11011₂ = 27;
N = 12 = 1100₂, сумма 2 чётная: 11000 → 10000₂ = 16 ≤ 19.
Ответ: 12.
6
Задание №6
#949521 баллАнализ алгоритмов для исполнителя
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз (где k – целое число).
Черепахе был дан для исполнения следующий алгоритм:
Направо 45
Повтори 3 [Направо 45 Вперёд 10 Направо 45]
Направо 315 Вперёд 10 Направо 90
Вперёд 20 Направо 90
Повтори 2 [Вперёд 10 Направо 90].
Определите, сколько точек с целочисленными координатами находятся внутри области, которая ограничена линией, заданной алгоритмом. Точки на линии учитывать не следует.
Правильный ответ
261
Пояснение
Черепаха проходит по вершинам (0; 0), (10; 0), (10; −10), (−10; −10), (−10; 10), (0; 10) и возвращается в (0; 0).
Полученная фигура – квадрат со стороной 20 с вырезанным угловым квадратом 10 × 10 (правая верхняя четверть).
Площадь фигуры: S = 400 − 100 = 300. Число целых точек на границе: 10 + 10 + 20 + 20 + 10 + 10 = 80.
По формуле Пика S = I + B/2 − 1, откуда I = 300 − 40 + 1 = 261.
Ответ: 261.
7
Задание №7
#949531 баллКодирование аудио и видео
Лена записывает голосовое сообщение для своей подруги. Перед отправкой сообщение оцифровывается в формате стерео с частотой дискретизации 28 000 Гц и глубиной кодирования 8 бит. Определите наименьшее количество Кбайт, необходимое для сохранения сообщения в памяти (без учёта заголовка), если его длительность – 2 минуты 20 секунд. В ответе укажите только число.
Правильный ответ
7657
Пояснение
Длительность сообщения: 2 мин 20 с = 140 с.
Объём в битах: 28 000 × 8 × 2 × 140 = 62 720 000 бит (множитель 2 – два канала стерео).
В байтах: 62 720 000 / 8 = 7 840 000 байт.
В Кбайтах: 7 840 000 / 1024 = 7656,25. Наименьшее целое количество Кбайт, которого хватит, – 7657.
Ответ: 7657.
8
Задание №8
#949541 баллКомбинаторика
Все шестибуквенные слова, составленные из букв А, П, Р, Е, Л, Ь, записаны в алфавитном порядке и пронумерованы.
Вот начало списка:
1. АААААА
2. АААААЕ
3. АААААЛ
4. АААААП
5. АААААР
6. АААААЬ
……
Определите, под каким номером в этом списке стоит первое слово с нечётным номером, которое не начинается с букв А или Л и при этом содержит в своей записи не менее двух букв П.
Примечание. Слово – последовательность идущих подряд букв, не обязательно осмысленная.
Правильный ответ
7903
Пояснение
Алфавитный порядок букв: А, Е, Л, П, Р, Ь. Присвоим им цифры А = 0, Е = 1, Л = 2, П = 3, Р = 4, Ь = 5. Тогда слово – это шестизначное число в шестеричной системе, а его номер в списке равен значению этого числа плюс 1.
Слова, начинающиеся с А, занимают номера с 1 по 6⁵ = 7776. Значит, искомое слово начинается с буквы Е или позже, то есть его номер больше 7776.
Номер нечётный, поэтому значение числа чётное, а последняя цифра чётная: последняя буква – А, Л или Р.
Перебор слов, начиная с номера 7777, даёт первое подходящее слово ЕААППА: его значение 7902 = 1 · 6⁵ + 3 · 6² + 3 · 6, номер 7903. Слово не начинается с А или Л и содержит две буквы П.
Ответ: 7903.
9
Задание №9
#949551 баллОбработка числовой информации
Откройте файл электронной таблицы, содержащей в каждой строке четыре натуральных числа. Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия:
– наибольшее из четырёх чисел меньше суммы трёх других;
– четыре числа нельзя разбить на две пары чисел с равными суммами.
В ответе запишите только число.

1_9.ods
Правильный ответ
2354
Пояснение
Для каждой строки с числами a, b, c, d проверяем два условия.
Первое: наибольшее из четырёх чисел меньше суммы трёх остальных, то есть max < (a + b + c + d) − max.
Второе: четыре числа нельзя разбить на две пары с равными суммами. Разбиений всего три, поэтому должны быть ложны все три равенства a + b = c + d, a + c = b + d, a + d = b + c.
В файле 3200 строк, обоим условиям удовлетворяют 2354 строки.
Ответ: 2354.
10
Задание №10
#949561 баллПоиск слова в тексте
C помощью текстового редактора определите, сколько раз встречается сочетание букв «то» или «То» только в составе других слов, включая сложные слова, соединённые дефисом, но не как отдельное слово, в тексте глав I и III третьей части тома 2 романа Л.Н. Толстого «Война и мир». В ответе укажите только число.

1_10.odt
Правильный ответ
115
Пояснение
Открываем файл и выделяем текст глав I и III третьей части тома 2.
Поиск сочетания «то» с учётом регистра (варианты «то» и «То») даёт 127 вхождений.
Поиск слова «то» целиком даёт 12 вхождений. Слова с дефисом (эти-то, где-то, что-то, чего-то, кого-то, несимметрично-растопыренными) считаются сложными словами, поэтому вхождения в них остаются.
127 − 12 = 115.
Ответ: 115.
11
Задание №11
#949571 баллКоличество информации
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 257 символов и содержащий только цифры семнадцатеричной системы счисления и символы из 4080-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Определите объём памяти (в Мбайт), необходимый для хранения 8 388 608 идентификаторов. В ответе запишите только целое число – количество Мбайт.
Правильный ответ
3344
Пояснение
В семнадцатеричной системе счисления 17 цифр, к ним добавляются 4080 специальных символов: всего 17 + 4080 = 4097 символов.
Так как 2¹² = 4096 < 4097, на один символ нужно 13 бит.
Один идентификатор: 257 × 13 = 3341 бит. Минимальное целое число байт: 3341 / 8 = 417,625, то есть 418 байт.
Всего: 8 388 608 × 418 = 2²³ × 418 байт = 2³ × 418 Мбайт = 3344 Мбайт.
Ответ: 3344.

Буква	Кодовое слово	Буква	Кодовое слово
A	00	F	1001
B		S	1100
C	010	X	1010
D	011	Y	1101
E	1011	Z	111

Задание №12

#949581 баллАнализ строковых алгоритмов

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов 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
Задание №13
#949591 баллМаски подсети
В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске.
Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы. Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств.
Сеть задана IP-адресом одного из входящих в неё узлов 68.203.243.87 и сетевой маской 255.255.224.0.
Найдите наибольший в данной сети IP-адрес, который может быть назначен компьютеру. В ответе укажите сумму числовых значений октетов найденного IP-адреса.
Например, если бы найденный адрес был равен 100.20.3.4, то в ответе следовало бы записать: 127.
Правильный ответ
780
Пояснение
Маска 255.255.224.0 в двоичном виде: 11111111.11111111.11100000.00000000, то есть под адрес узла отведено 13 младших разрядов.
Адрес сети: 243 & 224 = 224, поэтому сеть – 68.203.224.0.
Широковещательный адрес получается заменой всех нулей маски единицами: 68.203.255.255. Он не может быть назначен компьютеру.
Наибольший назначаемый адрес – 68.203.255.254.
Сумма октетов: 68 + 203 + 255 + 254 = 780.
Ответ: 780.
14
Задание №14
#949601 баллАнализ выражений
Определите количество цифр с чётным числовым значением в 36-ричной записи числа, заданного выражением:
$5 \cdot 1296^{2021} - 4 \cdot 216^{2022} + 3 \cdot 36^{2023} - 2 \cdot 6^{2024} - 2025$
Правильный ответ
1013
Пояснение
Заметим, что 1296 = 36², 216 = 6³, 36 = 6², поэтому все слагаемые удобно записывать в 36-ричной системе счисления.
Вычислив выражение и переведя его в систему счисления с основанием 36, получаем запись из 4043 цифр.
В этой записи 3027 цифр со значением 35, 1009 цифр 0 и по одной цифре со значениями 27, 15, 34, 33, 2, 32 и 4.
Чётные значения имеют 1009 нулей и четыре цифры 34, 2, 32, 4. Всего 1009 + 4 = 1013.
Ответ: 1013.
15
Задание №15
#949611 баллСложное логическое выражение
На числовой прямой даны два отрезка: B = [22; 40] и C = [32; 50]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
$\neg ( x \in A ) \rightarrow ( ( x \in B ) \equiv ( x \in C ) )$
истинно (т. е. принимает значение 1) при любом значении переменной х.
Правильный ответ
28
Пояснение
Импликация ложна только тогда, когда посылка истинна, а следствие ложно, то есть когда x ∉ A и (x ∈ B) не равносильно (x ∈ C).
Значит, отрезок A должен содержать все точки, которые принадлежат ровно одному из отрезков B и C, то есть симметрическую разность B и C.
B = [22; 40], C = [32; 50]. Симметрическая разность – это [22; 32) ∪ (40; 50].
Наименьший отрезок, содержащий это множество, – [22; 50]. Его длина 50 − 22 = 28.
Ответ: 28.
16
Задание №16
#949621 баллРекурсия
Алгоритм вычисления функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = 1, если n < 10;
F(n) = (n + 3) × F(n – 3), если n ≥ 10.
Чему равно значение выражения (F(247 563) / 519 – 477 × F(247 560)) / F(247 557)?
Правильный ответ
1431
Пояснение
По определению F(247 563) = (247 563 + 3) × F(247 560) = 247 566 × F(247 560).
Тогда числитель равен F(247 560) × (247 566 / 519 − 477). Так как 477 × 519 = 247 563, скобка равна (247 566 − 247 563) / 519 = 3 / 519 = 1 / 173.
Кроме того, F(247 560) = 247 563 × F(247 557).
Значит, всё выражение равно 247 563 / 173 = 1431.
Ответ: 1431.
17
Задание №17
#949631 баллОбработка числовой информации
В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от –100 000 до 100 000 включительно. Определите количество пар последовательности, в которых сумма элементов меньше минимального положительного элемента последовательности, кратного 123. Гарантируется, что такой элемент в последовательности есть. В ответе запишите количество найденных пар, затем абсолютное значение максимальной из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

1_17.txt
Правильный ответ
5001 962
Пояснение
Сначала находим минимальный положительный элемент последовательности, кратный 123. Он равен 984.
Затем перебираем все пары соседних элементов (их 9999) и оставляем те, у которых сумма меньше 984. Таких пар 5001.
Наибольшая из сумм этих пар равна 962, её абсолютное значение – 962.
Ответ: 5001 962.
18
Задание №18
#949641 баллЗадачи на динамику для таблиц
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных

1_18.ods
Правильный ответ
2476 436
Пояснение
Заполняем две вспомогательные таблицы 20 × 20 – максимальную и минимальную накопленные суммы. В клетку можно прийти сверху или слева, если между клетками нет стены.
Конечными считаются клетки, у которых справа и снизу стоят стены. В данной таблице их четыре; накопленные в них суммы (максимум; минимум) равны (792; 436), (1379; 790), (2476; 831) и (2230; 1423).
Максимальная из всех итоговых сумм равна 2476, минимальная – 436.
Ответ: 2476 436.
19
Задание №19
#949651 баллТеория игр
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в одну из куч (по своему выбору) 4 камня;
– увеличить количество камней в одной из куч (по своему выбору) в 3 раза.
Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (24, 30), (20, 34), (60, 30), (20, 90).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 154. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую игровую позицию, при которой в двух кучах суммарно 154 камня или больше. В начальный момент в первой куче 11 камней, во второй куче – S камней; 1 ≤ S ≤ 142.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
Правильный ответ
16
Пояснение
Ваня выигрывает первым ходом, если после хода Пети из позиции (a, b) он может получить сумму не менее 154, то есть если max(a + b + 4, 3a + b, a + 3b) ≥ 154.
При S ≤ 47 Петя не может выиграть первым ходом: наибольшая достижимая им сумма равна max(33 + S, 11 + 3S) < 154.
Проверяем S по возрастанию. При S = 15 после любого хода Пети (30, 30, 48 или 56 камней в сумме) Ваня не может набрать 154: наибольшая сумма получается из (11, 45) и равна 11 + 135 = 146.
При S = 16 Петя может неудачно сходить в позицию (11, 48). Тогда Ваня утраивает вторую кучу: (11, 144), сумма 155 ≥ 154, и Ваня выигрывает.
Ответ: 16.
20
Задание №20
#949661 баллТеория игр
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Правильный ответ
39 40
Пояснение
Петя выигрывает первым ходом при S ≥ 48 (тогда 11 + 3S ≥ 154). Значит, нужное S не превосходит 47.
Петя выигрывает вторым ходом, если у него есть ход в такую позицию, из которой Ваня не может выиграть сразу, а после любого хода Вани Петя набирает 154 камня или больше.
Перебор всех S от 1 до 47 по дереву игры даёт значения 39, 40, 43, 45, 46, …
Два наименьших из них – 39 и 40.
Ответ: 39 40.
21
Задание №21
#949671 баллТеория игр
Для игры, описанной в задании 19, найдите наименьшее значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Правильный ответ
41
Пояснение
Нужно найти S, при котором Петя не может выиграть первым ходом, после любого хода Пети Ваня выигрывает не более чем за два своих хода, но хотя бы после одного хода Пети Ваня не может выиграть сразу.
Перебор по дереву игры даёт значения S = 41, 42 и 44.
При S = 41 из позиций (11, 123) и (33, 41) Ваня выигрывает одним ходом, а из позиций (15, 41) и (11, 45) – только вторым ходом. Значит, гарантированного выигрыша первым ходом у Вани нет, но выигрыш за два хода есть.
Ответ: 41.
22
Задание №22
#949681 баллМногопоточность
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример организации данных в файле

ID процесса B Время выполнения процесса B (мс) ID процесса(-ов) A

1 3 0

2 4 1

3 2 2; 4

4 5 0

5 8 1; 4

6 3 1

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

1_22.ods
Правильный ответ
34
Пояснение
Время завершения процесса p равно его собственному времени плюс наибольшее из времён завершения процессов, от которых он зависит: t(p) = time(p) + max t(зависимости). Для независимого процесса t(p) = time(p).
Считаем t(p) для всех 25 процессов файла в порядке зависимостей.
Всё вычисление завершится тогда, когда завершится последний процесс, то есть в момент max t(p) = 34 мс.
Ответ: 34.
23
Задание №23
#949691 баллПоиск количества программ
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Умножить на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является 39 и при этом траектория вычислений не содержит числа 14?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABC при исходном числе 7 траектория состоит из чисел 8, 16, 48.
Правильный ответ
188
Пояснение
Обозначим через N(n) количество программ, переводящих число n в число 39 так, чтобы траектория не содержала числа 14.
Тогда N(39) = 1, N(n) = 0 при n > 39, а для остальных n
N(n) = N(n + 1) + N(2n) + N(3n),
причём слагаемые, которые дают число 14, отбрасываются.
Считая значения от 39 вниз до 2, получаем N(2) = 188.
Ответ: 188.
24
Задание №24
#949701 баллОбработка строк, нахождение подстроки
Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F.
Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых пара символов BC (в указанном порядке) встречается ровно 190 раз.
В ответе запишите число – количество символов в найденной последовательности.
Для выполнения этого задания следует написать программу.

1_24.txt
Правильный ответ
2287
Пояснение
Найдём все позиции i, в которых начинается пара BC. Их 1 055 932.
Отрезок содержит ровно 190 пар тогда и только тогда, когда это 190 подряд идущих вхождений p_j, …, p_j+189. Чтобы отрезок был как можно длиннее, он должен начинаться сразу после предыдущего вхождения (в позиции p_j−1 + 1) и заканчиваться на первом символе следующего вхождения (в позиции p_j+190).
Перебирая j, получаем наибольшую длину 2287.
Ответ: 2287.
25
Задание №25
#949711 баллПроверка делимости
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 89*6?7?9?, делящиеся на 9874 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 9874.
Количество строк в таблице для ответа избыточно.
Правильный ответ
8901677598 901527 8905627198 901927 8912617990 902635 8941667298 905577 8952607690 906685 8970607992 908508 8988647790 910335
Пояснение
Перебираем числа, кратные 9874, от 9874 до 10¹⁰ и проверяем каждое на соответствие маске: запись начинается с 89, затем идёт произвольная (возможно пустая) последовательность цифр, а последние шесть цифр имеют вид 6?7?9?.
Условию удовлетворяют семь чисел:

Число Частное

8901677598 901527

8905627198 901927

8912617990 902635

8941667298 905577

8952607690 906685

8970607992 908508

8988647790 910335

Ответ: 8901677598 901527 8905627198 901927 8912617990 902635 8941667298 905577 8952607690 906685 8970607992 908508 8988647790 910335.
26
Задание №26
#949722 баллаСортировка
В магазине продаётся N товаров нескольких артикулов. Товары одного артикула имеют одинаковую цену. Учёт товаров ведётся поштучно, для каждой единицы товара известен её текущий статус (продана или нет). Товары разделены на две категории: дорогие и дешёвые. Дорогими считаются товары, цена на которые превышает среднюю цену (среднее арифметическое) всех товаров в базе данных магазина без учёта их текущего статуса. Остальные товары считаются дешёвыми.
Лидером продаж называется товар с таким артикулом, наибольшее количество единиц которого продано. Лидер продаж выбирается среди дорогих товаров, а если продано одинаковое количество дорогих товаров с разными артикулами, лидером выбирается товар с наибольшей ценой. Если и таких товаров несколько, лидер продаж – тот из них, которого осталось меньше всего.
Найдите суммарную выручку магазина от реализации товара – лидера продаж, а также оставшееся количество товара с этим артикулом.
Входные данные
В первой строке входного файла находится число N – количество товаров в базе данных магазина (натуральное число, не превышающее 10 000). В каждой из следующих N строк находится три числа, разделённых пробелом: артикул товара (натуральное число, не превышающее 100 000), его цена (натуральное число, не превышающее 10 000) и статус (0, если товар уже продан, и 1, если ещё не продан).
Выходные данные
Два числа: сумма выручки от реализации товара – лидера продаж, а также количество товара с этим артикулом, оставшееся в магазине.
Типовой пример организации данных во входном файле
8
10 100 1
3 10 0
10 100 0
2 10 1
10 100 0
3 10 1
11 100 0
1 200 0
При таких исходных данных дорогими являются товары стоимостью 100 и 200 рублей. Больше всего было продано товара с артикулом 10. В продаже остался один такой товар. Условию задачи удовлетворяет ответ: 200 1.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

1_26.txt
Правильный ответ
43656 36
Пояснение
Считаем среднюю цену всех 9992 единиц товара: она равна примерно 558,11. Дорогими считаются товары с ценой выше этого значения.
Среди дорогих товаров подсчитываем для каждого артикула количество проданных единиц. Наибольшее количество – 51 единица – продано сразу у трёх артикулов: 37134 (цена 831), 51786 (цена 856, остаток 37) и 46481 (цена 856, остаток 36).
По цене выбираем два артикула с ценой 856, а среди них – тот, которого осталось меньше: артикул 46481.
Выручка: 51 × 856 = 43 656. Осталось 36 единиц.
Ответ: 43656 36.

ID процесса B	Время выполнения процесса B (мс)	ID процесса(-ов) A
1	3	0
2	4	1
3	2	2; 4
4	5	0
5	8	1; 4
6	3	1

Число	Частное
8901677598	901527
8905627198	901927
8912617990	902635
8941667298	905577
8952607690	906685
8970607992	908508
8988647790	910335

Задание №27

#949732 баллаОптимальный алгоритм для большого количества данных

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку (звезду) этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

$d ( A , B ) = \sqrt{ ( x_2 - x_1 )^2 + ( y_2 - y_1 )^2 }$

Каждая звезда помимо координат на плоской карте характеризуется своим спектральным классом и классом светимости. Спектральный класс определяет цвет (который связан с температурой звезды) следующим образом.

Обозначение спектрального класса (латинская буква)	O	B	A	F	G	K	M
Цвет звезды	Голубой	Бело-голубой	Белый	Жёлто-белый	Жёлтый	Оранжевый	Красный

Каждый из спектральных классов, в свою очередь, делится на подклассы от 0 до 9 в порядке уменьшения температуры. Обозначение подкласса ставится после обозначения спектрального класса (например, B2).
Класс светимости звезды обозначим римскими цифрами от I до VII.

Обозначение класса светимости	I	II	III	IV	V	VI	VII
Светимость	Сверхгигант	Яркий гигант	Гигант	Субгигант	Карлик	Субкарлик	Белый карлик

В файле A хранится информация о точках двух кластеров, где H = 6,0 и W = 5,5 для каждого кластера. В каждой строке сначала записана информация о расположении на карте одной звезды: координата x, затем координата y. Далее в той же строке для звёзд классов светимости I–VI указываются спектральный класс, подкласс и класс светимости. Обозначения классов ничем не разделяются. Для звёзд класса светимости VII (Белый карлик) обозначения спектрального класса и подкласса в файле не указываются. Известно, что количество точек не превышает 2000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6,0, W = 5,5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична структуре в файле А.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: A_x и A_y – абсциссу и ординату красного гиганта, ближайшего к центру кластера, который содержит наименьшее количество точек.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B₁ – расстояние между центрами кластеров с наименьшим и наибольшим количеством оранжевых гигантов и B₂ – наибольшее расстояние между жёлтыми карликами одного кластера.

В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютной величины произведения A_x × 10 000, затем целую часть абсолютной величины произведения A_y × 10 000; во второй строке – сначала целую часть произведения B₁ × 10 000, затем целую часть произведения B₂ × 10 000.

Пример организации данных в одном из исходных файлов для случая четырёх звёзд
5,01788 8,32466 G2V
4,289251 6,955186 VII
4,619358 5,524697 B7V
6,91934 20,425391 G2V

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

1_27_A.txt

1_27_B.txt

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

44694 69754 138716 34029

Пояснение

Кластеры разделены большими промежутками, поэтому их находят иерархической кластеризацией с одиночной связью (или методом DBSCAN).

Файл A. Точки делятся на два кластера – из 114 и 121 точки. Меньший кластер содержит 114 точек, его центр – звезда с координатами (4,960398; 7,345450).

Красный гигант – это звезда спектрального класса M и класса светимости III. Ближайший к центру красный гигант имеет координаты (4,469472; 6,975433).

A_x × 10 000 = 44 694,72, целая часть 44694; A_y × 10 000 = 69 754,33, целая часть 69754.

Файл Б. Точки делятся на три кластера – из 288, 393 и 1170 точек. Оранжевых гигантов (класс K, светимость III) в них 25, 28 и 87 соответственно.

Центр кластера с 25 оранжевыми гигантами – (18,794456; 36,905542), центр кластера с 87 оранжевыми гигантами – (11,746691; 24,957689). Расстояние между ними B₁ = 13,8716323, поэтому целая часть B₁ × 10 000 равна 138716.

Наибольшее расстояние между жёлтыми карликами (класс G, светимость V) одного кластера равно 3,4029521, поэтому целая часть B₂ × 10 000 равна 34029.

Ответ: 44694 69754 138716 34029.

Задание 1 из 27

Номер пункта	1	2	3	4	5	6	7
1		4					5
2	4				8	9	6
3						10	7
4					11
5		8		11		12
6		9	10		12		13
7	5	6	7			13