Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Возрастающие пути#44510

Дано дерево на n вершинах (связный неориентированный ациклический граф c n−1 рёбрами), где у каждого ребра есть вес w. Назовём простой путь длины k возрастающим , если существует такое целое x>=2, что вес первого ребра пути делится на x, второго ребра — делится на x², ……, вес k-го ребра делится на x^k.

Требуется найти максимальную длину k возрастающего пути, где k — количество рёбер в нём.

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

В первой строке вводится единственное целое число n (1 <= n <= 100000) - число вершин в дереве.

В следующих n−1 строках вводятся по три целых числа u, v, w ( 1<= v <= n, 1<= w <= n, u ≠ v, 1 <= w <= 10⁷) - номера вершин, которые соединяет очередное ребро, и его вес.

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

Выведите одно целое число k - максимальную длину возрастающего пути.

Примечание

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

В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 8 1 3 6 1 4 3	2
2	6 1 2 2 2 3 4 3 4 2 4 5 4 5 6 8	3

Алгоритмы на графах Арифметические алгоритмы (Теория чисел)Обход в глубину Применение обхода в глубину

✓ 2✗ 31 200средняяВойти и решать

Switch Grass#27216

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

Ферма Джона состоит из NN (1≤N≤200,000), полей, и MM пар полей соединены двунаправленными дорожками (1≤M≤200,000). Используя эти дорожки, можно пройти от любого поля к любому другому полю. Каждая дорожка имеет целочисленную длину в интервале 1…1,000,000. Любая пара полей соединена не более чем одной прямой дорожкой.

В каждом поле ФД изначально посадил один из KK типов травы (1≤K≤N). Через некоторое время, однако, он может решить изменить тип травы на некоторых из полей. Он называет это операцией "обновления".

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

В 30 процентах тестов каждое поле непосредственно соединено не более чем с 10 дорожками.

ФОРМАТ ВВОДА:

Первая строка ввода содержит четыре целых числа N, M, K, Q, где Q - количество операций обновления (1≤Q≤200,000). Следующие M строк описывают дорожки. Каждая строка содержит три целых числа A, B, L, указывающих, что есть дорожка между полями A, B и её длина L. (A, B - целые числа в интервале 1…N). Следующая строка указывает начальный тип травы для каждого поля (N целых чисел в интервале 1…K). Затем идут Q строк, каждая из которых описывает одну операцию обновления двумя целыми числами A и B, означающими, что на поле A типе травы изменён на B.

ФОРМАТ ВЫВОДА:

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

Ввод	Вывод
3 2 3 4 1 2 3 2 3 1 1 1 2 3 3 2 3 1 2 2 2	1 3 3 1

Алгоритмы на графах Дерево отрезков, RSQ, RMQ Минимальный каркас Обход в глубину Структуры данных

✓ 1✗ 41 200средняяВойти и решать

Мониторинг труб#33124

Газораспределительная система одного региона устроена следующим образом. Она

содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними

трубами. Узел с номером 1 соответствует центральному газохранилищу.

Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с

номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi

к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до

любого узла системы (возможно, с использованием промежуточных узлов). В системе

используются трубы различных типов, тип трубы обозначается буквой английского алфавита

от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.

Для проверки качества труб используется специальный робот. Он помещается в

систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по

которой он перемещается. Робот может перемещаться по трубам только в том же

направлении, в котором по трубе передается газ. Совершив одно или несколько

перемещений по трубам между узлами, робот извлекается из системы труб.

Каждый запуск робота должен соответствовать одной из m заданных спецификаций,

пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st,

состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st,

если количество перемещений робота по трубам во время запуска совпадает с длиной st, и

для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с

st[j] —символом на позиции j в спецификации.

Если запуск робота соответствует спецификации с номером t, то стоимость этого

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

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

робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все

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

минимальна. Одну и ту же трубу можно проверять несколько раз.

Требуется написать программу, которая по описанию системы труб и списку

спецификаций определяет минимальную суммарную стоимость запусков робота, в

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

запусков (по требованию).

Формат входных данных

В первой строке входных данных находятся три целых числа n, m и t — количество

узлов системы труб, количество спецификаций запусков робота и параметр, указывающий,

требуется ли вывести список запусков робота или только их минимальную суммарную

стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 10⁵, t равно 0 или 1).

В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих

строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее

номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита,

задающая тип этой трубы (1 ≤ pi ≤ i – 1).

В последующих m строках содержится информация о спецификациях, i-я из этих

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

соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита

строку si — саму спецификацию (1 ≤ wi ≤ 10⁹). Суммарная длина строк si не превышает 10⁶.

Формат выходных данных

Первая строка выходных данных должна содержать одно число — минимальную

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

Если проверить все трубы невозможно, требуется вывести «–1».

Если t = 0, то больше ничего выводить не требуется.

Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний

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

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

следующих k строках необходимо вывести по три целых числа ai, bi и ci — номер узла, в

котором начинается запуск, номер узла, в котором заканчивается запуск, и номер

спецификации, которой соответствует запуск.

Если оптимальных способов проверки несколько, требуется вывести любой из них.

Ввод	Вывод
3 3 0 1 a 2 b 3 a 4 b 2 a	6
7 3 1 1 a 2 a 3 b 3 b 1 b 6 b 3 aab 5 b 2 ab	15 4 1 4 1 2 5 3 1 6 2 6 7 2

Пояснение к примеру

Система труб, заданная во втором примере входных данных, и оптимальный способ

проверки всех труб для этого случая приведены на рисунке ниже.

Необходимо обратить внимание на следующие моменты:

- трубу можно проверять несколько раз, так в приведенном примере дважды

проверена труба из узла 2 в узел 3;

- одну и ту же спецификацию разрешается использовать несколько раз, в

приведенном примере вторая спецификация используется дважды, для

проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;

- робот может перемещаться по трубам только в том же направлении, по

которому по трубе передается газ, спецификацию «ab» нельзя использовать

для проверки труб по маршруту 2→1→6, так как робот не может

переместиться из узла 2 в узел 1.

Алгоритмы на графах Деревья Динамическое программирование

1 300средняяВойти и решать

Воздушные потоки#24765

Колобок ушёл от бабушки и поехал путешествовать. Неожиданно для себя он забрёл в страну Ивэнлэнд. Первые трудности встали на его пути: Колобка и вход в страну отделял огромный ров с водой, которая, как известно, не очень хорошо влияет на нашего героя. К счастью, повсюду рас- положены воздушные потоки, которые могли поднимать того, кто на них встает, на определённую высоту. Страна не просто так названа Ивэнлэнд, поэтому все высоты, на которые могут поднять героя воздушные потоки — это чётные числа.

Представим воздушные потоки как массив h[1..n] из n натуральных чисел — высот потоков. Для каждого 1 ≤ i ≤ n посчитаем G[i] — индекс ближайшего элемента слева, строго большего h[i]. Более формально, g[i] = max{j | j < i и h[j] > h[i]}. Если i = 1 или до h[i] нет ни одного элемента больше него, то G[i] считается равным 0.

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

Чем меньше сумма, тем расположение оптимальнее. Всё, что может сейчас сделать Колобок — это увеличить высоту одного из воздушных потоков не более чем на m. После этого действия высота потока должна остаться целым числом, но может, если необходимо, стать и нечётной.

Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма S(h), описанная выше, после проделанного действия была минимальна.

Формат входного файла
В первой строке входного файла даны числа n, m (1 ≤ n ≤ 10⁵ , 1 ≤ m ≤ 10⁹ ) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них. Во второй строке даны высоты воздушных потоков h[i] (1 ≤ h[i] ≤ 10⁹ ). Гарантируется, что все высоты — чётные числа.

Формат выходного файла
В единственной строке выходного файла выведите одно целое число — минимальную искомую сумму.

Ввод	Вывод
3 100 4 2 6	4
3 2 4 2 6	5
3 10 2 2 2	4

Деревья Наименьший общий предок Разреженные таблицы (sparse table)Структуры данных

✓ 2✗ 151 200средняяВойти и решать

Пожар в НИИЧАВО#21953

В научно-исследовательском институте чародейства и волшебства пожар! Во время опыта Кор- неева В. П. по превращению всей морской и океанской воды планеты в живую воду произошло короткое замыкание, и теперь его кабинет объят пламенем. Задача первостепенной важности — спасти из огня ценные лабораторные приборы, в особенности единственный в своём роде диван- транслятор µ-поля. Ваша задача — перенести диван-транслятор из кабинета Корнеева в запасную лабораторию изучения µ-поля.

НИИЧАВО состоит из N кабинетов, соединённых M коридорами. Кабинеты пронумерованы це- лыми числами от 1 до N, при этом кабинет Корнеева имеет номер A, а лаборатория изучения µ-поля расположена в кабинете номер B. Благодаря специальному искажению пространства внутри инсти- тута, все коридоры имеют одинаковую длину, которую можно пройти за 1 минуту, если двигаться быстрым шагом.

Ситуация усугубляется тем, что диван-транслятор — прибор, очень чувствительный к резким пе- репадам температуры. Внутри каждого коридора НИИЧАВО поддерживается свой температурный режим. Если абсолютная величина разности температур в двух последовательных коридорах на пути из кабинета Корнеева в лабораторию окажется больше D градусов, то диван-транслятор пе- рейдёт в нестабильное состояние, что может привести к катастрофическим последствиям. Обратите внимание, что на своём пути вы не заходите в сами кабинеты, а только переходите из коридора в коридор, поэтому климат внутри кабинетов не влияет на диван-транслятор. В силу причин магиче- ского характера, войдя в коридор, вы обязаны дойти до его конца, иными словами, останавливаться или разворачиваться посреди коридора запрещено. По каждому коридору можно перемещаться в обоих направлениях.

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

Формат входных данных
В первой строке входных данных следуют три целых числа N, M и D (2 <= N <= 100 000, 1 <= M <= 200 000, 0 <= D <= 2 · 10⁸ ), обозначающие количество кабинетов, количество коридоров в НИИЧАВО и максимальный допустимый перепад температур для дивана-транслятора в граду- сах. В последующих M строках находятся описания коридоров. Каждая строка содержит по три целых числа ui , vi , ti — номера двух кабинетов, соединённых i-м коридором, и значение температуры в этом коридоре, выраженное в градусах (1 <= ui , vi <= N, −109 <= ti <= 10⁹ ). Как вы уже могли понять, НИИЧАВО — весьма необычное заведение, поэтому между двумя кабинетами может пролегать несколько коридоров, возможно с разными температурами, а некоторые коридоры могут соединять кабинет с самим собой. Гарантируется, что коридоры перечислены во входном файле в порядке неубывания ti . В следующей строке находится целое число Q (1 <= Q <= 50) — количество пар A и B, которые вам требуется обработать. В каждой из последующих Q строк находятся по два целых числа Ai , Bi , обозначающих номер кабинета Корнеева и номер кабинета, в котором расположена лаборатория (1 <= A_i , B_i <= N, A_i != B_i).

Формат выходных данных
Для каждого набора данных выведите в отдельной строке минимальное количество минут, ко- торое требуется потратить, чтобы добраться из кабинета Корнеева до лаборатории, либо выведите −1, если сделать это, используя допустимый для дивана-транслятора маршрут, невозможно.

Примеры

Ввод	Вывод
6 9 5 6 6 -42 1 2 4 2 3 6 3 2 7 2 5 11 6 1 12 1 3 15 3 4 16 5 6 18 2 1 5 4 2	4 -1
6 9 7 6 6 -42 1 2 4 2 3 6 3 2 7 2 5 11 6 1 12 1 3 15 3 4 16 5 6 18 1 4 2	5

Замечание
Пояснение к тестам из условия. В обоих тестах план НИИЧАВО выглядит следующим образом:

Рассмотрим первый тест, в нём D = 5. В первом наборе A = 1, B = 5. В качестве воз- можного маршрута может выступить следующая последовательность переходов по коридорам:

Третьим шагом можно вернуться в кабинет 2 и по тому же коридору с t = 6 .
Во втором наборе A = 4, B = 2. Способа добраться из кабинета 4 в кабинет 2, ни разу не допустив перепад температуры больше, чем в 5 градусов, не существует.

Во втором тесте D = 7. В единственном наборе A = 4, B = 2 cтартовый и конечный кабинет те же, что и во втором наборе первого теста из условия, но допустимый перепад температур больше, благодаря чему подходит следующий маршрут:

Алгоритмы на графах Обход в ширину Структуры данных

✓ 12✗ 211 200средняяВойти и решать

Караваны и Провинции#50366

Далекая страна содержит \(n\) городов, соединенных \(n - 1\) дорогами, при этом из любого города можно добраться до любого другого по дорогам страны.

Известно, что каждый город относится ровно к одной провинции. Город \(v\) относится к провинции \(t_v\). Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер \(1\).

Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить. В городе \(v\) он равен \(c_v\).

Вам приходят запросы двух типов:

Изменить провинцию, к которой относится город \(v\), на \(t_{new}\)
В \(k\) городах с номерами \(a_1, a_2, \ldots, a_k\) появляется по одному каравану, которые идут в столицу (город с номером 1) по кратчайшему пути. Разбойники выбирают один город, который находится в провинции \(t\), после чего грабят все караваны, которые пройдут через этот город. Если разбойники ограбят караваны в городе с номером \(v\), то они получат \(c_v \cdot num_v\), где \(c_v\) — коэффициент города \(v\), а \(num_v\) это количество караванов, проходящих через этот город.

Определите максимальный ущерб, равный количеству награбленного разбойниками, для каждого запроса второго типа. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Формат входных данных
В первой строке даны два целых числа \(n\) и \(q\) (\(2 \le n \le 200\,000, 1 \le q \le 200\,000\)) — количество городов и количество запросов.

Во второй строке дано \(n - 1\) целое число \(p_2, p_3, \ldots, p_n\) (\(1 \le p_i < i\)), где число \(p_i\) означает, что существует дорога между городами \(i\) и \(p_i\).

В третьей строке дано \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le n\)) — номера провинций у городов.

В четвертой строке дано \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 10^9\)) — коэффициенты успешности грабежа.

Далее идет \(q\) строк описаний запросов. В начале каждой строки дано одно целое число \(x_i\) (\(1 \le x_i \le 2\)) — тип запроса.

Если \(x_i = 1\), то далее идет два целых числа \(v\) и \(t_{new}\) (\(1 \le v, t_{new} \le n\)) — номер города, у которого меняется провинция, и номер его новой провинции.
Если \(x_i = 2\), то далее идут целые числа \(t\) и \(k\), и \(k\) целых чисел \(a_1, a_2, \ldots, a_k\) (\(1 \le t, k, a_i \le n\)) — номер провинции, в городе которой можно грабить; количество городов, из которых выходят караваны; и номера городов, из которых входят караваны. Гарантируется, что в одном запросе все \(a_i\) различны. Также гарантируется, что сумма \(k\) по всем запросам второго типа не превышает \(200\,000\).

Формат выходных данных
На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Примечание
В первом запросе караваны идут из городов с номерами \(3\) и \(4\) и нужно ограбить их в городе из третьей провинции. Это те же самые города с номерами \(3\) и \(4\), через каждый из которых пройдет по одному каравану. Поэтому разбойники ограбят караваны в третьем городе и получат \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

Во втором запросе караваны также идут из городов с номерами \(3\) и \(4\), но теперь нужно ограбить их в городе из первой провинции. В первой провинции находятся города \(1\) и \(2\), через каждый из которых пройдет два каравана. Среди них разбойники выбирают город \(2\), потому что \(c_2 > c_1\) и ответ на этот запрос равен \(c_2 \cdot 2 = 3 \cdot 2 = 6\).

В третьем провинция для города \(3\) изменяется на \(1\).

В четвертом запросе караваны снова идут из городов с номерами \(3\) и \(4\), и нужно ограбить караваны в городе из первой провинции. То есть разбойники могут ограбить караваны в одном из городов с номерами \(1, 2\) или \(3\). Через города с номерами \(1\) и \(2\) пройдет два каравана, а через город \(3\) только один. Разбойникам выгодно ограбить караваны в городе \(3\) и получить \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

графы Дерево отрезков, RSQ, RMQ Деревья

✓ 1✗ 201 200средняяВойти и решать

Выбор столицы#48969

Дано неориентированное дерево "— связный граф из \(n\) вершин без циклов, и число \(k\). Зафиксируем некоторую вершину \(s\) дерева и назовем ее столицей.

Ориентируем ребра дерева в направлении от столицы. Иными словами, ориентируем ребро \((u, v)\) в направлении \(u \to v\), если при подвешивании дерева за вершину \(s\) вершина \(u\) является родителем вершины \(v\). Заметим, что при таком ориентировании ребер каждая вершина достижима из столицы.

Определим расстояние до вершины \(v\) графа как минимальное количество ребер на пути из \(s\) в \(v\). Назовем доступностью вершины \(s\) максимальное из расстояний до всех вершин.

Разрешается добавить в дерево не более \(k\) дополнительных ориентированных ребер.

Для каждой вершины \(s\) дерева определите, какой минимальной доступности можно достичь, если выбрать вершину \(s\) в качестве столицы.

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

Формат входных данных
Первая строка содержит три целых числа \(n\), \(k\) и \(t\) (\(2 \le n \le 2 \cdot 10^5\), \(1 \le k \le n - 1\), \(n \cdot k \le 2 \cdot 10^5\), \(0 \le t \le 1\)) — количество вершин дерева, ограничение на максимальное количество добавленных ребер и число \(t\), равное \(0\), если нужно вывести ответ только для вершины с номером \(1\), и равное \(1\) иначе.

Каждая из следующих \(n - 1\) строк содержит два целых числа \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) — ребра дерева.

Гарантируется, что заданные ребра образуют дерево.

Формат выходных данных

В случае, если \(t = 0\), выведите единственное целое число: минимальную доступность, которую можно достичь, выбрав вершину с номером \(1\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

В случае, если \(t = 1\), выведите \(n\) чисел: \(i\)-е число равняется минимальной доступности, которую можно достичь, выбрав вершину \(i\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

На рисунке приведены иллюстрации к первому примеру. Пунктирными линиями обозначены добавленные ребра. Для вершин \(1\) и \(2\) минимальная доступность равняется \(1\), а для вершин \(3\), \(4\) и \(5\) минимальная доступность равняется 2.

графы Деревья дп

✓ 0✗ 461 200средняяВойти и решать

Ускорители для Деда Мороза#44037

Дед Мороз за ночь должен посетить N городов. У него есть двумерный план расположения всех городов. План нарисован в декартовой системе координат, в которой точкой (0, 0) обозначено место старта Деда Мороза. Каждый город на плане отмечен точкой с координатой (X_i, Y_i). Также на карте обозначены M точек с координатами (P_i, Q_i), в которых расположены ускорители. Чтобы успеть разнести все подарки, Дед Мороз может воспользоваться ускорителем, который увеличивает его скорость в два раза (а может им и не пользоваться).

Дед Мороз в Новогоднюю ночь начинает с места старта, посещает все N городов и возвращается обратно.

Начальная скорость Деда Мороза равна 1. Найдите наименьшее время, необходимое Деду Морозу, чтобы посетить все города и вернуться обратно. Временем, при котором он раскладывает все подарки будем пренебрегать!

Входные данные
Первая строка входных данных содержит два целых числа N и M (1 <= N <= 12, 0 <= M <=5). Следующие N строк содержат координаты городов (X_i, Y_i). Далее идут M строк с координатами ускорителей (P_i, Q_i). Все координаты различны и среди них нет координаты (0, 0).

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	2 1 1 1 0 1 1 0	2 1 1 1 0 1 1 0	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1. Пройти расстояние 1 от ускорителя 1 до города 1 со скоростью 2, затратив время 0,5. Пройти расстояние 1 от города 1 до города 2 со скоростью 2, затратив время 0,5. Пройти расстояние 1 от города 2 до начала координат со скоростью 2, затратив время 0,5.
2	2 1 1 1 0 1 100 0	3.4142135624	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1.41... от начала координат до города 1 со скоростью 1, затратив время 1.41.... Пройти расстояние 1 от города 1 до города 2 со скоростью 1, затратив время 1. Пройти расстояние 1 от города 2 до начала координат со скоростью 1, затратив время 1.
3	1 2 4 4 1 0 0 1	4.3713203436	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1. Пройти расстояние 1,41... от ускорителя 1 до ускорителя 2 со скоростью 2, затратив время 0,707.... Пройти расстояние 5 от ускорителя 2 до города 1 со скоростью 4, затратив время 1,25. Пройти расстояние 5,65... от города 1 до начала координат со скоростью 4, затратив время 1,41....

Алгоритмы на графах Динамическое программирование на таблицах Элементарная геометрия

✓ 2✗ 181 300средняяВойти и решать

Короткий код#40164

Код Эвана содержит n переменных. Каждая переменная имеет уникальное имя, состоящее только из английских строчных (маленьких) букв. Однажды Эван решил укоротить свой код.

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

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

Найдите минимальную возможную суммарную длину новых имён.

Входные данные:
В первой строке содержится одно целое число n (1 ≤ n ≤ 10⁵) — число переменных в коде Эвана.

Следующие n строк содержат названия переменных по одному на строку. Каждое название не является пустой строкой и содержит только лишь строчные (маленькие) английские буквы. Суммарная длина всех этих строк не больше 10⁵. Все названия переменных различны.

Выходные данные:
Выведите одно целое число — минимально возможную суммарную длину новых названий переменных.

Примеры:

Входные данные	Выходные данные
3 codeforces codehorses code	6
5 abba abb ab aa aacada	11
3 telegram digital resistance	3

Пояснения:
В первом примере одним из наилучших вариантов будет сокращение имён в порядке их ввода до "cod", "co", "c".
Во втором примере можно укоротить последнее имя до "aac" и первое имя до "a" без изменения других имён переменных.

Бор Деревья Жадный алгоритм

✓ 1✗ 101 200средняяВойти и решать

Роботы#38573

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

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

Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).

Входные данные
Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

Выходные данные
Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 1 3 3 1 2 4	1
2	3 2 1 2 2 3 2 1 3	1

Задачи на моделирование Обход в ширину

✓ 2✗ 351 200средняяВойти и решать

Кодовый замок#38371

Компания «Замки и замки» недавно разработала новый тип кодового замка, для размещения на воротах замков. Панель замка представляет собой прямоугольник шириной w ячеек и высотой h ячеек. В некоторых из них расположены кнопки.

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

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

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

В первой строке находятся три целых числа h, w и k (1 ≤ h, w ≤ 30; 1 ≤ k ≤ 10). Каждая из последующих h строк содержит w символов. Символ «#» обозначает кнопку, а «.» — ее отсутствие.

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

Выведите единственное число — количество кодов, удовлетворяющих указанным требованиям.

Примеры

№	Входные данные	Выходные данные
1	2 2 2 .# ##	2
2	5 6 7 .#.... ##.##. ..#.#. .####. .....#	3

Обход в глубину

✓ 3✗ 551 300средняяВойти и решать

Перегоны#38355

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

Входные данные
Во входном файле записаны сначала числа N — количество станций (2 ≤ N ≤ 100) и E — количество пар станций, расстояния между которыми заданы (0 ≤ E ≤ 10000). Далее идет E троек чисел, первые два числа каждой тройки задают номера станций (это числа из диапазона от 1 до N), а третье — расстояние между этими станциями (все эти расстояния заданы точно и выражаются вещественными неотрицательными числами не более чем с 3-я знаками после десятичной точки).

Выходные данные
В случае, когда восстановить длины перегонов можно однозначно, в выходной файл выведите сначала число 1, а затем N–1 вещественное число. Первое из этих чисел должно соответствовать расстоянию от 1-й станции до 2-й, второе — от 2-й до 3-й, и так далее. Все числа должны быть выведены с точностью до 3-х знаков после десятичной точки.

Если приведенная информация о расстояниях между станциями является противоречивой или не позволяет однозначно точно восстановить длины перегонов, выведите в выходной файл одно число 2.

Примеры

№	Входные данные	Выходные данные
1	2 3 1 1 0 2 2 0 2 1 2.5	1 2.500
2	15 13 1 2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 1 8 7 1 9 8 1 10 9 1 11 10 1 12 11 1 13 12 15 14 13	2

Обход в глубину

✓ 1✗ 71 200средняяВойти и решать

Робот#38285

На Марсе есть большой полигон для испытания роботов. Он представляет собой таблицу из n строк и m столбцов, столбцы которой направлены с севера на юг, а строки — с запада на восток. В каждой клетке таблицы находится ускоритель, направленный в одну из сторон света.

Находясь в клетке, робот может воспользоваться ускорителем в ней. При этом он попадает в соседнюю с текущей клетку в направлении ускорителя и не тратит топливо. Если соседней клетки в направлении ускорителя нет, то им нельзя воспользоваться. Также робот может не пользоваться ускорителем и переместиться в любую из соседних клеток, затратив один литр топлива.

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

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

Входные данные
Первая строка входных данных содержит два числа n и m — протяженность полигона с севера на юг и с запада на восток ( 1 ≤ n , m ≤ 20 ).

Следующие n строк содержат по m латинских букв, описывающих направления ускорителей в очередной строке. Буква соответствуют направлению ускорителя: N — на север, W — на запад, S — на юг, E — на восток. Строки занумерованы с севера на юг, а столбцы с запада на восток. Таким образом, направление на север соответствует уменьшению номера строки, направление на юг — увеличению номера строки, направление на запад — уменьшению номера столбца, а направление на восток — увеличению номера столбца.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 SSN NSN SWN SWE ENS	2

0-1 BFS

✓ 4✗ 111 300средняяВойти и решать

Порталы#38132

Беси расположена на сети из N (2≤N≤10⁵) вершин помеченных 1…N и 2N порталов помеченных 1…2N. Каждый портал соединяет две различных вершины u и v (u≠v). Множество порталов может соединять некоторую пару вершин.
Каждая вершина v соседняя для четырёх различных порталов. Список порталов вершины v задаётся как pv=[p_v,1,p_v,2,p_v,3,p_v,4].

Ваше текущее положение может быть представлено упорядоченной парой (current vertex,current portal); то есть парой (v,p_v,i) где 1≤v≤N и 1≤i≤4. Вы можете использовать одну из следующих операций для изменения своего текущего положения:

Изменить текущую вершину перемещением через текущий портал.
Переключить текущий портал. В каждой вершине первые два портала в списке объединены в пару и последние два портала в списке также объединены в пару. Поэтому если Ваше текущее состояние (v,p_v,2), то Вы можете переключиться чтобы использовать портал (v,p_v,1) и обратно. Аналогично, если Ваше текущее положение (v,p_v,3) Вы можете переключиться на портал (v,p_v,4) и обратно. никакие другие переключения не разрешены (например, Вы не можете переключиться с портала pv,2 на портал) p_v,4).
Всего имеется 4N различных состояний. К несчастью, может не оказаться, что что любое состояние достижимо из любого с помощью последовательности заданных операций. Поэтому, за цену cv (1≤c_v≤1000) мунов вы можете сделать перестановку списка порталов соседних вершине v, в любом желаемом Вами порядке. После этого первые два портала в списке объединяются в одну пару, а последние два портала - в другую пару.

Например, если Вы переставить порталы вершины v в порядке [p_v,3,p_v,1,p_v,2,p_v,4], Это означает. что если Вы в вершине v,

Если Вы в портале p_v,1, Вы можете переключиться на портал p_v,3 и обратно
Если Вы в портале p_v,2, Вы можете переключиться на портал p_v,4 и обратно
Теперь Вы не можете переключаться с портала p_v,1 на p_v,2, или с портала p_v,3 на портал p_v,4 и обратно.
Вычислите минимальное количество мунов, требуемых для модификации сети таким образом, чтобы сделать достижимым каждое состояние из каждого состояния. Гарантируется, что тестовые данные сконструированы таким образом, что существует хотя бы один способ такой модификации сети.

Входные данные:
Первая строка содержит N.
Каждая из следующих N строк описывает вершину. Строка v+1 содержит 5 разделённых одиночными пробелами целых чисел c_v,p_v,1,p_v,2,p_v,3,p_v,4.
Гарантируется, что для каждой v все p_v,1,p_v,2,p_v,3,p_v,4 различны, и каждый портал появляется в списках ровно двух вершин.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	Достаточно сделать перестановку списков вершин 1 и 4. Это требует c1+c4=13 мунов. Перестановки такие: p1=[1,9,4,8] и p4=[7,4,6,3].

Древовидные структуры данных Минимальный каркас Система непересекающихся множеств

✓ 2✗ 391 200средняяВойти и решать

*Сталкер#33469

В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.

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

Входные данные:
- в первой строке входных данных содержатся два натуральных числа N и K (\(2 <= N <= 2000\); \(1 <= K <= 2000\)) — количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад — в здании с номером N.
- в последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i — количество дорог, обозначенных на i-ой карте;
- затем идут r_i строк, содержащие по два натуральных числа a и b (\(1 <= a\), \(b <= N\); \(a ? b\)), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (\(r_1 + r_2 + … + r_K <= 300 000\)).

Выходные данные: выведите одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1.

Примеры

№	Входные данные	Выходные данные
1	12 4 4 1 6 2 4 7 9 10 12 3 1 4 7 11 3 6 3 2 5 4 11 8 9 5 3 10 10 7 7 2 12 3 5 12	3

0-1 BFS Дек

✓ 3✗ 951 300средняяВойти и решать

Проложи дорогу#33467

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

Формат входных данных
Первая строка содержит число N – количество городов в стране (\(1\leq N\leq10^4\)). Каждая из последующих N строк содержит по два целых числа, xi и yi – координаты соответствующего города (\(|x|, |y| \leq 10^6\) ). Далее содержится число M – количество особых пар городов (\(0\leq M \leq min(10^4, N(N-1)/2)\). Далее в M строках содержится описание особых дорог, каждое состоит из трех целых чисел: u, v – пара различных городов, между которыми проходит особая дорога, и w – стоимости постройки соответствующей дороги (\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). В последней строке содержатся номера городов А и Б (от 1 до N).

Формат выходных данных
Выведите одно число – искомую минимальную длину. Ваш ответ должен отличаться от правильного не более чем на 10⁻⁵.

Алгоритм Дейкстры

✓ 6✗ 5881 400средняяВойти и решать

Type Printer#33314

Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:

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

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

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

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

Ваша программа должна считать следующие входные данные:

На первой строке число N (1<=N<=25000).

На следующих N строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 20. Все слова различны.

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

Ваша программа должна вывести следующие данные:

На первой строке M — число операций.

На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:

Добавление символа обозначается собственно символом.

Удаление символа обозначается символом «-» (минус, ASCII-код 45).

Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).

Ввод	Вывод
3 print the poem	20 t h e P - - - p o e m P - - - r i n t P

Бор Обход в глубину

✓ 1✗ 741 200средняяВойти и решать

*Упорядочивания#33257

Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.

Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя n помещений, пронумерованных от 1 до n. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно n − 1 переход между помещениями. Иными словами, карта убежища представляет собой дерево.

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

После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.

Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений p₁p₂ . . . p_n, для которой верно, что если роботы могут перемещаться по переходу от помещения pi к помещению p_j , то i < j.

Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.

Входные данные: Первая строка входных данных содержит единственное целое число n — количество помещений в убежище, нарисованном Йон-Роггом (1 <= n <= 3 000).

Каждая из следующих n − 1 строк содержит два целых числа a, b — номера помещений, соединенных очередным коридором (1 <= a, b <= n). Роботы перемещаются по коридору в направлении от помещения a к помещению b.

Гарантируется, что убежище представляет собой дерево, то есть от любого помещения можно добраться до любого другого, двигаясь по переходам (возможно, в направлении, противоположном направлению движения роботов в этом переходе).

Выходные данные: Выведите остаток от деления на 998 244 353 количества различных перестановок p₁p₂ . . . p_n, для которых верно, что если роботы перемещаются по переходу от помещения p_i к помещению p_j , то i < j.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 1 3	2
2	4 2 3 3 1 2 4	3

Замечание

В первом тесте из примера Кэрол может выписать две перестановки: {1, 2, 3} или {1, 3, 2}.

Во втором тесте Кэрол может выписать три перестановки: {2, 3, 1, 4}, {2, 3, 4, 1} или {2, 4, 3, 1}.

Топологическая сортировка

✓ 3✗ 121 300средняяВойти и решать

Все кратчайшие маршруты#33229

Учёный-ботаник получил карту дорог страны Лимония. Чтобы составить план исследования этой страны, ему требуется найти кратчайшие расстояния между каждой парой городов этой страны (можно ехать только по проложенным дорогам). Помогите учёному – напишите программу, которая решает эту задачу.

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

В первой строке вводится количество городов N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог между городами: положительное число означает расстояние между городами, ноль говорит о том, что дороги нет.

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

Программа должна вывести все кратчайшие маршруты между всеми городами в следующем формате:

(1->3): 1 2 3 (23)

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

Ввод	Вывод
4 0 0 0 0 0 0 2 1 0 2 0 4 0 1 4 0	(1,2): 0 (1,3): 0 (1,4): 0 (2,3): 2 3 (2) (2,4): 2 4 (1) (3,4): 3 2 4 (3)

Алгоритм Флойда кратчайшие пути

✓ 1✗ 901 200средняяВойти и решать

Эвакуация#24913

Через T минут армия читаури под предводительством Локи атакует Землю. Мстители никак не успевают помешать открытию портала в Нью-Йорке, поэтому Капитан Америка принял решение эвакуировать из города всех его жителей. Ему необходимо выяснить, успеют ли жители города эвакуироваться до начала вторжения.

Окрестности Нью-Йорка можно представить как набор небольших городов, связанных между собой дорогами с односторонним движением. Каждая дорога характеризуется своей длиной и пропускной способностью. Длина дороги l означает, что въехав на нее в момент времени t, автомобиль окажется в конце этой дороги через l минут, в момент времени t + l. Пропускная способность дороги s означает, что каждую минуту на эту дорогу могут въехать не больше, чем s автомобилей. Приехав в какой-нибудь город, любой автомобиль может сразу продолжить путь, въехав на какую-то дорогу, выходящую из этого города, а может остановиться в этом городе на любое количество минут, и только потом уехать из него.

Капитан Америка уже решил, в каком именно городе должны оказаться жители Нью-Йорка после эвакуации. Также ему известно, сколько автомобилей необходимо для эвакуации всего города. Теперь ему необходимо выяснить успеют ли все жители эвакуироваться до прибытия захватчиков и, если да, какое минимальное количество времени у них на это уйдет, а если нет какому минимальному числу автомобилей с горожанами не удастся доехать до безопасного города.

Формат входного файла

Первая строка входного файла содержит четыре целых числа n, m, K и T (1 ≤ n x T ≤ 10 000, 1 ≤ m, K ≤ 10 000) количество городов в окрестностях Нью-Йорка, количество дорог между ними, количество автомобилей, которым необходимо попасть из Нью-Йорка в безопасный город и время до вторжения захватчиков соответственно. Следующие m строк содержат описания дорог между городами.

Каждая дорога описывается четырьмя целыми числами u, v, l и s (1 ≤ u, v ≤ n, u != v, 1 ≤ s ≤ 3 000, 1 ≤ l ≤ 200) город, из которого выходит эта дорога, город, в который она ведет, ее длина и пропускная способность соответственно.

Между двумя городами может существовать только одна дорога, ведущая в каком-то направлении. Нью-Йорком считается город с номером 1, а безопасным городом город с номером n. в момент времени 0 все автомобили находятся в Нью-Йорке.

Формат выходного файла

Если все жители Нью-Йорка успеют добраться до безопасного города не более, чем за T минут, выведите в выходной файл минимальное количество минут, которое им на это понадобится. В противном случае выведите минимальное количество автомобилей, которым не удастся попасть в безопасное место за T минут. Да, не нужно выводить, какой из этих случаев имеет место :-).

Ввод	Вывод
5 5 10 10 1 2 2 2 2 3 1 1 2 4 1 1 4 5 2 4 3 5 2 4	9

Обход в глубину

✓ 0✗ 61 300средняяВойти и решать