Тренировочная работа №3 статград по информатике 11 класс в формате ЕГЭ 2025 года тренировочные варианты ИН2410301, ИН2410302 с ответами и решением для подготовки к государственному экзамену ФИПИ дата проведения пробника 28 января 2025.
→ Варианты заданий: скачать
→ Ответы и файлы: скачать
Тренировочная работа по информатике состоит из 27 заданий с кратким ответом, выполняемых с помощью компьютера. На выполнение тренировочной работы отводится 3 часа 55 минут (235 минут). Тренировочная работа выполняется с помощью специализированного программного обеспечения, предназначенного для проведения испытания в компьютерной форме. При выполнении заданий Вам будут доступны на протяжении всей работы текстовый редактор, редактор электронных таблиц, системы программирования.
Варианты ЕГЭ 2025 статград по информатике 11 класс
https://100ballnik.com/wp-content/uploads/2025/01/ИН2410301-ИН2410302-статград-информатика.pdf
Задания и ответы для ИН2410301
1 задание
На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога КИ короче дороги АГ. Определите длину дороги ДЖ.
Ответ: 22
2 задание
Логическая функция F задаётся выражением: (w → ¬(z ≡ y)) ∧ (z ∨ (y → x)) Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть заданы выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности. Тогда первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе нужно написать: yx.
Ответ: yxwz
3 задание
В файле приведён фрагмент базы данных «Продукты», содержащей информацию о поставках товаров и их продаже. База данных состоит из трёх таблиц. Таблица «Торговля» содержит записи о поставках и продажах товаров в магазинах города в июне 2021 г. Таблица «Товар» содержит данные о товарах. Таблица «Магазин» содержит данные о магазинах. На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. Используя информацию из приведённой базы данных, определите, в какой день в магазинах Заречного района выручка от продажи товаров отдела «Молоко» была наибольшей. В ответе запишите целое число от 1 до 30, соответствующее числу искомой даты. Например, ответ 1 означает, что наибольшая выручка была получена 1 июня.
Ответ: 20
4 задание
Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: И – 110, Н – 011, Ф – 00, О – 1111, Р – 11100, М – 11101, А – 1001, Т – 101, К – 1000. Сколько существует способов назначить для буквы Ю код, длина которого не превышает шести двоичных знаков?
Ответ: 14
5 задание
Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом. 1. Строится троичная запись числа N. 2. В полученной записи все нули заменяются на двойки, все двойки – на нули. Из полученного числа удаляются ведущие нули. 3. Результат переводится в десятичную систему счисления. 4. Результатом работы алгоритма становится модуль разности исходного числа N и числа, полученного на предыдущем шаге. Пример. Дано число N = 35. Алгоритм работает следующим образом. 1. Строим троичную запись числа N: 3510 = 10223. 2. Заменяем цифры и удаляем ведущие нули: 1022 → 1200. 3. Переводим в десятичную систему: 12003 = 4510. 4. Вычисляем модуль разности: | 35 – 45 | = 10. Результат работы алгоритма R = 10. При каком наименьшем N в результате работы алгоритма получится R = 1 864 246?
Ответ: 3323607
6 задание
Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. Черепаха может выполнять две команды: Вперёд n (n – число) и Направо m (m – число). По команде Вперёд n Черепаха перемещается вперёд на n условных единиц. По команде Направо m Черепаха поворачивается на месте на m градусов по часовой стрелке, при этом соответственно меняется направление дальнейшего движения. В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат). Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что заданная последовательность из S команд повторится k раз.
Черепаха выполнила следующую программу: Повтори 3 [Вперёд 19 Направо 90 Вперёд 3 Направо 90] Повтори 3 [Вперёд 5 Направо 90 Вперёд 11 Направо 90] Полученный при выполнении этой программы рисунок можно рассматривать как набор непересекающихся прямоугольников. Определите наибольшее количество точек с целочисленными координатами, находящихся внутри одного из этих прямоугольников. Точки, находящиеся на линиях, не учитывать.
Ответ: 28
7 задание
Книгу объёмом 1,5 Мбайт записали как аудиокнигу. Запись велась в формате стерео (2 канала) с частотой 32 кГц и разрешением 16 бит. За одну минуту записывалось в среднем 1,5 Кбайт текста. Записанный аудиофайл сжали и разделили на 60 фрагментов со средним размером 25 Мбайт. Определите, на сколько процентов уменьшился размер файла при сжатии. Заголовки и другую служебную информацию не учитывать. В ответе запишите число – округлённый до целого процент сжатия.
8 задание
Сколько существует натуральных чисел, не превышающих 855 000 000, запись которых в системе счисления с основанием 15 содержит ровно 8 различных цифр?
9 задание
В каждой строке электронной таблицы записаны восемь натуральных чисел, разбитых на две четвёрки. Первая четвёрка занимает столбцы с 1 по 4, вторая – с 5 по 8. Определите количество строк таблицы, для которых одновременно выполнены все следующие условия: – максимальное число строки встречается в ней ровно один раз; – максимальное число строки находится в первой четвёрке; – среднее арифметическое чисел первой четвёрки меньше среднего арифметического чисел второй четвёрки.
10 задание
Повесть братьев Стругацких «Понедельник начинается в субботу» состоит из трёх историй. Один из персонажей носит фамилию Хунта. Определите, сколько раз встречается эта фамилия в любом падеже в каждой из историй. В ответе запишите наибольшее из найденных чисел.
11 задание
Предприятие выпускает партии изделий. Каждая партия получает уникальный код из 21 символа. Каждый символ кода может быть любой строчной или заглавной латинской буквой. Все изделия в партии получают последовательные номера от 1 до общего числа изделий в партии. Запись о каждом изделии заносится в информационную систему. Запись содержит код изделия и некоторую дополнительную информацию. Код изделия состоит из кода партии и номера изделия в партии.
Для записи кода партии используется посимвольное кодирование, каждый символ кодируется одинаковым минимально возможным количеством битов. Номер изделия записывается как двоичное целое число, для записи каждого номера используется одинаковое минимально возможное количество битов. Для записи кода изделия в целом используется минимально возможное целое количество байтов. Для записи дополнительной информации о каждом изделии требуется 60 байт. Известно, что для хранения информации обо всех изделиях одной партии используется не более 80 Кбайт. Какое наибольшее количество изделий может быть в партии?
12 задание
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. Дана программа для Редактора: НАЧАЛО ПОКА нашлось (111) ИЛИ нашлось (22) заменить (111, 2) заменить (222, 1) заменить (221, 1) заменить (122, 1) заменить (22, 2) КОНЕЦ ПОКА КОНЕЦ Определите, сколько различных строк, содержащих ровно 5 единиц, может получиться в результате применения этой программы к строкам, состоящим только из единиц и двоек.
13 задание
В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места – нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0. Известно, что в двоичной записи адреса сети, к которой принадлежит узел 68.30.20.77, содержится столько же единиц, сколько нулей в двоичной записи маски этой сети. Сколько адресов, в двоичной записи которых ровно 10 единиц, содержится в этой сети?
14 задание
В системе счисления с основанием p выполняется равенство y27x + wy86 = xxz3y. Буквами x, y, z и w обозначены некоторые цифры из алфавита системы счисления с основанием p. Определите значение числа xyzwp и запишите это значение в десятичной системе счисления.
15 задание
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14&5 = 11102&01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула (x&5160 > 0 \/ x&3650 > 0) → (x&9545 = 0 → x&А > 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
16 задание
Обозначим через a%b остаток от деления натурального числа a на натуральное число b, а через a//b – целую часть от деления a на b. Функция F(n), где n – неотрицательное целое число, задана следующими соотношениями: F(n) = 0, если n = 0; F(n) = F(n//4) + n%4, если n>0 и n%4 < 2; F(n) = F(n//4) + n%4 – 1, если n%4 ≥ 2. Найдите минимальное n, для которого F(n) = 27, а F(n + 1) = 16.
17 задание
Файл содержит последовательность натуральных чисел, не превышающих 100 000. Назовём тройкой три идущих подряд элемента последовательности. Определите количество троек, для которых выполняются следующие условия: – в тройке есть четырёхзначные числа; – в тройке не более одного числа, у которого остаток от деления на 5 равен остатку от деления на 5 минимального элемента всей последовательности; – в тройке не менее двух чисел, у которых остаток от деления на 7 равен остатку от деления на 7 максимального элемента всей последовательности. В ответе запишите два числа: сначала количество найденных троек, затем максимальную величину суммы элементов этих троек.
18 задание
Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя. Для вашего удобства такие клетки выделены тёмным фоном. В остальных клетках записаны положительные числа. За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Клетка, из которой робот не может сделать допустимого хода (справа и снизу находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток. В начальный момент робот обладает некоторым запасом энергии.
Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки. Задание 2. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом. Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.
19 задание
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. Если количество камней в куче делится на целое k (2 ≤ k ≤ 9), то игрок может убрать из кучи k камней. Если количество камней в куче не делится ни на одно из указанных чисел, игрок убирает один камень, после чего выполняет ход по описанному выше правилу. Например, если в куче 12 камней, то за один ход можно убрать 2, 3, 4 или 6 камней, а если в куче 11 камней, то игрок за один ход сначала убирает один камень (остаётся 10), а затем убирает 2 или 5 камней. Игра завершается, когда количество камней в куче становится не более 15. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 15 или меньше камней. В начале игры в куче было S камней, S > 15. Укажите минимальное значение S, при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим первым ходом.
20 задание
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. В ответе запишите найденные значения в порядке возрастания.
21 задание
Для игры, описанной в задании 19, найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом.
22 задание
В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или нескольких других процессов – поставщиков данных. Если зависимый процесс получает данные от других процессов (поставщиков данных), то выполнение зависимого процесса не может начаться раньше завершения всех процессовпоставщиков. Длительность процесса не зависит от других параллельно выполняемых процессов, приостановка выполнения процесса не допускается. В таблице представлены идентификатор (ID) каждого процесса, его длительность в мс и ID поставщиков данных для зависимых процессов. Для независимых процессов в качестве ID поставщика данных указан 0. В момент, когда процесс готов к запуску, он ставится в очередь. Если несколько процессов оказываются готовы к запуску одновременно, первым ставится в очередь тот процесс, у которого меньше ID. Одновременно может выполняться не более 4 процессов. Если в какой-то момент в системе работает менее 4 процессов, то при наличии готовых к запуску процессов выбирается и запускается первый процесс из очереди. За какое время будут выполнены все процессы? В ответе напишите число – требуемое время в мс.
23 задание
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены буквами. A. Вычти 2 B. Если число кратно 3, Раздели на 3, Иначе Вычти 4 Программа для исполнителя – это последовательность команд. Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы BAB при исходном числе 99 траектория будет состоять из чисел 33, 31, 27. Сколько существует программ, которые преобразуют исходное число 36 в число 4 и при этом траектория вычислений не содержит числа 16?
24 задание
Текстовый файл содержит строку, состоящую из цифр от 1 до 9, знаков операций «+», «–» и «*» (сложение, вычитание и умножение) и заглавных латинских букв A, B, C, D. Назовём правильной суммой строку, которая содержит последовательность из одного или более десятичных чисел, в которой между каждыми двумя соседними числами стоит ровно один знак «+» или «–» и нет других знаков. Примеры правильных сумм: «23», «115+6», «1980+12–123–51+3».
Назовём результатом правильной суммы число, которое получится при выполнении записанных в соответствующей строке действий. Например, результат правильной суммы «2+3» – число 5, а результат правильной суммы «1+2–8+3» – число –2. Найдите в данной строке расположенную непосредственно после буквы A правильную сумму, содержащую наибольшее число символов, и вычислите её результат. Если несколько правильных сумм содержат одинаковое наибольшее число символов, выберите ту, которая имеет больший результат. В ответе запишите результат найденной суммы. Гарантируется, что ответ не превышает 2·109 .
25 задание
Маска числа – это последовательность цифр, в которой могут встречаться специальные символы «?» и «*». Символ «?» означает ровно одну произвольную цифру, символ «*» означает произвольную (в том числе пустую) последовательность цифр. Например, маске 123*4?5 соответствуют числа 123405 и 12376415. Найдите все натуральные числа, не превышающие 109 , которые соответствуют маске 4?5*07*3 и при этом без остатка делятся на 9341. В ответе запишите все найденные числа в порядке возрастания.
26 задание
При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной. При анализе результатов эксперимента рассматривают изолированные точки. Точка называется изолированной, если эта точка светлая (независимо от того, сколько частиц в неё попало), а другие светлые точки в том же ряду либо отсутствуют, либо находятся на расстоянии более 500. Вам необходимо по заданному протоколу определить наибольшее количество изолированных точек, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Первая строка входного файла содержит целое число N – общее количество частиц, попавших на экран. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду. В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем – номер ряда, в котором это количество встречается.
27 задание
В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям. По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров – кругов радиуса не более 3 единиц – так, что каждая точка попадает ровно в один кластер. Центром кластера считается та из входящих в него точек, для которой минимально среднее расстояние до всех остальных точек кластера. При этом расстояние вычисляется по стандартной формуле расстояния между точками на евклидовой плоскости. Радиусом кластера считается максимальное из расстояний от центра до остальных точек кластера.
Обработка результатов эксперимента включает следующие шаги: 1) кластер, содержащий наименьшее число точек, исключается; 2) определяются центры и радиусы всех оставшихся кластеров; 3) вычисляется средний радиус оставшихся кластеров. В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты X и Y точки, соответствующей одному испытанию. По данному протоколу надо определить средний радиус всех кластеров за исключением содержащего наименьшее число точек. Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. По данным каждого из представленных файлов определите средний радиус по описанным выше правилам. В ответе запишите два числа: сначала средний радиус для файла A, затем для файла B. В качестве значения указывайте целую часть от умножения найденного числового значения на 10 000.
Задания и ответы для ИН2410302
1. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога ЖИ короче дороги ВЕ. Определите длину дороги ДК.
Ответ: 26
2. Логическая функция F задаётся выражением: (x → ¬(y ≡ w)) ∧ (y ∨ (w → z)) Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть заданы выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности. Тогда первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе нужно написать: yx.
Ответ: wzyx
3. В файле приведён фрагмент базы данных «Продукты», содержащей информацию о поставках товаров и их продаже. База данных состоит из трёх таблиц. Таблица «Торговля» содержит записи о поставках и продажах товаров в магазинах города в июне 2021 г. Таблица «Товар» содержит данные о товарах. Таблица «Магазин» содержит данные о магазинах. На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. Используя информацию из приведённой базы данных, определите, в какой день в магазинах Первомайского района выручка от продажи товаров отдела «Бакалея» была наибольшей. В ответе запишите целое число от 1 до 30, соответствующее числу искомой даты. Например, ответ 1 означает, что наибольшая выручка была получена 1 июня.
Ответ: 12
4. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: И – 111, Н – 010, Ф – 011, О – 11000, Р – 0011, М – 10, А – 0010, Т – 000, К – 11001. Сколько существует способов назначить для буквы Ю код, длина которого не превышает шести двоичных знаков?
Ответ: 4
5. Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом. 1. Строится троичная запись числа N. 2. В полученной записи все нули заменяются на двойки, все двойки – на нули. Из полученного числа удаляются ведущие нули. 3. Результат переводится в десятичную систему счисления. 4. Результатом работы алгоритма становится модуль разности исходного числа N и числа, полученного на предыдущем шаге. Пример. Дано число N = 35. Алгоритм работает следующим образом. 1. Строим троичную запись числа N: 3510 = 10223. 2. Заменяем цифры и удаляем ведущие нули: 1022 → 1200. 3. Переводим в десятичную систему: 12003 = 4510. 4. Вычисляем модуль разности: | 35 – 45 | = 10. Результат работы алгоритма R = 10. При каком наименьшем N в результате работы алгоритма получится R = 1 824 648?
Ответ: 3303808
6. Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. Черепаха может выполнять две команды: Вперёд n (n – число) и Направо m (m – число). По команде Вперёд n Черепаха перемещается вперёд на n условных единиц. По команде Направо m Черепаха поворачивается на месте на m градусов по часовой стрелке, при этом соответственно меняется направление дальнейшего движения. В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат). Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что заданная последовательность из S команд повторится k раз. Черепаха выполнила следующую программу: Повтори 3 [Вперёд 20 Направо 90 Вперёд 4 Направо 90] Повтори 3 [Вперёд 6 Направо 90 Вперёд 13 Направо 90] Полученный при выполнении этой программы рисунок можно рассматривать как набор непересекающихся прямоугольников. Определите наибольшее количество точек с целочисленными координатами, находящихся внутри одного из этих прямоугольников. Точки, находящиеся на линиях, не учитывать.
Ответ: 40
7. Книгу объёмом 2 Мбайт записали как аудиокнигу. Запись велась в формате стерео (2 канала) с частотой 36 кГц и разрешением 24 бит. За одну минуту записывалось в среднем 1,5 Кбайт текста. Записанный аудиофайл сжали и разделили на 270 фрагментов со средним размером 20 Мбайт. Определите, на сколько процентов уменьшился размер файла при сжатии. Заголовки и другую служебную информацию не учитывать. В ответе запишите число – округлённый до целого процент сжатия.
8. Сколько существует натуральных чисел, не превышающих 738 000 000, запись которых в системе счисления с основанием 14 содержит ровно 8 различных цифр?
9. В каждой строке электронной таблицы записаны восемь натуральных чисел, разбитых на две четвёрки. Первая четвёрка занимает столбцы с 1 по 4, вторая – с 5 по 8. Определите количество строк таблицы, для которых одновременно выполнены все следующие условия: – минимальное число строки встречается в ней ровно один раз; – минимальное число строки находится в первой четвёрке; – среднее арифметическое чисел первой четвёрки больше среднего арифметического чисел второй четвёрки.
10. Повесть братьев Стругацких «Понедельник начинается в субботу» состоит из трёх историй. Один из персонажей носит имя Кристобаль. Определите, сколько раз встречается это имя в любом падеже в каждой из историй. В ответе запишите наибольшее из найденных чисел.
11. Предприятие выпускает партии изделий. Каждая партия получает уникальный код из 17 символов. Каждый символ кода может быть любой строчной или заглавной латинской буквой. Все изделия в партии получают последовательные номера от 1 до общего числа изделий в партии. Запись о каждом изделии заносится в информационную систему. Запись содержит код изделия и некоторую дополнительную информацию. Код изделия состоит из кода партии и номера изделия в партии. Для записи кода партии используется посимвольное кодирование, каждый символ кодируется одинаковым минимально возможным количеством битов. Номер изделия записывается как двоичное целое число, для записи каждого номера используется одинаковое минимально возможное количество битов. Для записи кода изделия в целом используется минимально возможное целое количество байтов. Для записи дополнительной информации о каждом изделии требуется 50 байт. Известно, что для хранения информации обо всех изделиях одной партии используется не более 90 Кбайт. Какое наибольшее количество изделий может быть в партии?
12. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. Дана программа для Редактора: НАЧАЛО ПОКА нашлось (111) ИЛИ нашлось (22) заменить (111, 2) заменить (222, 1) заменить (221, 1) заменить (122, 1) заменить (22, 2) КОНЕЦ ПОКА КОНЕЦ Определите, сколько различных строк, содержащих ровно 4 единицы, может получиться в результате применения этой программы к строкам, состоящим только из единиц и двоек.
13. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места – нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0. Известно, что в двоичной записи адреса сети, к которой принадлежит узел 169.25.132.59, содержится столько же единиц, сколько нулей в двоичной записи маски этой сети. Сколько адресов, в двоичной записи которых ровно 11 единиц, содержится в этой сети?
14. В системе счисления с основанием p выполняется равенство y18x + wy98 = xxz4y. Буквами x, y, z и w обозначены некоторые цифры из алфавита системы счисления с основанием p. Определите значение числа xyzwp и запишите это значение в десятичной системе счисления.
15. Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14&5 = 11102&01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула (x&6280 > 0 \/ x&3394 > 0) → (x&10828 = 0 → x&А > 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
16. Обозначим через a%b остаток от деления натурального числа a на натуральное число b, а через a//b – целую часть от деления a на b. Функция F(n), где n – неотрицательное целое число, задана следующими соотношениями: F(n) = 0, если n = 0; F(n) = F(n//4) + n%4, если n>0 и n%4 < 2; F(n) = F(n//4) + n%4 – 1, если n%4 ≥ 2. Найдите минимальное n, для которого F(n) = 27, а F(n + 1) = 20.
17. Файл содержит последовательность натуральных чисел, не превышающих 100 000. Назовём тройкой три идущих подряд элемента последовательности. Определите количество троек, для которых выполняются следующие условия: – в тройке есть четырёхзначные числа; – в тройке не более одного числа, у которого остаток от деления на 5 равен остатку от деления на 5 максимального элемента всей последовательности; – в тройке не менее двух чисел, у которых остаток от деления на 7 равен остатку от деления на 7 минимального элемента всей последовательности. В ответе запишите два числа: сначала количество найденных троек, затем максимальную величину суммы элементов этих троек.
18. Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя. Для вашего удобства такие клетки выделены тёмным фоном. В остальных клетках записаны положительные числа. За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Клетка, из которой робот не может сделать допустимого хода (справа и сверху находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток. В начальный момент робот обладает некоторым запасом энергии. Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки. Задание 2. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом. Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.
19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. Если количество камней в куче делится на целое k (2 ≤ k ≤ 9), то игрок может убрать из кучи k камней. Если количество камней в куче не делится ни на одно из указанных чисел, игрок убирает один камень, после чего выполняет ход по описанному выше правилу. Например, если в куче 12 камней, то за один ход можно убрать 2, 3, 4 или 6 камней, а если в куче 11 камней, то игрок за один ход сначала убирает один камень (остаётся 10), а затем убирает 2 или 5 камней. Игра завершается, когда количество камней в куче становится не более 9. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 9 или меньше камней. В начале игры в куче было S камней, S > 9. Укажите минимальное значение S, при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим первым ходом.
20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. В ответе запишите найденные значения в порядке возрастания.
21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом.
22. В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или нескольких других процессов – поставщиков данных. Если зависимый процесс получает данные от других процессов (поставщиков данных), то выполнение зависимого процесса не может начаться раньше завершения всех процессовпоставщиков. Длительность процесса не зависит от других параллельно выполняемых процессов, приостановка выполнения процесса не допускается. В таблице представлены идентификатор (ID) каждого процесса, его длительность в мс и ID поставщиков данных для зависимых процессов. Для независимых процессов в качестве ID поставщика данных указан 0. В момент, когда процесс готов к запуску, он ставится в очередь. Если несколько процессов оказываются готовы к запуску одновременно, первым ставится в очередь тот процесс, у которого меньше ID. Одновременно может выполняться не более 3 процессов. Если в какой-то момент в системе работает менее 3 процессов, то при наличии готовых к запуску процессов выбирается и запускается первый процесс из очереди. За какое время будут выполнены все процессы? В ответе напишите число – требуемое время в мс.
23. Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены буквами. A. Вычти 2 B. Если число кратно 3, Раздели на 3, Иначе Вычти 4 Программа для исполнителя – это последовательность команд. Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы BAB при исходном числе 99 траектория будет состоять из чисел 33, 31, 27. Сколько существует программ, которые преобразуют исходное число 38 в число 6 и при этом траектория вычислений не содержит числа 10?
24. Текстовый файл содержит строку, состоящую из цифр от 1 до 9, знаков операций «+», «–» и «*» (сложение, вычитание и умножение) и заглавных латинских букв A, B, C, D. Назовём правильной суммой строку, которая содержит последовательность из одного или более десятичных чисел, в которой между каждыми двумя соседними числами стоит ровно один знак «+» или «–» и нет других знаков. Примеры правильных сумм: «23», «115+6», 1980+12–123–51+3». Назовём результатом правильной суммы число, которое получится при выполнении записанных в соответствующей строке действий. Например, результат правильной суммы «2+3» – число 5, а результат правильной суммы «1+2–8+3» – число –2. Найдите в данной строке расположенную непосредственно после буквы B правильную сумму, содержащую наибольшее число символов, и вычислите её результат. Если несколько правильных сумм содержат одинаковое наибольшее число символов, выберите ту, которая имеет больший результат. В ответе запишите результат найденной суммы. Гарантируется, что ответ не превышает 2·109
25. Маска числа – это последовательность цифр, в которой могут встречаться специальные символы «?» и «*». Символ «?» означает ровно одну произвольную цифру, символ «*» означает произвольную (в том числе пустую) последовательность цифр. Например, маске 123*4?5 соответствуют числа 123405 и 12376415. Найдите все натуральные числа, не превышающие 109 , которые соответствуют маске 6?1*89*3 и при этом без остатка делятся на 9341. В ответе запишите все найденные числа в порядке возрастания.
26. При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной. При анализе результатов эксперимента рассматривают изолированные точки. Точка называется изолированной, если эта точка светлая (независимо от того, сколько частиц в неё попало), а другие светлые точки в том же ряду либо отсутствуют, либо находятся на расстоянии более 1000. Вам необходимо по заданному протоколу определить наибольшее количество изолированных точек, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер. Входные данные Первая строка входного файла содержит целое число N – общее количество частиц, попавших на экран. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду. В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем – номер ряда, в котором это количество встречается.
27. В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям. По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров – кругов радиуса не более 3 единиц – так, что каждая точка попадает ровно в один кластер. Центром кластера считается та из входящих в него точек, для которой минимально среднее из расстояний до всех остальных точек кластера. При этом расстояние вычисляется по стандартной формуле расстояния между точками на евклидовой плоскости. Радиусом кластера считается максимальное из расстояний от центра до остальных точек кластера.
Обработка результатов эксперимента включает следующие шаги: 1) кластер, содержащий наибольшее число точек, исключается; 2) определяются центры и радиусы всех оставшихся кластеров; 3) вычисляется средний радиус оставшихся кластеров. В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты X и Y точки, соответствующей одному испытанию. По данному протоколу надо определить средний радиус всех кластеров за исключением содержащего наибольшее число точек. Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. По данным каждого из представленных файлов определите средний радиус по описанным выше правилам. В ответе запишите два числа: сначала средний радиус для файла A, затем для файла B. В качестве значения указывайте целую часть от умножения найденного числового значения на 10 000.