Банк заданий
ЕГЭ по информатике

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

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

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

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

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

Файлы к заданию: https://docs.google.com/spreadsheets/d/1RVvaBc1F0oFSCBc9Q8TXS5X-9_VlWHFK/edit?usp=drive_link&ouid=109918313430926500890&rtpof=true&sd=true

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

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

В первой строке входного файла находится натуральное число $N$ ($N ≤ 1000$) – количество заявок на проведение мероприятий. Следующие $N$ строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440. 

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

Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).

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

5

10 150

100 120

131 170

150 180

120 130

При таких исходных данных можно провести максимум два мероприятия, например, мероприятия по заявкам 2 и 4. Максимальный перерыв между двумя последними мероприятиями составит 30 мин., если состоятся мероприятия по заявкам 2 и 5.

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

Файл к заданию: https://drive.google.com/file/d/1PXbn5y0nEKR1-QHLe8FYdL8CTwSz7Zlt/view?usp=drive_link

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.

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

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $A(x_{1},y_{1})$ и $B(x_{2},y_{2})$ вычисляется по формуле:

$d(A,B)=\sqrt{(x_{2}−x_{1})^{2}+(y_{2}−y_{1})^{2}}$

В файле A хранятся данные о звёздах двух кластеров, где $H = 4$, $W=4$ для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров, где $H = 5$, $W = 5$ для каждого кластера. Известно, что количество звёзд не превышает 10000.

Структура хранения информации о звездах в файле B аналогична файлу А. 

Известно, что в файле В имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем вычислите два числа: $P_{x}$​ -  расстояние по оси абcцисс между центрами кластеров и $P_{y}$​ - расстояние по оси ординат между центрами кластеров.

Для файла Б определите координаты центра каждого кластера, затем вычислите два числа: $Q_{x}$​ - расстояние между центрами кластеров с минимальным и минимальным количеством точек, и $Q_{y}$ - минимальное расстояние от центра кластера до любой точки другого кластера.

Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке - сначала целую часть абсолютной величины произведения $P_{x} * 10\space000$​, затем целую часть абсолютной величины произведения $P_{y} * 10\space000$; во второй строке - сначала целую часть абсолютной величины произведения $Q_{x} * 10\space000$​, затем целую часть абсолютной величины произведения $Q_{y} * 10\space000$.

Возможные данные одного из файлов проиллюстрированы графиком.

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

Файл А к заданию: https://drive.google.com/file/d/18mKzx7tt3yZVr75QjG4JD82uphZksHuC/view?usp=drive_link

Файл В к заданию: https://drive.google.com/file/d/1TaGUB5zv27BaMbvSTRat98G2-BrK3ePb/view?usp=drive_link

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

– символ «?» означает ровно одну произвольную цифру;

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

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих $10^{10}$, найдите все числа, соответствующие маске 1*2715?6, делящиеся на 2024 без остатка.

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

Количество строк в таблице для ответа избыточно.

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

$(x+3*y<A)∨(y>x)∨(x>80)$

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