Информатика

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

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

ρ = m / V.

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

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

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

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

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

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

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

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

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

\(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.

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 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: независимый процесс длительностью d выполняется на миллисекундах 1, 2, …, d, а зависимый может начаться со следующей миллисекунды после завершения всех предшественников.

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

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

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

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

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

Для выполнения ходов у каждого игрока имеется неограниченное количество камней. Игра завершается, когда в куче становится не менее 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)? В ответе запишите целое число.

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n: в двоичной записи результата единица стоит только в тех разрядах, в которых единицы есть у обоих операндов. Например, 6 & 3 = 2, поскольку 110₂ & 011₂ = 010₂.

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

((x & 77) ≠ 0) → (((x & 37) = 0) → ((x & A) ≠ 0))

тождественно истинно, то есть принимает значение 1 при любом целом неотрицательном x? В ответе запишите A в десятичной системе счисления.

Значение арифметического выражения

5⁸⁰ + 5³⁰ − x,

где x — целое положительное число, не превышающее 1000, записали в системе счисления с основанием 5 без ведущих нулей.

Определите наибольшее значение x, при котором в полученной записи содержится ровно 51 цифра 0. В ответе запишите найденное значение x в десятичной системе счисления.

Исполнитель преобразует число, записанное на экране. У исполнителя две команды, обозначенные латинскими буквами:

Команда "Прибавить 1" увеличивает число на экране на 1. Команда "Умножить на 2" применяется только тогда, когда число на экране нечётно, и увеличивает это число в два раза. К чётному числу команда B неприменима.

Программа для исполнителя — последовательность допустимых команд. Траектория вычислений — последовательность результатов выполнения всех команд программы. Например, программа BA при исходном числе 3 имеет траекторию 6, 7.

Сколько существует программ, для которых при исходном числе 2 результатом является число 31? В ответе запишите целое число.