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

8 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Возрастающие пути#44510

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

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

 

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

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

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

 

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

Выведите одно целое число 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средняяВойти и решать
Кодовый замок#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средняяВойти и решать
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 переход между помещениями. Иными словами, карта убежища представляет собой дерево.
Известно, что для перевозки грузов между помещениями в убежище скруллы используют специальных роботов. Роботы довольно примитивны и плохо ориентируются в убежище. Для решения этой проблемы скруллы выбрали в каждом переходе ровно одно направление, вдоль которого могут перемещаться роботы.
После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.
Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений p1p2 . . . pn, для которой верно, что если роботы могут перемещаться по переходу от помещения pi к помещению pj , то i < j.
Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.

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

Выходные данные: Выведите остаток от деления на 998 244 353 количества различных перестановок p1p2 . . . pn, для которых верно, что если роботы перемещаются по переходу от помещения pi к помещению pj , то 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средняяВойти и решать
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средняяВойти и решать
Эвакуация#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средняяВойти и решать
Друзья#21825
В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.
 
Входные данные
 
В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.
 
Выходные данные
 
В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

Ввод:
3 1
0 1 0
1 0 1
0 1 0

Вывод
2
графыПоиск компонент связности
✓ 0✗ 51 200средняяВойти и решать
Поделиться
Класснуть