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

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

Каждая карта представляется в виде строки из двух символов, где первый символ означает ранг ("6", "7", "8", "9", "T", "J", "Q", "K", "A") карты, а второй символ означает масть ("S", "C", "D", "H"). Ранги перечислены в порядке возрастания старшинства (от 6 до "A", где "T" = 10, "J" = Валет, "Q" = Дама, "K" = Король, "A" = Туз). Карты в файле записываются слитно, без пробела между рангом и мастью.

Игроку на руках сдано $K$ карт, а соперник пошел $M$ картами. Чтобы успешно отбиться в партии, игроку необходимо под каждую карту атаки подобрать отдельную подходящую карту со своих рук по следующим правилам:

– Карта атаки покрывается либо более старшей картой той же масти, либо любой козырной картой (если карта атаки была не козырной).

– Если карта атаки сама является козырной, её можно отбить только более старшей козырной картой.

– Каждую карту с рук игрока можно использовать для защиты не более одного раза.

Определите наименьшее количество козырных карт, которое суммарно потратит игрок на отбой во всех успешно выигранных им партиях, а также максимально возможный суммарный числовой эквивалент рангов всех карт, использованных для защиты, в той из успешных партий, где на отбой потребовалось наибольшее количество козырных карт (ранги учитываются как числа: 6..9 = 6..9, "T" = 10, "J" = 11, "Q" = 12, "K" = 13, "A" = 14; если в партии существует несколько способов отбиться с минимальным расходом козырей, игрок выбирает тот способ, который максимизирует сумму рангов карт, сыгравших в защите).

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

В первой строке входного файла находится число $N$ — общее количество проводимых партий (натуральное число, не превышающее 20000). Далее следуют описания $N$ партий.

Описание каждой партии состоит из трёх строк:

– Первая строка содержит два целых числа и один символ: $K$ (количество карт на руках, $K \le 35$), $M$ (количество карт атаки, $M \le 10$) и $R$ (символ козырной масти этой партии: "S", "C", "D" или "H").

– Вторая строка содержит $K$ карт, записанных через пробел — карты на руках у игрока.

– Третья строка содержит $M$ карт, записанных через пробел — карты атаки соперника.

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

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

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

2

4 2 S

8S TS 7C AH

8S 9C

3 2 H

6H 7H 8S

TH AH

При таких исходных данных в первой партии игрок имеет карты 8S, TS, 7C, AH, козырь — S. Нужно отбить карты 8S и 9C. Чтобы отбить 9C с минимальным расходом козырей, игрок мог бы взять любой козырь, но не козырных карт масти 'C' старше 9 нет. Карта 8S отбивается более старшим козырем TS, а 9C отбивается козырем 8S. Отбой успешен. Из двух карт защиты обе являются козырями (потрачено 2 козыря). Сумма рангов защитных карт равна 8 + 10 = 18. Во второй партии у игрока нет карт, способных отбить TH и AH, партия проиграна. Всего успешных партий одна, минимальное сумма козырей — 2, и наибольшая сумма рангов защитных карт среди партий с максимальным числом козырей — 18.

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

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

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

Определите координаты центра каждого кластера, затем найдите два числа: $A_1$ – количество желтых карликов, расположенных на расстоянии не более 2,0 от центра кластера, который содержит наибольшее количество желтых карликов, и $A_2$ – расстояние между центрами кластеров.

В ответе запишите два числа: сначала $A_1$, затем целую часть произведения $A_2 \times 10 000$.

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

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/13dQUI_AUvHzfH-p1Fk-P8ayeVjvkopc9/view

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

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

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

В ответе запишите два числа: сначала целую часть произведения $A_1 \times 10000$, затем целую часть произведения $A_2 \times 10 000$.

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

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/1R5BovAx8NXycp4Q7JTUH6ebOEgQsU0Ij/view

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

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

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

В ответе запишите два числа: сначала целую часть произведения $A_1 \times 10000$, затем целую часть произведения $A_2 \times 10 000$.

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

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/1F6ZB9THglorCVbrE_oJtF9NZ6sqikh4G/view

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

В файле хранятся данные о морских обитателях из трёх различных экологических колоний (кластеров). Для каждой колонии параметры разброса координат составляют $H=6{,}0$, $W=5{,}5$. В каждой строке записана информация об одной зафиксированной точке: сначала координата $x$, затем координата $y$, а далее без разделителей указываются характеристики существа (например, E3I или VII). Обозначения характеристик в журнале исследователей записываются слитно. Для существ, относящихся к глубоководным планктофагам (обозначение V-II), температурный подкласс в базе данных не указывается (запись выглядит просто как VII). Известно, что общее количество записей в файле не превышает 10000.

Определите координаты центра каждого кластера, затем найдите два числа: $B_1$ – абсциссу и $B_2$ – ординату центра кластера с наибольшим соотношением количества хищников к количеству жертв (планктофаги и детритофаги).

В ответе запишите два числа: сначала целую часть абсолютного значения произведения $B_1 \times 10 000$, затем целую часть абсолютного значения произведения $B_2 \times 10 000$.

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

5.01788 8.32466 E3I

4.289251 6.955186 VII

4.619358 5.524697 M5III

6.91934 20.425391 E0II

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

Файл к заданию: https://drive.google.com/file/d/1Ea2Al5_OXNP10MPXi_mfI9i7GFMjRzQh/view

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

В файле хранятся данные о морских обитателях из двух различных экологических колоний (кластеров). Для каждой колонии параметры разброса координат составляют $H=5{,}0$, $W=4{,}5$. В каждой строке записана информация об одной зафиксированной точке: сначала координата $x$, затем координата $y$, а далее без разделителей указываются характеристики существа (например, E3I или VII). Обозначения характеристик в журнале исследователей записываются слитно. Для существ, относящихся к глубоководным планктофагам (обозначение V-II), температурный подкласс в базе данных не указывается (запись выглядит просто как VII). Известно, что общее количество записей в файле не превышает 2000.

Определите координаты центра каждого кластера, затем найдите два числа: $A_1$ – расстояние от начала координат до центра того кластера, в котором суммарная координата х всех его обитателей минимальна и $A_2$ – среднее арифметическое всех координат х всех планктофагов, обитающих в глубинной зоне.

В ответе запишите два числа: сначала целую часть произведения $A_1 \times 10 000$, целую часть абсолютного значения произведения $A_2 \times 10 000$.

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

5.01788 8.32466 E3I

4.289251 6.955186 VII

4.619358 5.524697 M5III

6.91934 20.425391 E0II

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

Файл к заданию: https://drive.google.com/file/d/12VEJjZlMV1Y7pFVJ7X2sbCG8HVFcfKTe/view

Лесной массив спроецирован на плоскость с декартовой системой координат. Лесничий решил провести кластеризацию полученных точек, являющихся местом произрастания деревьев, то есть разбить их множество на $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 лет, где возраст кодируется цифрой), типом древесины и прогнозируемым объемом получаемой древесины в килограммах. Породы деревьев кодируются латинскими буквами следующим образом. Каждая порода делится на возрастные категории от 0 до 9 в порядке увеличения возраста дерева. Обозначение категории ставится после буквы породы (например, C5). Тип древесины обозначается римскими цифрами от I до III.

Каждое дерево также имеет числовую характеристику — массу древесины в килограммах (целое число), которая записывается сразу после типа древесины. Для особо ценных березовых деревьев строительного типа (обозначение B-I) возрастная категория в базе данных не указывается, и запись породы выглядит просто как BI, после чего сразу указывается масса древесины (например, BI450). Все характеристики в журнале лесничего записываются слитно.

В файле хранятся данные о деревьях из двух различных лесополос (кластеров). Для каждого кластера параметры разброса координат составляют $H=5{,}0$, $W=4{,}5$. В каждой строке файла записана информация об одной зафиксированной точке: сначала координата $x$, затем координата $y$, а далее без разделителей указываются характеристики дерева (например, C3I250 или BII180). Известно, что общее количество записей в файле не превышает 2000.

Определите координаты центра каждого кластера, затем найдите два числа: $A_1$ – максимальное расстояние от хвойного дерева возрастной категории 5 с топливным типом древесины до центра того кластера, к которому оно относится, и $A_2$ – среднее арифметическое всех координат х всех лиственных деревьев строительного типа.

В ответе запишите два числа: сначала целую часть произведения $A_1 \times 10 000$, целую часть произведения $A_2 \times 10 000$.

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

5.01788 8.32466 C3I350

4.289251 6.955186 BI500

4.619358 5.524697 D5III120

6.91934 20.425391 C0II220

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

Файл к заданию: https://drive.google.com/file/d/1tcCn4JmuYdVf2XzxDlBHjvdItob8rW-f/view

Лесной массив спроецирован на плоскость с декартовой системой координат. Лесничий решил провести кластеризацию полученных точек, являющихся местом произрастания деревьев, то есть разбить их множество на $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 лет, где возраст кодируется цифрой), типом древесины и прогнозируемым объемом получаемой древесины в килограммах. Породы деревьев кодируются латинскими буквами следующим образом. Каждая порода делится на возрастные категории от 0 до 9 в порядке увеличения возраста дерева. Обозначение категории ставится после буквы породы (например, C5). Тип древесины обозначается римскими цифрами от I до III.

Каждое дерево также имеет числовую характеристику — массу древесины в килограммах (целое число), которая записывается сразу после типа древесины. Для особо ценных березовых деревьев строительного типа (обозначение B-I) возрастная категория в базе данных не указывается, и запись породы выглядит просто как BI, после чего сразу указывается масса древесины (например, BI450). Все характеристики в журнале лесничего записываются слитно.

В файле хранятся данные о деревьях из трёх различных лесополос (кластеров). Для каждого кластера параметры разброса координат составляют $H=6{,}0$, $W=5{,}5$. В каждой строке файла записана информация об одной зафиксированной точке: сначала координата $x$, затем координата $y$, а далее без разделителей указываются характеристики дерева (например, C3I250 или BII180). Известно, что общее количество записей в файле не превышает 10000.

Определите координаты центра каждого кластера, затем найдите два числа: $B_1$ – среднее значение абсцисс всех лиственных деревьев топливного типа в том кластере, где общее количество таких деревьев минимально (но больше нуля), и $B_2$ – расстояние от начала координат до центра того кластера, в котором суммарный прогнозируемый объем получаемой древесины всех его деревьев максимален.

В ответе запишите два числа: сначала целую часть абсолютного значения произведения $B_1 \times 10 000$, затем целую часть абсолютного значения произведения $B_2 \times 10 000$.

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

5.01788 8.32466 C3I350

4.289251 6.955186 BI500

4.619358 5.524697 D5III120

6.91934 20.425391 C0II220

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

Файл к заданию: https://drive.google.com/file/d/1HRV9O-2Rz5FR76n2-lZbkkVQaDa1qZwP/view

Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты $x$ и $y$, вектор скорости $V_x$ и $V_y$, масса $m$, а также количество выездов $K$ (среднее число зафиксированных событий).

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

Будем называть центром кластера такую его частицу, для которой сумма модулей разности кинетических энергий со всеми остальными частицами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.

В каждой строке текстового файла хранится информация об одной частице: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$ , масса $m$ и количество выездов $K$.

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

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютная величина каждого числового значения не превышает 100.0.

Известно, что все описанные в файле частицы подразделяются ровно на 3 кластера ($N = 3$) с $R = 2.0$ для каждого.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ – среднее арифметическое расстояний между всеми возможными парами центров всех трех кластеров, и $Q_2$ – расстояние от начала координат до центра того кластера, в котором разность между максимальным и минимальным количеством выездов $K$ из одной частицы максимальна.

В ответе запишите два числа: сначала целую часть произведения $Q_1 * 10000$, затем целую часть произведения $Q_2 * 10000$.

Для справки

Кинетическая энергия $E$ частицы массы $m$, обладающей скоростью $\vec{V}=(V_x; V_y)$ вычисляется по формуле:

$E = \frac{1}{2} * m * (V_x^2 + V_y^2)$.

Взвешенный путь $W_i$ от центра с координатами $(x_1; y_1)$ до частицы $i$ с координатами $(x_2; y_2)$ и количеством выездов $K_i$ вычисляется по формуле

$W_i = K_I \times \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

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

Три строки файла для трёх частиц:

0,67 -2,14 3,0 -4,0 0,2 50

3,14 7,22 3,2 4,3 0,7 10

1,33 5,56 0,0 5,22 0,456 3

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

Файл к заданию: https://drive.google.com/file/d/1McSId1lRnUhc6T6oz-G7CjmRntTp5Jq4/view

Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты $x$ и $y$, вектор скорости $V_x$ и $V_y$, масса $m$, а также количество выездов $K$ (среднее число зафиксированных событий).

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

Будем называть центром кластера такую его частицу, для которой сумма модулей разности кинетических энергий со всеми остальными частицами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.

В каждой строке текстового файла хранится информация об одной частице: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$ , масса $m$ и количество выездов $K$.

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

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютная величина каждого числового значения не превышает 100.0.

Известно, что все описанные в файле частицы подразделяются ровно на 3 кластера ($N = 3$) с $R = 2.0$ для каждого.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ – максимальное из евклидовых расстояний от начала координат $(0; 0)$ до центра каждого из трех кластеров, и $Q_2$ – суммарный взвешенный путь от центра того кластера, в котором находится частица с наименьшей массой $m$, до всех остальных частиц этого же кластера.

В ответе запишите два числа: сначала целую часть произведения $Q_1 * 10000$, затем целую часть произведения $Q_2 * 10000$.

Для справки

Кинетическая энергия $E$ частицы массы $m$, обладающей скоростью $\vec{V}=(V_x; V_y)$ вычисляется по формуле:

$E = \frac{1}{2} * m * (V_x^2 + V_y^2)$.

Взвешенный путь $W_i$ от центра с координатами $(x_1; y_1)$ до частицы $i$ с координатами $(x_2; y_2)$ и количеством выездов $K_i$ вычисляется по формуле

$W_i = K_I \times \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

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

Три строки файла для трёх частиц:

0,67 -2,14 3,0 -4,0 0,2 50

3,14 7,22 3,2 4,3 0,7 10

1,33 5,56 0,0 5,22 0,456 3

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

Файл к заданию: https://drive.google.com/file/d/1u0UeraUAc6mmy_nr-u33aw_-pA1usJv3/view

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

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

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

В каждой строке текстового файла хранится информация об одном наноботе: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$ , масса $m$ (активность выделения фермента).

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

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000.

Известно, что все описанные в файле наноботы (за исключением аномальных) подразделяются ровно на 3 кластера ($K = 3$) с $R = 2.0$ для каждого, а также в файле содержится ровно 10 аномальных точек.

Для каждого кластера определите его эпицентр, затем найдите два числа: $Q_1$ – отношение суммарной массы всех наноботов кластера с наибольшим количеством элементов к суммарной массе кластера с наименьшим количеством элементов, и $Q_2$ – сумму расстояний от каждого из трех найденных эпицентров до начала координат $(0; 0)$.

В ответе запишите два числа: сначала целую часть произведения $Q_1 * 10000$, затем целую часть произведения $Q_2 * 10000$.

Для справки

Кинетическая энергия $E$ нанобота массы $m$, обладающего скоростью $\vec{V}=(V_x; V_y)$ вычисляется по формуле:

$E = \frac{1}{2} * m * (V_x^2 + V_y^2)$.

Евклидово расстояние между двумя точками на плоскости $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,67 -2,14 3,0 -4,0 0,2

3,14 7,22 3,2 4,3 0,7

1,33 5,56 0,0 5,22 0,456

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

Файл к заданию: https://drive.google.com/file/d/1_S7ZNlbSwUESS0dQOjZNSwPITexAXaRJ/view

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

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

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

В каждой строке текстового файла хранится информация об одном наноботе: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$ , масса $m$ (активность выделения фермента).

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

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000.

Известно, что все описанные в файле наноботы (за исключением аномальных) подразделяются ровно на 3 кластера ($K = 3$) с $R = 2.0$ для каждого, а также в файле содержится ровно 10 аномальных точек.

Для каждого кластера определите его эпицентр, затем найдите два числа: $Q_1$ – среднюю массу $m$ наноботов в кластере, у которого сумма координат $X$ и $Y$ эпицентра наименьшая, и $Q_2$ – максимальное расстояние от эпицентра до точки своего кластера среди всех точек всех трех кластеров.

В ответе запишите два числа: сначала целую часть произведения $Q_1 * 10000$, затем целую часть произведения $Q_2 * 10000$.

Для справки

Кинетическая энергия $E$ нанобота массы $m$, обладающего скоростью $\vec{V}=(V_x; V_y)$ вычисляется по формуле:

$E = \frac{1}{2} * m * (V_x^2 + V_y^2)$.

Евклидово расстояние между двумя точками на плоскости $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,67 -2,14 3,0 -4,0 0,2

3,14 7,22 3,2 4,3 0,7

1,33 5,56 0,0 5,22 0,456

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

Файл к заданию: https://drive.google.com/file/d/19U9at1b3QJ0Z-zCTESyOISH7rMwaKRNo/view

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

Будем называть центром кластера такую его звезду, для которой сумма модулей разности кинетических энергий со всеми остальными звездами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.

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

В каждой строке текстового файла хранится информация об одной звезде: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$ , а также масса $m$.

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

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000.

Известно, что все описанные в файле звёзды (за исключением аномальных) подразделяются ровно на 3 кластера ($K = 3$) с $R = 2.0$ для каждого, а также в файле содержится ровно 3 аномальные точки. Гарантируется, что во всех кластерах количество точек различно.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ – число точек наибольшего по количеству точек кластера, находящихся вне круга радиуса 1,5 с центром в центре этого же кластера, и $Q_2$ – модуль разности расстояний между двумя ближайшими центрами кластеров, рассчитанных до очистки данных от аномалий и после неё.

В ответе запишите два числа: сначала $Q_1$, затем целую часть произведения $Q_2 * 10000$.

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

Для справки

Кинетическая энергия $E$ звезды массы $m$, обладающего скоростью $\vec{V}=(V_x; V_y)$ вычисляется по формуле:

$E = \frac{1}{2} * m * (V_x^2 + V_y^2)$.

Евклидово расстояние между двумя точками на плоскости $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,67 -2,14 3,0 -4,0 0,2

3,14 7,22 3,2 4,3 0,7

1,33 5,56 0,0 5,22 0,456

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

Файл к заданию: https://drive.google.com/file/d/16x2XELKJWxG2ycVQqsqBYrbTTQZwzQP3/view

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

Будем называть центром кластера такую его звезду, для которой сумма модулей разности кинетических энергий со всеми остальными звездами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.

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

В каждой строке текстового файла хранится информация об одной звезде: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$ , а также масса $m$.

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

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000.

Известно, что все описанные в файле звёзды (за исключением аномальных) подразделяются ровно на 4 кластера ($K = 4$) с $R = 2.0$ для каждого, а также в файле содержится ровно 5 аномальные точки. Гарантируется, что во всех кластерах количество точек различно.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ – количество звезд в кластере с наименьшей суммой координат $X$ и $Y$ своего центра, у которых абсцисса больше абсциссы центра этого кластера, и $Q_2$ – наименьшее евклидово расстояние между центрами четырех основных кластеров, рассчитанными после очистки данных от аномалий.

В ответе запишите два числа: сначала $Q_1$, затем целую часть произведения $Q_2 * 10000$.

Для справки

Кинетическая энергия $E$ звезды массы $m$, обладающего скоростью $\vec{V}=(V_x; V_y)$ вычисляется по формуле:

$E = \frac{1}{2} * m * (V_x^2 + V_y^2)$.

Евклидово расстояние между двумя точками на плоскости $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,67 -2,14 3,0 -4,0 0,2

3,14 7,22 3,2 4,3 0,7

1,33 5,56 0,0 5,22 0,456

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

Файл к заданию: https://drive.google.com/file/d/1-PavigceCMDdWGVrc3njjbw1Da44E1KJ/view

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

Будем называть центром кластера такую его звезду, для которой сумма модулей разности кинетических энергий со всеми остальными звездами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.

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

В каждой строке текстового файла хранится информация об одной звезде: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$ , а также масса $m$.

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

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 50000.

Известно, что все описанные в файле звёзды (за исключением аномальных) подразделяются ровно на 10 кластера ($K = 10$) с $R = 2.0$ для каждого, а также в файле содержится до 10 аномальные точки. Гарантируется, что во всех кластерах количество точек различно.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ – среднее арифметическое количество точек, находящихся внутри круга радиуса 2,0 с центром в центре своего кластера, для трёх наиболее удалённых от начала координат $(0; 0)$ кластеров, округлённое до ближайшего целого числа, и $Q_2$ – сумму расстояний между центрами всех возможных уникальных пар кластеров.

В ответе запишите два числа: сначала $Q_1$, затем целую часть произведения $Q_2 * 10000$.

Для справки

Кинетическая энергия $E$ звезды массы $m$, обладающего скоростью $\vec{V}=(V_x; V_y)$ вычисляется по формуле:

$E = \frac{1}{2} * m * (V_x^2 + V_y^2)$.

Евклидово расстояние между двумя точками на плоскости $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,67 -2,14 3,0 -4,0 0,2

3,14 7,22 3,2 4,3 0,7

1,33 5,56 0,0 5,22 0,456

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

Файл к заданию: https://drive.google.com/file/d/1_Jti00awiT5hL7ZchaiQA7GC-xbY7_9N/view

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

Будем называть центром кластера такую его звезду, для которой сумма модулей разности кинетических энергий со всеми остальными звездами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.

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

В каждой строке текстового файла хранится информация об одной звезде: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$ , а также масса $m$.

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

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 50000.

Известно, что все описанные в файле звёзды (за исключением аномальных) подразделяются ровно на 10 кластера ($K = 10$) с $R = 2.0$ для каждого, а также в файле содержится до 10 аномальные точки. Гарантируется, что во всех кластерах количество точек различно.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ – суммарное количество точек во всех 10 кластерах, у которых одновременно абсцисса меньше абсциссы центра своего кластера, а ордината больше ординаты центра своего кластера, и $Q_2$ – минимальное расстояние между центром наименьшего по количеству точек кластера и центром любого из остальных 9 кластеров.

В ответе запишите два числа: сначала целое число $Q_1$, затем целую часть произведения $Q_2 * 10000$.

Для справки

Кинетическая энергия $E$ звезды массы $m$, обладающего скоростью $\vec{V}=(V_x; V_y)$ вычисляется по формуле:

$E = \frac{1}{2} * m * (V_x^2 + V_y^2)$.

Евклидово расстояние между двумя точками на плоскости $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,67 -2,14 3,0 -4,0 0,2

3,14 7,22 3,2 4,3 0,7

1,33 5,56 0,0 5,22 0,456

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

Файл к заданию: https://drive.google.com/file/d/1uGRtYoaBCGk_PnNbMogMP20vGlh223h-/view

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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

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

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

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и пути из вершины 6 в вершину с номером 12, проходящего через вершину с номером 4, верным ответом будет 12. Единственный подходящий маршрут — 6 → 1 → 4 → 100 → 12, его длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть — 12.

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