ЕГЭ 2024 Декабрь Информатика Вариант 15

РЕШУ ЕГЭ — информатика

Вариант № 17007946

1.  Тип 1 № 63017

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога АБ длиннее дороги ЖИ. Определите длину дороги ВД.

2.  Тип 2 № 38936

Логическая функция F задаётся выражением (x ≡ ¬y) → ((x ∧ w) ≡ (z ∧ ¬w)). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

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

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

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

3.  Тип 3 № 37479

В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.

3.xlsx

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

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

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

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

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

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

4.  Тип 4 № 13616

По каналу связи передаются сообщения, содержащие только пять букв: П, И, Л, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы И используется кодовое слово 1; для буквы О используется кодовое слово 01.

Какова минимальная общая длина кодовых слов для всех пяти букв?

Примечание. условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

5.  Тип 5 № 18582

Автомат обрабатывает натуральное число N по следующему алгоритму:

1.  Строится двоичная запись числа N без ведущих нулей.

2.  Если в полученной записи единиц больше, чем нулей, то справа приписывается единица. Если нулей больше или нулей и единиц поровну, справа приписывается ноль.

3.  Полученное число переводится в десятичную запись и выводится на экран.

Пример. Дано число N  =  13. Алгоритм работает следующим образом.

1.  Двоичная запись числа N: 1101.

2.  В записи больше единиц, справа приписывается единица: 11011.

3.  На экран выводится десятичное значение полученного числа 27.

Какое наименьшее число, превышающее 100, может получиться в результате работы автомата?

6.  Тип 6 № 56534

Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. Черепаха может выполнять три команды: Вперёд n (n  — число), Направо m (m  — число) и Налево m (m  — число). По команде Вперёд n Черепаха перемещается вперёд на n единиц. По команде Направо m Черепаха поворачивается на месте на m градусов по часовой стрелке, при этом соответственно меняется направление дальнейшего движения. По команде Налево m Черепаха поворачивается на месте на m градусов против часовой стрелки, при этом соответственно меняется направление дальнейшего движения.

В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат).

Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что заданная последовательность из S команд повторится k раз.

Черепаха выполнила следующую программу (x в тексте программы  — некоторое натуральное число):

Повтори 3 [Вперёд 7 Направо 90]

Вперёд 8

Повтори 3 [Налево 90 Вперёд 5].

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

7.  Тип 7 № 15849

Автоматическая камера производит растровые изображения размером 600 на 1000 пикселей. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Объём файла с изображением не может превышать 250 Кбайт без учёта размера заголовка файла. Какое максимальное количество цветов можно использовать в палитре?

8.  Тип 8 № 3228

Все 5-⁠буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

1.  ААААА

2.  ААААО

3.  ААААУ

4.  АААОА

...

Укажите номер слова УАУАУ.

9.  Тип 9 № 48457

В каждой строке электронной таблицы записаны шесть натуральных чисел.

Определите, сколько в таблице строк, для которых выполнены следующие условия:

—  в строке встречается ровно четыре различных числа: два из них по два раза, два  — по одному;

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

В ответе запишите число  — количество строк, для которых выполнены эти условия.

Задание 9

10.  Тип 10 № 51979

Определите, сколько раз в тексте романа Михаила Булгакова «Мастер и Маргарита» встречается фамилия Лиходеев в начальной форме.

Задание 10

11.  Тип 11 № 15981

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. Для построения идентификатора используют только прописные латинские буквы (26 букв). В базе данных для хранения каждого пароля отведено одинаковое минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым минимально возможным количеством бит. Кроме пароля для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено одинаковое целое количество байт на каждого пользователя. Для хранения информации о 15 пользователях потребовалось 300 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число  — количество байт.

12.  Тип 12 № 15982

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

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

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

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

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

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

Цикл

ПОКА условие

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

КОНЕЦ ПОКА

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

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 82 единиц?

НАЧАЛО

    ПОКА нашлось (11111) ИЛИ нашлось (888)

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

            ТО заменить (11111, 88)

        ИНАЧЕ

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

                ТО заменить (888, 8)

            КОНЕЦ ЕСЛИ

        КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

13.  Тип 13 № 13623

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

14.  Тип 14 № 19065

Сколько единиц содержится в двоичной записи значения выражения: 4⁸ + 2⁸ − 8?

15.  Тип 15 № 27276

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

(2x + 3y A) ∨ (x ≥ y) ∨ (y 24)

тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных x и y?

16.  Тип 16 № 4937

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

F(1)  =  1;

F(2)  =  1;

F(n)  =  F(n – 2) · (n – 1) при n 2.

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

17.  Тип 17 № 58484

Файл содержит последовательность натуральных чисел, не превышающих 20 000. Назовём парой два идущих подряд элемента последовательности.

Задание 17

Определите количество пар, для которых выполняются следующие условия:

—  ровно одно число в паре четырёхзначное;

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

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

Ответ:

18.  Тип 18 № 61364

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

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

На поле может быть несколько финальных клеток.

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

Задание 18

Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до какой-⁠нибудь финальной клетки.

Задание 2. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.

В обоих заданиях энергии должно хватить и на прохождение финальной клетки.

Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.

Ответ:

19.  Тип 19 № 27797

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой  — 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (30, 7), (10, 8), (10, 21). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было шесть камней, во второй куче  — S камней; 1 ≤ S ≤ 61.

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

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

20.  Тип 20 № 27798

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой  — 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (30, 7), (10, 8), (10, 21). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было шесть камней, во второй куче  — S камней; 1 ≤ S ≤ 61.

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

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

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

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

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

21.  Тип 21 № 27799

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой  — 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (30, 7), (10, 8), (10, 21). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было шесть камней, во второй куче  — S камней; 1 ≤ S ≤ 61.

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

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

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

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

22.  Тип 22 № 59700

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс В зависит от процесса A, если для выполнения процесса В необходимы результаты выполнения процесса А. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы  — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Задание 22

Типовой пример организации данных в файле:

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

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

23.  Тип 23 № 55640

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

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

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

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

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

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

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

Программа для исполнителя  — это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 213 последовательно преобразует его в 3, 4, 8.

Сколько существует программ, которые преобразуют исходное число 1 в число 24 и при этом не содержат двух последовательных команд сложения и двух последовательных команд умножения?

24.  Тип 24 № 59702

Текстовый файл состоит из символов T, U, V, W, X, Y и Z.

Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ Y встречается не более 150 раз.

Для выполнения этого задания следует написать программу.

Задание 24

25.  Тип 25 № 52196

Маска числа  — это последовательность цифр, в которой могут встречаться специальные символы «?» и «*». Символ «?» означает ровно одну произвольную цифру, символ «*» означает произвольную (в том числе пустую) последовательность цифр.

Пример. Маске 123*4?5 соответствуют числа 123405 и 12376415. Найдите все натуральные числа, не превышающие 10⁹, которые соответствуют маске 12*93?1? и при этом без остатка делятся на 3127.

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

Ответ:

26.  Тип 26 № 64911

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

Если после 40 минут ожидания в очереди окно не освободилось, клиент уходит. Если окно освободилось ровно через 40 минут ожидания, клиент не уходит и получает услугу.

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

Задание 26

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

Первая строка входного файла содержит целое число N (N ≤ 1000)  — общее количество клиентов, пришедших в отделение за один рабочий день. Каждая из следующих N строк описывает одного клиента и содержит 3 целых числа: время прихода клиента в отделение (количество минут с начала рабочего дня), время (количество минут), необходимое для обслуживания данного клиента, и номер окна, в которое ему необходимо обратиться. Гарантируется, что никакие два клиента не приходят в одно и то же время.

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

В ответе запишите два целых числа: сначала набольшее количество клиентов, обслуженных в одном окне, затем количество необслуженных клиентов.

Ответ:

27.  Тип 27 № 59705

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

Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее K мин., а сумма этих чисел была минимально возможной. Запишите в ответе найденную сумму.

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

Файл А

Файл В

Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число К  — минимальное количество минут, которое должно пройти между моментами передачами любых двух из трёх показаний, а во второй  — количество переданных показаний N (1 ≤  N 10 000 000, N  K). B каждой из следующих N строк находится одно натуральное число, не превышающее 10 000 000, которое обозначает значение силы тока в соответствующую минуту.

Запишите в ответе два числа: сначала значение искомой величины для файла A, затем  — для файла В.

Типовой пример организации данных во входном файле:

2

6

15

14

20

23

21

10

При таких исходных искомая величина равна 45  — это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.

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

Ответ: