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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 3 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 1,3. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наименьшее расстояние между центрами двух кластеров; Q₂ — разность между максимальным и минимальным значениями энергия центров кластеров.

В ответе запишите целые части произведений Q₁ × 10 000 и Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 5 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,0. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — количество частиц с признаком IV в кластере с наибольшей средней массой частиц; Q₂ — среднее арифметическое модулей скоростей центров кластеров.

В ответе запишите сначала Q₁, затем целую часть произведения Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,5. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наибольшее среди всех частиц значение |E − E_ц|, где E_ц — значение характеристики центра её кластера; Q₂ — наибольшее расстояние между центрами двух кластеров.

В ответе запишите целые части произведений Q₁ × 10 000 и Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 1,5. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — максимальная по всем кластерам разность между наибольшей и наименьшей массами частиц с признаком VII внутри одного кластера; Q₂ — среднее арифметическое абсцисс центров кластеров.

В ответе запишите целые части произведений Q₁ × 10 000 и |Q₂| × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 5 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 1,8. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — количество частиц с признаком I в кластере, центр которого имеет максимальное значение кинетической энергии; Q₂ — ордината центра этого кластера.

В ответе запишите сначала Q₁, затем целую часть произведения |Q₂| × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 3 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 1,6. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наибольшее расстояние между двумя частицами кластера с наименьшим количеством частиц; Q₂ — модуль скорости центра кластера, у которого значение кластеризующей характеристики минимально.

В ответе запишите целые части произведений Q₁ × 10 000 и Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,0. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — общее количество частиц с признаком VI, находящихся на расстоянии не более 10,0 от центра своего кластера; Q₂ — среднее арифметическое значений энергия центров всех кластеров.

В ответе запишите сначала Q₁, затем целую часть произведения Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,2. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — количество частиц с признаком III в кластере, содержащем наибольшее число частиц; Q₂ — расстояние между центрами кластеров с наибольшим и наименьшим количеством частиц.

В ответе запишите два числа: сначала Q₁ без изменения, затем целую часть произведения Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 1,8. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наибольшее расстояние от частицы с признаком V до центра того кластера, которому эта частица принадлежит; Q₂ — наибольшая масса среди центров кластеров.

В ответе запишите целые части произведений Q₁ × 10 000 и Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,0. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наименьшее евклидово расстояние между двумя различными частицами одного кластера, каждая из которых имеет признак IV; Q₂ — минимальное значение кинетической энергии среди центров кластеров.

В ответе запишите два числа: целые части произведений Q₁ × 10 000 и Q₂ × 10 000 в указанном порядке.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,0. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наибольшее евклидово расстояние между двумя частицами одного кластера, каждая из которых имеет признак II; Q₂ — максимальное значение кинетической энергии среди центров кластеров.

В ответе запишите два числа: сначала целую часть произведения Q₁ × 10 000, затем целую часть произведения Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

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

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Для каждой частицы на плоскости известны её координаты x и y, проекции вектора скорости Vx и Vy, масса m и тип внутреннего строения. Тип обозначается одним из римских чисел от I до VII.

Частицы требуется разделить на пять непустых непересекающихся кластеров по значениям кинетической энергии. В пределах каждого кластера разность между энергиями любых двух частиц по модулю не должна превышать 1,5. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений в следующем порядке: x, y, Vx, Vy, m, тип. Значения разделены пробелами и/или символами табуляции. Дробная часть чисел отделена точкой. Все величины заданы в согласованных единицах измерения. Масса каждой частицы положительна, абсолютное значение каждого числового поля не превосходит 100. В файле не более 10 000 строк; заголовка нет.

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

• Q1 — наибольшее евклидово расстояние между двумя частицами одного кластера, одна из которых имеет тип III, а другая — тип VI;
• Q2 — среднее арифметическое значений кинетической энергии центров всех пяти кластеров.

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

В ответе запишите два числа: сначала целую часть произведения Q1 · 10 000, затем целую часть произведения Q2 · 10 000.

Кинетическая энергия частицы вычисляется по формуле

\(E = m · (Vx^2 + Vy^2) / 2.\)

Евклидово расстояние между точками (x₁; y₁) и (x₂; y₂) равно

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

Пример трёх строк файла:

1.20  -3.40   2.000  -1.000  0.60000000  III
5.10   0.80  -1.500   2.000  0.80000000  VI
-2.70  4.30   1.000  -3.000  0.40000000  I

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

Числа в ответе разделяйте одним пробелом.

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

Поступающих, допущенных к зачислению, упорядочивают по следующим правилам:

1. Выше располагается поступающий с большей суммой баллов за три испытания.
2. При равенстве сумм выше располагается поступающий с большим наименьшим баллом за отдельное испытание.
3. При равенстве обоих показателей выше располагается поступающий с меньшим ID.

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

В первой строке файла записаны два натуральных числа N и K — количество поступающих и количество мест, 1 ≤ K < N ≤ 100 000. Каждая из следующих N строк содержит пять целых чисел: уникальный ID поступающего, баллы за три испытания и отметку о прохождении практикума. ID находится в диапазоне от 1 до 1 000 000, каждый балл — от 0 до 100. Отметка 1 означает, что практикум пройден, 0 — что не пройден.

Определите количество поступающих, которые были допущены к зачислению, но не получили места, и ID последнего зачисленного поступающего. В ответе запишите эти два числа в указанном порядке.

Пример содержимого файла:

6 2
101 60 70 80 1
205 80 60 70 1
309 90 90 39 1
412 70 70 70 1
518 95 90 80 0
624 55 60 65 1

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

Числа в ответе разделяйте одним пробелом.

Пусть S — сумма всех чётных натуральных делителей числа, кроме самого числа.

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

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


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

 

Текстовый файл содержит одну строку длиной не более 3 000 000 символов. Строка состоит из латинских букв A, B, C, D, E и цифр от 1 до 9.

Определите максимальную длину непрерывной последовательности символов, которая содержит ровно 1500 вхождений подстроки BCA и не более 20 букв E.

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

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

Найдите кратчайший путь из вершины 7 в вершину 941. Длина пути равна сумме весов входящих в него рёбер. Гарантируется, что хотя бы один такой путь существует.

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

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

Пример графа:

Пример содержимого файла для этого графа: 63 941 8.0 7 28 4.6 941 512 1.1 63 28 1.5 7 941 11.6 28 941 3.2 7 63 2.4

Ответ для примера: 7.

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

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

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

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

В ответе запишите целое число миллисекунд.

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

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

• Петя не может выиграть первым ходом;
• Петя может гарантированно выиграть своим вторым ходом независимо от действий Вани.

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

Числа в ответе разделяйте одним пробелом.

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

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

Игра заканчивается, как только в куче остаётся не более 20 камней. Побеждает игрок, сделавший последний ход. В начальный момент в куче S камней, S ≥ 21.

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

Найдите наименьшее S, при котором Петя не может выиграть первым ходом, а Ваня после любого первого хода Пети может выиграть своим первым ходом.