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

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

- убрать из кучи 3 камня;

- убрать из кучи 7 камней;

- уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).

Например, из кучи в 20 камней за один ход можно получить кучу из 17, 13 или 5 камней.

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

В начальный момент в куче было $S$ камней; $S > 15$.

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

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

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

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

Определите количество процессов, которые начинаются и заканчиваются во временном промежутке [4; 18] мс, при условии, что все независимые друг от друга процессы могут выполняться параллельно и никакие задержки не допускаются.

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

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.

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

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

A. Вычесть 1

B. Вычесть 3

C. Найти целую часть от деления на 2

Программа для исполнителя - это последовательность команд.

Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит числа 9 и содержит 12?

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

Например, для программы СВА при исходном числе 13 траектория состоит из чисел 6, 3, 2.

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, оканчивающихся подстрокой $2025$, среди которых буква $Y$ встречается не менее 140 раз, а подстрока $2025$ содержится ровно 50 раз.

В ответе запишите число – количество символов в найденной последовательности.

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

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

Пусть $M$ – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение $M$ считается равным нулю.

Напишите программу, которая перебирает целые числа, большие 7800000, в порядке возрастания и ищет среди них такие, для которых $M$ оканчивается на 63 и кратно общему количеству различных простых делителей числа. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения $M$.

Например, для числа 14 $M = 2 + 7 = 9$.

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $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 = 6.5$, $W=4.5$ для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

Для файла А определите координаты центра каждого кластера, затем вычислите два числа: $A_1$​ -  в кластере с наименьшим количеством точек число точек, абсцисса которых не больше абсциссы центра этого кластера, и $A_2$​ - расстояние между центрами кластеров.

Для файла B определите координаты центра каждого кластера, затем вычислите два числа: $B_1$​ - в среднем по количеству точек кластере число точек, находящихся внутри квадрата с центром в центре этого же кластера, сторонами, параллельными координатным осям и длиной 2.0, и $B_2$ - расстояние по оси ординат между центрами кластеров с наименьшим и наибольшим количеством точек.

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

В ответе запишите четыре числа: в первой строке - сначала $A_1$​, затем целую часть произведения $A_2 * 10000$; во второй строке - сначала $B_1$​, затем целую часть произведения $B_2 * 10000$.

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

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

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

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

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

Определите, какова протяжённость дороги из пункта В в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.

Миша заполнял таблицу истинности функции $F=((z → x) → (x ≡ y)) \lor \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных $w, x, y, z$.

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

В ответе напишите буквы $x, y, z, w$ в том порядке, в котором идут соответствующие им столбцы (сначала - буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.

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

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

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

На рисунке приведена схема указанной базы данных.

Используя информацию из приведённой базы данных, определите общий вес (в кг) крахмала картофельного, поступившего в магазины Октябрьского района за период с 1 по 8 июня включительно.

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

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

Откройте файл электронной таблицы, содержащей в каждой строке четыре натуральных числа. Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия:

– наибольшее из четырёх чисел меньше суммы трёх других;

– четыре числа нельзя разбить на две пары чисел с равными суммами.

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

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

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

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

Квадрат разлинован на $N * N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

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

В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

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

В ответе укажите два числа - сначала максимальную сумму, затем минимальную.

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

Пример входных данных

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

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

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

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

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

Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых пара символов $BC$ (в указанном порядке) встречается ровно 190 раз.

В ответе запишите число – количество символов в найденной последовательности.

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

Файл к заданию: https://drive.google.com/file/d/11eE9jGaKPwyH-lVj7AjxSepRr8K8zrjj/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}}$.

Каждая звезда помимо координат на плоской карте характеризуется своим спектральным классом и классом светимости. Спектральный класс определяет цвет (который связан с температурой звезды) согласно таблице. Каждый из спектральных классов, в свою очередь, делится на подклассы от 0 до 9 в порядке уменьшения температуры. Обозначение подкласса ставится после обозначения спектрального класса (например, B2). Класс светимости звезды обозначим римскими цифрами от I до VII.

В файле A хранятся данные о звёздах двух кластеров, где $H=6.0$, $W=5.5$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Далее в той же строке для звёзд классов светимости I–VI указываются спектральный класс, подкласс и класс светимости. Обозначения классов ничем не разделяются. Для звёзд класса светимости VII (Белый карлик) обозначения спектрального класса и подкласса в файле не указываются. Известно, что количество точек не превышает 2000.

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

Для файла А определите координаты центра каждого кластера, затем найдите два числа: $A_x$ и $A_y$ - абсциссу и ординату красного гиганта, ближайшего к центру кластера, который содержит наименьшее количество точек.

Для файла В определите координаты центра каждого кластера, затем найдите два числа: $B_1$ - расстояние между центрами кластеров с наименьшим и наибольшим количеством оранжевых гигантов, и $B_2$ - наибольшее расстояние между жёлтыми карликами одного кластера.

В ответе запишите четыре числа: в первой строке - сначала целую часть абсолютного значения произведения $A_x * 10000$ , затем целую часть абсолютного значения произведения $A_y * 10000$ ; во второй строке - сначала целую часть произведения $B_1 * 10000$ , затем целую часть произведения $B_2 * 10000$ .

Пример организации данных в одном из исходных файлов для случая четырёх звёзд

5,01788 8,32466 G2V

4,289251 6,955186 VII

4,619358 5,524697 B7V

6,91934 20,425391 G2V

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

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

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

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

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

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

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

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

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

На рисунке приведена схема указанной базы данных.

Используя информацию из приведённой базы данных, определите общий объём (в литрах) всех видов ополаскивателя для белья, полученного магазинами, расположенными на улице Лермонтова, за период с 21 по 29 сентября включительно.

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

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

Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Определите количество строк таблицы, для которых выполнены оба условия:

- в строке есть ровно два числа, каждое из которых повторяется дважды, остальные числа различны;

- сумма всех повторяющихся чисел строки больше суммы всех её неповторяющихся чисел.

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

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

С помощью текстового редактора определите, сколько раз встречается отдельное слово «я» или «Я» (в именительном падеже) в тексте глав X и XI первой части тома 2 романа Л.Н. Толстого «Война и мир». В ответе запишите только число.

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

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

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

Квадрат разлинован на $N * N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

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

В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

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

В ответе укажите два числа - сначала максимальную сумму, затем минимальную.

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

Пример входных данных

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

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

Определите максимальное количество процессов, которые параллельно выполняются на 26-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.

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

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.

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

Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$. Определите в прилагаемом файле минимальное количество идущих подряд символов, среди которых тройка букв $ABC$ (в указанном порядке) встречается ровно 110 раз, при этом искомая последовательность заканчивается буквой $C$.

В ответе запишите число - количество символов в найденной последовательности.

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

Файл к заданию: https://drive.google.com/file/d/14Ca4DlbMtSpe-3bwzh3_y5qheID40pJa/view?usp=drive_link

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные - в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём, переданных на сервер с одного клиентского устройства данных, не превышающий 150000 Кбайт, а также сумму объёмов (в Кбайт) двух последних по времени резервных копий специального раздела, выполненных не позднее 11:59:59.

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: N(N< 1 000 000) - количество строк в журнале и $K$ ($K$ < 1 000 000) - вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды), а также два натуральных числа: $C$ ($C$ < 1 000 000) - идентификатор клиентского устройства и $S$ ($S$ < $K$) - объём данных запроса в Кбайт.

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

В ответе запишите два числа: сначала наибольший суммарный объём данных с одного клиентского устройства, не превышающий 150000 Кбайт, а затем сумму объёмов (в Кбайт) двух последних по времени резервных копий специального раздела, выполненных не позднее 11:59:59.

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

8 140000

01:01:01 101 20000

03:03:03 202 110000

05:05:05 101 90000

07:07:07 303 62000

10:10:10 101 48000

15:15:15 202 12000

21:21:21 303 120000

23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в 5:05:05 (в объёме 130000 Кбайт), в 07:07:07 (в объёме 90000 Кбайт), в 21:21:21 (в объёме 122000 Кбайт) и в 23:23:23 (в объёме 120000 Кбайт).

Всего на сервер должно быть передано 596000 Кбайт данных: 158000, 122000, 182000 и 134000 Кбайт от клиента идентификатором 101, 202, 303 404 соответственно. Ответ для приведённого примера: 134000 220000.

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $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}}$.

Каждая звезда помимо координат на плоской карте характеризуется своим спектральным классом и классом светимости. Спектральный класс определяет цвет (который связан с температурой звезды) согласно таблице. Каждый из спектральных классов, в свою очередь, делится на подклассы от 0 до 9 в порядке уменьшения температуры. Обозначение подкласса ставится после обозначения спектрального класса (например, B2). Класс светимости звезды обозначим римскими цифрами от I до VII.

В файле A хранятся данные о звёздах двух кластеров, где $H=6.0$, $W=5.5$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Далее в той же строке для звёзд классов светимости I–VI указываются спектральный класс, подкласс и класс светимости. Обозначения классов ничем не разделяются. Для звёзд класса светимости VII (Белый карлик) обозначения спектрального класса и подкласса в файле не указываются. Известно, что количество точек не превышает 2000.

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

Для файла А определите координаты центра каждого кластера, затем найдите два числа: $A_1$ - наименьшее расстояние от оранжевого субкарлика до центра кластера, которому он относится, и $A_2$ - суммарное расстояние от центров кластеров до точки с координатами $(-1.5; -1.5)$.

Для файла В определите координаты центра каждого кластера, затем найдите два числа: $B_1$ - абсциссу и $B_2$ - ординату центра кластера с наименьшим количеством оранжевых субкарликов.

В ответе запишите четыре числа: в первой строке - сначала целую часть произведения $A_1 * 10000$ , затем целую часть произведения $A_2 * 10000$ ; во второй строке - сначала целую часть абсолютного значения произведения $B_1 * 10000$ , затем целую часть абсолютного значения произведения $B_2 * 10000$ .

Пример организации данных в одном из исходных файлов для случая четырёх звёзд

5,01788 8,32466 G2V

4,289251 6,955186 VII

4,619358 5,524697 B7V

6,91934 20,425391 G2V

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

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

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