ЕГЭ 2024 Ноябрь Информатика Вариант 5

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

	П1	П2	П3	П4	П5	П6	П7	П8
П1		15		20				18
П2	15		25
П3		25				24		22
П4	20						12
П5						13	16	17
П6			24		13			15
П7				12	16
П8	18		22		17	15

 

 

 

 

 

 

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

2.  Тип 2 № 48423

Логическая функция F задаётся выражением:

 

(x → (y ≡ w)) ∧ (y ≡ (w → z)).

 

Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.

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

 

 

Переменная 1	Переменная 2	Переменная 3	Переменная 4	Функция
???	???	???	???	F
1		0	1	1
0	0		0	1
0	0	0	1	0

 

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

 

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

 

 

 

Переменная 1	Переменная 2	Функция
???	???	F
0	1	0

 

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

3.  Тип 3 № 58320

В файле приведён фрагмент базы данных «Машины», принадлежащей союзу автодилеров, предлагающему покупателям автомобили. База данных состоит из трёх связанных прямоугольных таблиц.

 

Задание 3

 

Таблица «Наличие» содержит записи о поступивших дилеру и проданных покупателям машинах. Поле Тип операции содержит значение «Поступило дилеру» или «Отдано покупателю». Заголовок таблицы имеет вид:

 

 

ID операции

Дата

ID машины

ID дилера

Количество

Тип операции

 

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

 

 

ID машины

Категория

Наименование

 

Таблица «Дилеры» содержит информацию о местах расположения дилерских центров.

Заголовок таблицы имеет вид:

 

 

ID дилера

Адрес

ФИО директора

 

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

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

В ответе запишите только число.

4.  Тип 4 № 13562

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А  — 11, B  — 101, C  — 0.

Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наибольшему возможному двоичному числу.

 

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

5.  Тип 5 № 16033

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

1)  Строится двоичная запись числа N.

2)  К этой записи дописываются справа ещё два разряда по следующему правилу:

       а)  если N чётное, в конец числа (справа) дописывается сначала ноль, а затем единица.

       б)  если N нечётное, справа дописывается сначала единица, а затем ноль.

Например, двоичная запись 100 числа 4 будет преобразована в 10001, а двоичная запись 111 числа 7 будет преобразована в 11110.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R  — результата работы данного алгоритма.

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

6.  Тип 6 № 47393

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

Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

7.  Тип 7 № 35896

В информационной системе хранятся изображения размером 1024 × 768 пикселей. Методы сжатия изображений не используются. Каждое изображение дополняется служебной информацией, которая занимает 640 Кбайт. Для хранения 2048 изображений потребовалось 2 Гбайт. Сколько цветов использовано в палитре каждого изображения?

8.  Тип 8 № 7986

Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

9.  Тип 9 № 59833

Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия:

—  в строке есть только два равных числа, остальные 4 различны;

—  среднее арифметическое повторяющихся чисел меньше, чем среднее арифметическое остальных чисел строки.

В ответе запишите только число.

 

Задание 9

 

10.  Тип 10 № 27584

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «его» или «Его» в тексте романа в стихах А. С. Пушкина «Евгений Онегин». Другие формы слова «его» учитывать не следует. В ответе укажите только число.

 

Задание 10

 

11.  Тип 11 № 18589

Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 13 символов, каждый из которых может быть одной из 16 допустимых заглавных букв или одной из 10 цифр. Для записи личного кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения состоит из двух натуральных чисел, не превышающих 100, каждое из которых кодируется как двоичное число и занимает минимально возможное целое число бит. Личный код и код подразделения записываются подряд и вместе занимают минимально возможное целое число байт. Всего на пропуске хранится 32 байт данных. Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число  — количество байт.

12.  Тип 12 № 9764

Исполнитель Редактор получает на вход строку цифр и преобразует её.

Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А)  заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б)  нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

ЕСЛИ условие

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

 

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

НАЧАЛО

ПОКА нашлось (333) ИЛИ нашлось (999)

ЕСЛИ нашлось (333)

ТО заменить (333, 9)

ИНАЧЕ заменить (999, 3)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

13.  Тип 13 № 18588

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

Например, если IP-⁠адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Узлы с IP-⁠адресами 98.162.71.151 и 98.162.71.155 находятся в разных сетях. Чему равно наименьшее количество возможных единиц в масках этих сетей?

14.  Тип 14 № 47218

Операнды арифметического выражения записаны в системе счисления с основанием 15:

 

123x5₁₅ + 1x233₁₅.

 

В записи чисел переменной x обозначена неизвестная цифра из алфавита 15-⁠ричной системы счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 14. Для найденного значения x вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.

15.  Тип 15 № 18566

Для какого наименьшего целого неотрицательного числа A выражение

 

(3m + 4n > 66) ∨ (m ≤ A) ∨ (n < A)

 

тождественно истинно при любых целых неотрицательных m и n?

16.  Тип 16 № 40732

Обозначим остаток от деления натурального числа a на натуральное число b как a mod b.

Алгоритм вычисления значения функции F(n), где n  — целое неотрицательное число, задан следующими соотношениями:

F(0)  =  0;

F(n)  =  F(n − 1) + 1, если n > 0 и при этом n mod 3  =  2;

F(n)  =  F((n − n mod 3) / 3), если n > 0 и при этом n mod 3 < 2.

 

Укажите наименьшее возможное n, для которого F(n)  =  6.

17.  Тип 17 № 45251

В файле содержится последовательность натуральных чисел. Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар последовательности, в которых хотя бы одно число делится на минимальный элемент последовательности, кратный 21. Гарантируется, что такой элемент в последовательности есть. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

 

17.txt

 

Ответ:

 

18.  Тип 18 № 27666

Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх  — в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

 

Задание 18

 

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

Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.

Пример входных данных:

 

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

 

Для указанных входных данных ответом должна быть пара чисел 35 и 15.

19.  Тип 19 № 27805

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 75 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 63.

Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 63 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 62.

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

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

20.  Тип 20 № 27806

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 75 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 63.

Победителем считается игрок, сделавший последний ход, то емть первым получивший кучу, в которой будет 63 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 62.

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

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

—  Петя не может выиграть за один ход;

—  Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

21.  Тип 21 № 27807

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 75 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 63.

Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 63 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 62.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

—  у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

—  у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

22.  Тип 22 № 52193

В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов  — поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.

 

Задание 22

 

В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.

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

23.  Тип 23 № 18570

Исполнитель РазДваТри преобразует число на экране.

У исполнителя есть три команды, которым присвоены номера.

1.  Прибавить 1.

2.  Умножить на 2.

3.  Умножить на 3.

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья умножает на 3.

Программа для исполнителя РазДваТри  — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 50, и при этом траектория вычислений содержит число 14 и не содержит числа 16?

Траектория вычислений  — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 3 траектория будет состоять из чисел 9, 10, 20.

24.  Тип 24 № 33494

Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите символ, который чаще всего встречается в файле сразу после буквы E.

Например, в тексте EBCEEBEDDD после буквы E два раза стоит B, по одному разу  — E и D. Для этого текста ответом будет B.

Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.

 

Задание 24

 

25.  Тип 25 № 33104

 

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [289123456; 389123456] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.

Например, в диапазоне [5; 16] ровно три различных натуральных делителя имеет число 16, поэтому для этого диапазона вывод на экране должна содержать следующие значения:

16 8

 

Ответ:

 

 

 

 

 

 

 

 

 

 

 

 

26.  Тип 26 № 33528

Предприятие производит оптовую закупку некоторых изделий A и B, на которую выделена определённая сумма денег. У поставщика есть в наличии партии этих изделий различных модификаций по различной цене. На выделенные деньги необходимо приобрести как можно больше изделий A независимо от модификации. Если у поставщика закончатся изделия A, то на оставшиеся деньги необходимо приобрести как можно больше изделий B. Известны выделенная для закупки сумма, а также количество и цена различных модификаций данных изделий у поставщика. Необходимо определить, сколько будет закуплено изделий B и какая сумма останется неиспользованной.

Входные данные.

 

Задание 26

 

Первая строка входного файла содержит два целых числа: N  — общее количество партий изделий у поставщика и M  — сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк описывает одну партию и содержит два целых числа (цена одного изделия в рублях и количество изделий в партии) и один символ (латинская буква A или B), определяющий тип изделия. Все данные в строках входного файла отделены одним пробелом.

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

Пример входного файла:

4 1000

30 8 A

50 12 B

40 14 A

30 60 B

В данном случае сначала нужно купить изделия A: 8 изделий по 30 рублей и 14 изделий по 40 рублей. На это будет потрачено 800 рублей. На оставшиеся 200 рублей можно купить 6 изделий B по 30 рублей. Таким образом, всего будет куплено 6 изделий B и останется 20 рублей. В ответе надо записать числа 6 и 20.

 

Ответ:

 

27.  Тип 27 № 35916

В текстовом файле записан набор натуральных чисел, не превышающих 10⁸. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, сумма которых делится на 3. Какую наименьшую сумму можно при этом получить?

Входные данные.

 

Файл A

Файл B

 

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.

Пример входного файла:

4

5

8

14

11 В данном случае есть четыре подходящие тройки: 5, 8, 11 (сумма 24); 5, 8, 14 (сумма 27); 5, 14 11 (сумма 30) и 8, 14, 11 (сумма 33). В ответе надо записать число 24.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

 

Ответ: