ЕГЭ по информатике, вариант 1

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

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

Задание выполняется с использованием прилагаемого файла. В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц (листов). Таблица «Движение товаров» содержит записи о поступлении товаров со склада в магазины в течение июня 2026 г., а также информацию о проданных товарах. Поле «Тип операции» содержит значение «Поступление» или «Продажа», а в поле «Количество упаковок» — сколько упаковок товара поступило или продано за день. Таблица «Товар» содержит артикул, отдел, наименование, единицу измерения, количество в упаковке и цену за упаковку. Таблица «Магазин» содержит ID магазина, район и адрес. На сколько упаковок товаров больше поступило, чем было продано, в магазинах района «Центральный» за период с 3 по 12 июня включительно? Если продано больше, чем поступило, ответ запишите со знаком «минус». В ответе запишите только число.

По каналу связи передаются сообщения, содержащие только буквы А, Н, О, С, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 0110, С – 100, Т – 1011. Для двух оставшихся букв О и Н кодовые слова неизвестны. Какое наименьшее количество двоичных знаков потребуется для кодирования слова НАНОСНО? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. Далее эта запись обрабатывается по следующему правилу: а) если количество единиц в записи чётное, то справа дописывается 0, а слева — 10; б) если количество единиц нечётное, то справа дописывается 1, а слева — 11. Полученная таким образом запись является двоичной записью искомого числа R. 3. Результат переводится в десятичную систему и выводится на экран. Сколько различных чисел R из отрезка [110; 326] может быть получено в результате работы этого алгоритма?

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

Камера каждые несколько секунд делает снимок $1280 \times 720$ пикселей, на цвет пикселя отводится 8 бит. Снимки сжимаются, после сжатия размер каждого составляет 40 % от исходного. Сколько Мбайт (наименьшее целое) нужно, чтобы сохранить 20 снимков?

Все 4-буквенные слова, составленные из букв А, Л, М, Н, Р, Т, записаны в алфавитном порядке и пронумерованы, начиная с 1. Вот начало списка: 1. АААА 2. АААЛ 3. АААМ …… Под каким номером в этом списке стоит последнее слово, которое начинается с буквы А и не содержит буквы Л?

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

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Даны адрес узла 248.5.64.187 и маска 255.255.255.192. Сколько в этой сети адресов, которые можно назначить узлам (адрес сети и широковещательный адрес узлам не назначаются)?

На предприятии каждой изготовленной детали присваивают серийный номер из 268 символов. В базе данных для хранения каждого номера отведено одинаковое и минимально возможное целое число байт; символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 12450 серийных номеров отведено не более 4073 Кбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на ячейки. В каждой ячейке находится ровно один символ, включая пустой символ λ. На каждом такте головка обозревает одну ячейку, может изменить символ в ней и сдвинуться на соседнюю ячейку влево или вправо, после чего переходит в новое состояние. Программа задаётся таблицей: на пересечении состояния и символа — команда из трёх элементов через запятую: записываемый символ; L, R — сдвиг влево или вправо, S — остановка после выполнения команды; новое состояние. В начальный момент головка находится в состоянии q0. На ленте в соседних ячейках записано двоичное представление числа 1699 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами λ. В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Программа работы исполнителя:Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.

Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены буквами: A. Прибавь 1 B. Прибавь 4 Первая команда увеличивает число на экране на 1, вторая — увеличивает его на 4. Программа для исполнителя — это последовательность команд. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Сколько существует программ, для которых при исходном числе 12 результатом является число 49, при этом траектория вычислений содержит число 19?

Операнды арифметического выражения записаны в системе счисления с основанием 11: $\text{3xA6}_{11}$ + $\text{4x9051}_{11}$ + $\text{A98x}_{11}$ В записи чисел переменной x обозначена неизвестная цифра из алфавита 11-ричной системы счисления. Определите наименьшее значение x, при котором значение выражения кратно 21. Для найденного x вычислите частное от деления значения выражения на 21 и укажите его в ответе в десятичной системе счисления.

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m»; Для какого наименьшего натурального числа A логическое выражение ДЕЛ(x, 11) → (¬ДЕЛ(x, 5) → ¬ДЕЛ(x, A)) истинно (т. е. принимает значение 1) при любом целом положительном значении переменной x?

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан соотношениями: F(n) = 1 при n = 1; F(n) = n · F(n − 1), если n > 1. Чему равно значение выражения $(F(2038) + 7 \cdot F(2037)) / F(2036)$?

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

Задание выполняется с использованием прилагаемого файла. Квадрат разлинован на $13 \times 13$ клеток. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. В каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

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

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

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

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

Задание выполняется с использованием прилагаемого файла. В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Две вершины графа не могут быть соединены более чем одним ребром. Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Вершины графа могут быть пронумерованы не подряд. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Задание выполняется с использованием прилагаемого файла. Текстовый файл состоит из символов A, E, I, O, U. Определите максимальное количество идущих подряд символов, среди которых нет двух одинаковых соседних. Для выполнения этого задания следует написать программу.

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 10^8, найдите все числа, соответствующие маске 3?1?52*0, делящиеся на 4486 без остатка. В ответе запишите все найденные числа в порядке возрастания, а через пробел после каждого из них — соответствующее частное от деления на 4486.

Задание выполняется с использованием прилагаемого файла. Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда для очередного запроса остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Записи в журнале не упорядочены по времени. Напишите программу обработки журнала и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов (в Кбайт) трёх наибольших резервных копий, созданных не позднее 07:59:59. Входные данные. Первая строка файла содержит два натуральных числа: N — количество строк в журнале и K — вместимость раздела памяти в Кбайт. Каждая из следующих N строк содержит время регистрации запроса в формате ЧЧ:ММ:СС и два натуральных числа: C — идентификатор устройства и S — объём данных запроса в Кбайт (S < K). В ответе запишите два числа: сначала идентификатор устройства, затем сумму объёмов резервных копий.

Задание выполняется с использованием прилагаемого файла. Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами от I до VII (в римской системе счисления). Учёный решил провести кластеризацию частиц по значениям их кинетической энергии, то есть разбить их множество на 4 непересекающихся непустых подмножеств (кластеров), таких, что модуль разности кинетических энергий любых двух частиц каждого подмножества не превосходит R = 2,0. Гарантируется, что такое разбиение существует и единственно. Центром кластера назовём такую его частицу, для которой сумма модулей разности кинетических энергий со всеми остальными частицами этого кластера минимальна; для каждого кластера центр единственный. В каждой строке файла: координаты x и y, проекции скорости Vx и Vy, масса m и признак. Значения разделяются пробелами. Для каждого кластера определите его центр, затем найдите два числа: Q1 — наибольшее евклидово расстояние между частицами одного кластера, имеющими признак II, и Q2 — максимальное значение кинетической энергии для центра кластера. В ответе запишите два числа: сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000. Для справки: кинетическая энергия частицы E = m(Vx² + Vy²)/2.