Экзамены и диагностики

10 224 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.

Все четырёхбуквенные слова, составленные из букв С, Б, В, Ж, П, Ц, З, И, записаны в алфавитном порядке и пронумерованы начиная с 1. Буквы в словах могут повторяться.

Вот начало списка:

1. ББББ
2. БББВ
3. БББЖ
4. БББЗ
5. БББИ
6. БББП
7. БББС
8. БББЦ
…

Сколько существует слов в списке с чётными номерами, которые начинаются с букв СВ?

Примечание. Слово — последовательность идущих подряд букв, не обязательно осмысленная.

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 753 на 465 пикселей. Для кодирования цвета каждого пикселя используется одинаковое и минимально возможное количество бит.

Коды пикселей записываются в файл один за другим без промежутков. Сжатие данных не производится. Служебная информация и заголовки файлов при расчёте объёма не учитываются.

При передаче снимки группируются в пакеты по 128 фотографий. Минимальный объём памяти, необходимый для хранения одного полного пакета снимков, составляет более 97 792 Кбайт.

Какое минимальное количество цветов можно использовать в изображениях? В ответе запишите только число. Считать, что 1 Кбайт = 210 байт, 1 байт = 8 бит.

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен.

При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения.

У исполнителя существует 6 команд:

  • Поднять хвост — переход к перемещению без рисования;
  • Опустить хвост — переход в режим рисования;
  • Вперёд n, где n — целое число, — перемещение на n единиц в том направлении, куда указывает голова;
  • Назад n, где n — целое число, — перемещение на n единиц в противоположном голове направлении;
  • Направо m, где m — целое число, — поворот на m градусов по часовой стрелке;
  • Налево m, где m — целое число, — поворот на m градусов против часовой стрелки.

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

Черепахе был дан для исполнения следующий алгоритм:

Повтори 2 [Вперёд 18 Направо 90 Вперёд 22 Направо 90]
Поднять хвост
Вперёд 7
Направо 90
Вперёд 17
Налево 90
Опустить хвост
Повтори 2 [Вперёд 23 Направо 90 Вперёд 41 Направо 90]

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

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

  1. Строится двоичная запись числа N без ведущих нулей.
  2. Справа к этой записи дописывается 0, если количество единиц в записи чётно, и 1, если количество единиц нечётно.
  3. К полученной записи ещё раз применяется то же правило: подсчитывается количество единиц уже в полученной записи и справа дописывается соответствующая цифра.
  4. Из полученной записи удаляются две крайние левые цифры. Оставшаяся запись является двоичной записью числа R. Ведущие нули, если они появились, на числовое значение R не влияют.
  5. Результат переводится в десятичную систему счисления.

Например, для исходного числа N = 1110 = 10112 после первого дописывания получается 101112, после второго — 1011102. После удаления двух крайних левых цифр остаётся 11102 = 1410.

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

По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, Ж, З, К и Л. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано.

Кодовые слова для некоторых букв известны:

БукваКодовое слово
К01011
Л01111
Ж1010
Г1100
Б10011
В10001
А01110
Е00010

Для букв Д и З кодовые слова ещё не определены. Укажите кратчайшее кодовое слово для буквы Д, при котором можно выбрать кодовое слово для буквы З так, чтобы весь код удовлетворял условию Фано.

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

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Задание выполняется с использованием прилагаемых файлов.

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

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

ID операцииДата покупкиВремя покупкиКод спектакляID тарифаДата спектакляБилеты для взрослых без льготЛьготные билеты для взрослыхДетские билеты

В трёх последних столбцах указано количество купленных билетов соответствующей категории.

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

ID тарифаНазвание тарифаСтоимость билета для взрослого без льгот, руб.Стоимость льготного билета для взрослого, руб.Стоимость детского билета, руб.

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

Код спектакляНазваниеАвторРежиссёрЖанр

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

Продажа_билетовID операцииКод спектакляID тарифаСпектаклиКод спектакляЦеныID тарифа∞1∞1

Используя информацию из приведённой базы данных, определите общую сумму в рублях, вырученную за детские билеты, проданные по тарифу «утренний спектакль зимний сезон» на все комедии А. П. Чехова, состоявшиеся в период с 17 февраля по 21 октября 2024 года включительно.

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

Миша заполнял таблицу истинности логической функции F

F = (x → y) ∧ (z ∨ ¬w) ∧ (y → ¬(x ≡ w)),

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

F
10001
10101
11100

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

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

Например, функция задана выражением ¬x ∨ y, а фрагмент таблицы имеет следующий вид.

¬x ∨ y
010

В этом примере первому столбцу соответствует переменная y, второму — x. Ответ к примеру: yx. Пример не относится к исходной функции F.

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


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

Определите, какова сумма протяжённостей дорог из пункта F в пункт C и из пункта H в пункт A. В ответе запишите целое число.

Задание выполняется с использованием прилагаемых файлов.

В лаборатории исследуют образцы материалов. Для каждого образца известны координаты x и y его положения на плоскости, масса m, объём V и тип внутреннего строения. Тип обозначается одним из римских чисел от I до VII. Масса и объём положительны; все значения даны в согласованных единицах измерения.

Плотность образца вычисляется по формуле:

ρ = m / V.

Учёный решил разбить все образцы на четыре непересекающихся непустых кластера по значениям плотности. Модуль разности плотностей любых двух образцов одного кластера не должен превышать 0,4. Гарантируется, что такое разбиение существует и единственно.

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

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

В каждой строке файла записаны пять значений: x, y, m, V и тип образца. Значения разделены пробелами и/или символами табуляции. Десятичный разделитель — точка. Заголовка и строки с количеством образцов нет.

Количество строк не превышает 10 000. Абсолютные значения всех числовых полей не превышают 100. В каждом кластере есть не менее двух образцов типа IV. Порядок строк не определяет принадлежность образцов кластерам.

Выполните задание

Для каждого кластера определите его центр. Затем найдите два числа:

  • P — наибольшее евклидово расстояние между двумя образцами типа IV, принадлежащими одному и тому же кластеру; максимум выбирается среди всех четырёх кластеров;
  • Q — наименьшая плотность центра среди центров четырёх кластеров.

Евклидово расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле:

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

В ответе запишите в одной строке два целых числа: сначала целую часть произведения P · 10 000, затем целую часть произведения Q · 10 000. Округлять до ближайшего целого не нужно. Для выполнения задания следует написать программу.

Типовой пример организации данных
1.20 -2.50 5.00000 2 IV
3.40 1.10 7.62000 3 II
-2.00 4.20 16.30000 2 IV

Плотность образца из первой строки примера равна 5 / 2 = 2,5. Пример показывает только формат записи; для решения используйте весь прилагаемый файл.



Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки. 
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.

Задание выполняется с использованием прилагаемых файлов.

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

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

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

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

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

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

В первой строке файла записаны два натуральных числа: N — количество заявок, не превышающее 1 000 000, и K — число ячеек, не превышающее 30. Каждая из следующих N строк содержит три натуральных числа: ID заявки, время прибытия и время освобождения. Все эти числа не превышают 1 000 000; время освобождения строго больше времени прибытия. Время задано в секундах от общего начала отсчёта.

Идентификаторы заявок уникальны. Строки файла расположены в произвольном порядке. Числа в строке разделены пробелами. Гарантируется, что хотя бы одна заявка будет принята.

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

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

Типовой пример организации данных
6 2
1 1 5
2 2 6
3 3 4
4 5 10
5 6 8
6 8 12

В примере заявка 3 отклоняется. Заявки 1 и 4 занимают ячейку 1 суммарно на 9 секунд, а заявки 2, 5 и 6 — ячейку 2 суммарно на 10 секунд. Ответ к примеру: 5 2. Пример имеет иллюстративный характер; для решения используйте прилагаемый файл.


Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки. 
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.

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

  • символ «?» обозначает ровно одну произвольную цифру;
  • символ «*» обозначает любую последовательность цифр произвольной длины, в том числе пустую последовательность.

Например, маске 12*3? соответствуют числа 1230 и 120035. В последнем случае «*» заменяет последовательность 00, а «?» — цифру 5.

Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 4?27?16*3 и делящиеся на 2027 без остатка.

В ответе запишите найденные числа в порядке возрастания; после каждого укажите результат его деления на 2027. Каждая пара образует строку таблицы ответа.


Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Все пары чисел записываются построчно: первая пара в первую строку, вторая - во вторую и т.д. В первой колонке записывается найденное число, во второй - результат его деления на 2027.

При решении вне станции ответ записывается построчно, числа в паре разделяются одним пробелом.

Задание выполняется с использованием прилагаемых файлов.

Текстовый файл содержит одну строку, состоящую из заглавных латинских букв A, B, C, D, E, F, G и T. Количество символов строки не превышает 10 000 000.

Определите минимальное количество символов в непрерывной последовательности, которая содержит ровно 100 букв T и не содержит подстроки AB, то есть буквы A, непосредственно за которой следует B. Гарантируется, что подходящая последовательность существует.

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

Задание выполняется с использованием прилагаемых файлов.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке записаны два натуральных числа L, M и положительное вещественное число W. Такая строка описывает ребро, ведущее из вершины L в вершину M и имеющее вес W.

Количество строк равно количеству рёбер. Между одной и той же парой вершин нет нескольких рёбер одного направления. Строки с количеством вершин или рёбер в начале файла нет. Номера вершин могут идти не подряд; их числовой порядок не задаёт направление рёбер.

Длина пути равна сумме весов входящих в него рёбер. Найдите целую часть длины длиннейшего пути из вершины 11 в вершину 907. Существование хотя бы одного такого пути гарантируется.

Номера вершин не превышают 1000, вес ребра не превышает 10 000. Количество строк файла не превышает 200. Числа в строках разделены пробелами и/или символами табуляции. Десятичный разделитель — точка. Для выполнения задания следует написать программу.

Типовой пример организации данных
1 2 2.5
1 3 4.0
2 4 6.0
3 4 3.5
2 3 1.0

Для этого примера длиннейший путь из вершины 1 в вершину 4 — 1–2–4, его длина равна 8,5. Ответ к примеру — 8. Пример поясняет формат и не относится к вершинам основного задания.

Задание выполняется с использованием прилагаемых файлов.

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

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

В первом столбце таблицы указан ID процесса, во втором — длительность в миллисекундах, в третьем — ID предшественников, разделённые символом «;». Значение 0 означает отсутствие предшественников.

Каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.

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

Типовой пример организации данных
ID процесса B Время выполнения процесса B (мс) ID процесса (ов) A
1 3 0
2 4 1
3 2 2; 4
4 5 0

В примере процесс 2 выполняется на миллисекундах 4–7, а процесс 3 — на миллисекундах 8–9. Пример имеет иллюстративный характер; для решения используйте прилагаемый файл.

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

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

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

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

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

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



Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки. 
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит одна куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

  • добавить в кучу два камня;
  • добавить в кучу пять камней;
  • увеличить количество камней в куче в два раза.

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

В начальный момент в куче было S камней, где 1 ≤ S ≤ 102. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Задание выполняется с использованием прилагаемых файлов.

Квадрат разлинован на N × N клеток, где 1 < N < 30. Исполнитель Робот начинает движение в левой верхней клетке и должен попасть в правую нижнюю клетку.

За одно перемещение Робот выполняет одну из двух команд: «вправо» — переходит в соседнюю клетку справа, или «вниз» — переходит в соседнюю клетку снизу. Квадрат ограничен внешними стенами. Между соседними клетками могут находиться внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском в каждой клетке лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает её монету. Это относится и к начальной, и к конечной клетке маршрута.

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

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



Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки. 
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.

Задание выполняется с использованием прилагаемых файлов.

В файле содержится последовательность натуральных чисел. Её элементы принимают значения от 1 до 100 000 включительно. Каждое число записано в отдельной строке; заголовка нет.

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

Под парой понимаются два идущих подряд элемента последовательности. Среднее арифметическое равно сумме всех элементов, делённой на их количество. Гарантируется, что подходящая пара существует.

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



Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки. 
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.

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

  • F(1) = 3;
  • F(n) = F(n − 1) + n, если n > 1 и n чётно;
  • F(n) = F(n − 1) + 2n, если n > 1 и n нечётно.

Чему равно значение выражения F(2026) − F(2022)? В ответе запишите целое число.

Поделиться
Класснуть