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

65817#65817

В далёком заснеженном города Снежнокрибирске очень мало пеших тропинок, так как город просто не успевает их чистить, потому люди передвигаются в основном только на внедорожниках: ездят в магазин, отвозят детей в школу, ездят на работу и так далее.
В один из последних дней перед зимними каникулами ребятам в школе задали проект на каникулы, который можно делать как самому, так и в группе, но не более 3 человек. Но так как проект связан с совместной работой, а в городе нет никакой связи: ни телефонной, ни интернета, то ребята решили собираться у кого-нибудь дома, чтобы делать проект вместе. Так как проект может делать до трёх человек, то ученики составили карту своих домов в городе, а также отметили на них тропинки. У них встал вопрос о том, как делать большинство проектов максимальным возможным количеством человек, но так, чтобы как можно меньше учеников делали проект одни. Помогите ребятам по описанию карты их города и тропинкам составить возможный план, как им лучше распределить проекты между собой.

Формат входных данных
На первой строке подаются два числа N, M (1 <= N,M <= 100) – количество домов и тропинок между ними соответственно.
Далее на M строках подаются дорожки в виде номеров домов (если существует дорога 1-2, то значит существует дорожка и 2-1).
Формат выходных данных
Выведите на первой строке количество учеников, которые делают проект в одиночку.
На второй – количество групп учеников, делающих проект в паре.
На третьей – количество групп учеников, делающих проект втроём.

Примечание: ребята стараются разбиться на группы по максимуму человек (по 3), если остался кто-то один, но он мог делать проект не один, то стараемся минимизировать одиночек.

✓ 32✗ 58800средняяВойти и решать

Трехцветные таблицы#55402

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

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

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

Входные данные
Вводятся числа N и M — количество строк и столбцов таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой, задающие цвета, в которые должны быть окрашены клетки:

0 — клетка может в итоге быть любого цвета

1 — клетка должна быть синей

2 — клетка должна быть желтой

3 — клетка должна быть зеленой

Выходные данные
Выведите одно число — количество различных правильных таблиц, в которых нужные клетки покрашены в нужный цвет. Обратите внимание, что если два или более способов раскраски столбцов и строк таблицы приводят к одинаковой раскраске самой таблицы, то это нужно считать как один вариант раскраски таблицы (см. пример 2).

Обход в глубину Обход в ширину Способы задания графа

✓ 1✗ 6—Войти и решать

Возрастающие пути#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средняяВойти и решать

Транзитный путь#38585

Вам дано дерево с N вершинами. Здесь дерево - это разновидность графа, а точнее, связный неориентированный граф с N−1 ребром, где N - количество его вершин. I-е ребро (\(1<=i<=N-1\)) соединяет вершины a_i и b_i и имеет длину c_i.
Вам также дано Q запросов и целое число K. Для каждого j-го запроса (\(1<=j<=Q\)) найдите длину кратчайшего пути от вершины x_j к вершине y_j через вершину K.

Входные данные
В первой строке записано целое число N (\(3<=N<=10^5\)). В следующих N строках записаны вершины a_i и b_i (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\)) и длина между ними c_i(\(1<=c_i<=10^9\), \(1<=i<=N-1\))
Далее идут два числа Q и K (\(1<=Q<=10^5\), \(1<=K<=N\)). В последних Q строках записаны целые числа x_j, y_j(\(x_j \neq y_j\),\(x_j \neq K\), \(y_j \neq K\) \(1<=j<=Q\), ).
Заданный граф является деревом.

Выходные данные
Выведите ответы на запросы в Q строках. В j-й строке выведите ответ на j-й запрос.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1 2 1 1 3 1 2 4 1 3 5 1 3 1 2 4 2 3 4 5	3 2 4	Кратчайшие пути для трех запросов следующие: Запрос 1: Вершина 2 → Вершина 1 → Вершина 2 → Вершина 4: Длина 1 + 1 + 1 = 3 Запрос 2: Вершина 2 → Вершина 1 → Вершина 3: Длина 1 + 1 = 2 Запрос 3: Вершина 4 → Вершина 2 → Вершина 1 → Вершина 3 → Вершина 5: Длина 1 + 1 + 1 + 1 = 4
2	7 1 2 1 1 3 3 1 4 5 1 5 7 1 6 9 1 7 11 3 2 1 3 4 5 6 7	5 14 22	Путь для каждого запроса должен проходить через вершину K = 2.
3	10 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 1 1 9 10	17000000000

Алгоритмы на графах Кратчайшие пути в графе Обход в ширину

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

Гномы и Одинокая гора#30710

Гномы продолжают искать золото предков в недрах Одинокой горы. Недра Одинокой горы представляют собой n пещер, некоторые из которых соединены двусторонними переходами. При этом из каждой пещеры в любую другую можно попасть по переходам, причем это можно сделать единственным способом.

Гномы разделились на два отряда, которые начали свои поиски с пещер u₀ и v₀, соответственно. Гномы каждого из отрядов перемещаются вместе. На обследование пещеры у отряда гномов уходит ровно одна минута, после чего каждый отряд быстро перемещается по переходу в одну из соседних пещер. При этом гномы никогда не заходят в пещеру, если они или другой отряд в ней уже побывали. Оба отряда никогда не заходят в одну и ту же пещеру. Если хотя бы один из отрядов гномов не может переместиться в соответствии с этими правилами, оба отряда сразу прекращают поиски сокровищ.

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

Формат входных данных
В первой строке число n (2 ≤ n ≤ 200 000) — число пещер в Одинокой горе. В следующих n−1 строках заданы переходы между пещерами. В каждой строке записаны номера двух пещер v и u, соединенных переходом (1 ≤ v, u ≤ n). В следующей строке заданы номера пещер v₀ и u₀, в которых исходно находятся два отряда гномов (1 ≤ v₀, u₀ ≤ n, v₀ != u₀).

Формат выходных данных
Выведите максимальное число минут, которое могут продолжаться поиски сокровищ.

Ввод	Вывод	Пояснение
6 1 2 2 3 3 4 4 5 5 6 4 5	2
8 1 2 2 3 3 4 2 5 5 6 3 7 7 8 1 8	4

Деревья Обход в глубину Применение обхода в глубину

✓ 1✗ 1—Войти и решать

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средняяВойти и решать

Мишина машина (В', В)#23371

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

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

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

Помогите Мише найти самый выгодный маршрут.

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

В первой строке содержатся два целых числа n и m количество городов и дорог соединяющих города в стране соответственно (1 <= n <= 10⁵, 0<= m <= 10⁵)

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

Гарантируется, что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов. Вершины нумеруются с единицы.

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

Выведите одно число максимальное количество монет которое Миша сможет получить.

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

Замечание

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

Кратчайшие пути в графе Обход в ширину Способы задания графа

✓ 22✗ 49900средняяВойти и решать

Milk Visits#90046

Фермер Джон построил \(N\) (\(1 \leq N \leq 10^5\)) ферм, соединённых \(N-1\) дорогами, формируя дерево (то есть, каждая ферма достижима от любой другой, и отсутствуют циклы). Каждая ферма содержит коров, чья марка Guernsey или Holstein.

\(M\) друзей ФД (\(1 \leq M \leq 10^5\)) часто посещают его фермы. Во время визита друга \(i\), ФД идёт с эти другом по уникальному маршруту от фермы \(A_i\) до фермы \(B_i\) (возможен случай, когда \(A_i = B_i\)). Дополнительно они могут попробовать некоторое количество молока вдоль пути, по которому они идут. Поскольку большинство друзей ФД сами фермеры, у них есть сильные предпочтения по молоку. Некоторые из его друзей пьют молоко только коров Guernsey, а оставшиеся пьют только молоко Holstein. Любой из друзей ФД будет счастлив только если он сможет попить предпочитаемое молоко во время визита.

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

ОЦЕНИВАНИЕ:

Тесты 2-5 удовлетворяют \(N\le 10^3, M\le 2\cdot 10^3.\)

ФОРМАТ ВВОДА (файл milkvisits.in):

Первая строка содержит два целых числа \(N\) и \(M\).

Вторая строка содержит строку длину длины \(N\). \(i\)-ый символ строки есть 'G' если корова на \(i\)-ой ферме Guernsey, или 'H', если корова на \(i\)-ой ферме Holstein.

Каждая их следующих \(N-1\) строк содержит два целых числа \(X\) и \(Y\) (\(1 \leq X, Y \leq N\)), указывающих, что существует дорога между фермами \(X\) и \(Y\).

Последующие \(M\) строк содержат целые числа \(A_i\), \(B_i\) и символ \(C_i\). \(A_i\) и \(B_i\) представляют конечные точки пути \(i\)'-го друга, а \(C_i\) либо G либо H - тип молока, предпочитаемый \(i\)-ым другом.

ФОРМАТ ВЫВОДА (файл milkvisits.out):

Выведите двоичную строку длины \(M\). \(i\)-ый символ строки должен быть '1' если \(i\)-ый друг будет счастлив, или '0' в противном случае.

графы Деревья Поиск компонент связности

—Войти и решать

New Barns#90007

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

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

ФД имеет \(Q\) (\(1 \leq Q \leq 10^5\)) запросов, каждый вида "построить" или "расстояние". Для запроса "построить" ФД строит амбар и соединяет его не более чем с одним из имеющихся амбаров. На запрос "расстояние" ФД спрашивает у Вас от определённого амбара до самого дальнего амбара достижимого от этого амбара по некоторой последовательности дорожек. Гарантируется, что амбар запроса уже построен. Ответьте на запросы ФД.

ФОРМАТ ВВОДА (файл newbarn.in):

Первая строка содержит целое число \(Q\). каждая из последующих \(Q\) строк содержит запрос. Каждый запрос имеет вид "B p" или "Q k", соответственно построить амбар и соединить его с амбаром \(p\) или вывести дальнейшее расстояние по условию задачи от амбара \(k\). Если \(p = -1\), то новый амбар не соединяется ни с каким из старых. Иначе \(p\) - номер амбара в порядке построения. Амбары нумеруются от \(1\), т.е. Первый построенный амбар будет иметь номер \(1\), второй - \(2\), и т.д.

ФОРМАТ ВЫВОДА (файл newbarn.out):

Выведите по одной строке для каждого запроса "расстояние". Заметим, что амбар, который не соединён ни с одним из других амбаров имеет самое дальнее расстояние \(0\).

Двоичные подьемы Наименьший общий предок

—Войти и решать

Island Travels#89883

Фермер Джон отвез саоих коров на океан. Коровы живут на N (1<=N<=15) островах, которые расположены на решетке R x C (1 <= R, C <= 50). Остров - это максимальная связная группа квадратов на решетке, помеченная символами 'X', где два 'X' связны, только если они имеют общую сторону. Квадраты имеющие общий угол, не обязательно связны.
Беси опоздала, она прилетела с ФД на вертолете. Она может приземлиться на любом острове. Она хочет посетить все N островов хотя бы один раз.
Вокруг островов находится мелководье (обозначено буквой 'S'). Беси может плыть по нему в четырех направлениях (север, юг, запад, восток) для того, чтобы путешествовать между островами. Она также может путешествовать между островом и мелководьем и наоборот.
Определите минимальное расстояние, которое Беси должна проплыть, чтобы посетить все острова (гарантируется, что это возможно). Расстояние, которое проплывет Беси, равно количеству различных раз, когда Беси посетит клеточку 'S'.
PROBLEM NAME: island
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: R и C.
* Строки 2..R+1: Строка i+1 содержит C символов, определяющих i-ую строку решетки. Глубокая вода обозначена '.', острова 'X', мелководье 'S'.
Формат выходных данных
* Строка 1: Одно целое число, представляющее минимальное расстояние, которое должна проплыть Беси, чтобы посетить все острова.
Примечание
Бэси может проплыть от левого верхнего сотрова к среднему, проплыв 1 клеточку, а затем от среднего острова к правому нижнему, проплыв 2 клеточки - всего 3.

графы Минимальный каркас Обход в ширину

—Войти и решать

Tractor#89878

Одно из полей Фермера Джона весьма холмисто. И он хочет купить новый трактор для работы на этом поле. Поле описывается решеткой из N x N (1 <= N <= 500) неотрицательных целых высот ячеек. Трактор может перемещаться из ячейки в соседнюю (на один шаг на север, юг, запад или восток), с разницей их высот D ровно за D единиц денег.
ФД хочет заплатить достаточно, так чтобы его трактор, начиная с некоторой ячейки поля мог посетить как минимум половину ячеек поля. Если число ячеек в поле - нечетное, то половина, округленная вверх.
Определите минимальную стоимость покупки трактора способного выполнить эту задачу.

PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка содержит N разделенных одиночными пробелами неотрицательных целых чисел (каждое не более миллиона), определяющих строку поля ФД.
Формат выходных данных
* Line 1: Минимальная стоимость трактора, который способен объехать не менее половины этого поля.
Примечание
Трактор стоимостью 3 способен перемещаться из ячейки с высотой 0 в ячейку с высотой 3. Поэтому он может посетить все ячейки с высотами 0 и 3. Вместе они представляют не менее половины фермы.

Бинарный поиск по ответу Обход в ширину Поиск компонент связности

—Войти и решать

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

Задан ориентированный ациклический граф с \(n\) вершинами и \(m\) ребрами. Также задана перестановка вершин графа. Необходимо проверить, является ли данная перестановка топологической сортировкой.

В первой строке даны два числа \(n\) и \(m\) — количество вершин и ребер в графе соответственно (\(1 \leq n, m \leq 10^5\)). В следующих \(m\) строках заданы пары чисел \(u_i, v_i\), означающие, что в графе есть ребро из вершины \(u_i\) в вершину \(v_i\). В последней строке задана перестановка из \(n\) элементов.

Выведите "YES" (без кавычек), если данная перестановка является топологической сортировкой и "NO" в противном случае.

Применение обхода в глубину Топологическая сортировка

✓ 3✗ 1—Войти и решать

Кластеры роботов - 2#62562

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Известно, что \(i\)-й робот соединен с \(k_i\) другими роботами с номерами \(v_{i,1}, \ldots, v_{i,k_i}\). Провода двухсторонние, то есть если \(i\) связан с \(j\), то \(j\) связан с \(i\) (иными словами, \((i, j)\) и \((j, i)\) — это один и тот же провод).

Вы находитесь рядом с роботом номер \(n\). Роботом номер \(t\) можно управлять, если он связан с \(n\)-м некоторой цепочкой проводов, то есть

либо если \(t = n\);
либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = n\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с \(n\)-м проходила через \(x\)-й.

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

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \leq n \leq 10^5\)) — количество роботов.

Затем следуют \(n\) строк, в \(i\)-й из которых записаны числа \(k_i\) (\(0 \le k_i \le n - 1\)) и \(v_{i,1}, \ldots, v_{i,k_i}\) (\(1 \le v_{i,j} \le n\); \(v_{i,j} \neq i\)) — количество проводов, подключенных к \(i\)-му роботу, и номера роботов на противоположных концах этих проводов. Гарантируется, что данные корректны: никакие два провода не соединяют одну и ту же пару роботов, и если \(j \in v_i\), то \(i \in v_j\).

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма количества проводов по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

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

В следующих \(k\) строках выведите сами описания действий в формате <<\(y\) + \(t\) - \(x\)>> (\(1 \leq t, x, y \leq n\); \(x \neq y\)). Каждая такая строка соответствует замене провода \((t, x)\) на провод \((t, y)\).

Если возможных ответов несколько, выведите любой. Обратите внимание, что \(k\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.

Деревья Жадный алгоритм Конструктив Обход в глубину

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

Кластеры роботов#62485

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Всего на производстве \(m\) проводов и \(i\)-й из них сейчас соединяет роботов с номерами \(a_i\) и \(b_i\).

Вы находитесь рядом с роботом номер \(1\). Роботом номер \(t\) можно управлять, если он связан с первым некоторой цепочкой проводов, то есть

либо если \(t = 1\);
либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = 1\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Первая строка каждого набора входных данных содержит целые числа \(n\) и \(m\) (\(1 \leq n \leq 10^5\); \(0 \leq m \leq 1.5 \cdot 10^5\)) — количество роботов и количество проводов, соответственно.

В следующих \(m\) строках дано описание проводов: в \(i\)-й строке даны целые числа \(a_i\) и \(b_i\) (\(1 \leq a_i, b_i \leq n\); \(a_i \neq b_i\)) — номера роботов, соединенных \(i\)-м проводом. Гарантируется, что никакие два провода не соединяют одну и ту же пару роботов.

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма \(m\) по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

В следующих \(k\) строках выведите сами описания действий по одному на каждой строке. Описание действия должно состоять из трех целых чисел \(t\), \(x\) и \(y\) (\(1 \leq t, x, y \leq n\); \(x \neq y\)), означающих, что робот номер \(t\) меняет провод \((t, x)\) на провод \((t, y)\).

Деревья Жадный алгоритм Конструктив Обход в глубину

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

Есть ли цикл? - Флойдом#60158

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

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

В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Алгоритм Флойда Обход в глубину

✓ 113✗ 71500лёгкаяВойти и решать

Свинки-копилки#56020

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

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

Входные данные
В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

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

Примечание
Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.
Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.

Обход в глубину Способы задания графа

✓ 2✗ 1—Войти и решать

Левый лабиринт#55694

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

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

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

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

Входные данные
Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

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

Алгоритм Дейкстры Динамическое программирование на таблицах Обход в ширину

✓ 1✗ 0—Войти и решать

Водостоки#55551

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

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

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

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

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

Входные данные
Во входном файле записаны сначала числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).

Выходные данные
В выходной файл выведите минимальное количество водостоков, которое необходимо построить.

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

✓ 2✗ 0—Войти и решать

Вырезанные фигуры#55548

Эпидемия гриппа не обошла стороной семиклассника Алешу. Скучая дома, Алеша решил вырезать фигурки из листа клетчатой бумаги. Лист состоял из M строк и N столбцов клеточек. Сначала Алеша нарисовал на листе границы фигур. Количество фигур было не меньше 2. Чтобы фигуры получались ровными, границы фигур Алеша рисовал строго по линиям имеющейся клеточной разметки листа (при этом некоторые границы фигур могли пройти по границам листа). Форма фигур могла быть любой, но при этом все фигуры были связными (фигура называется связной, если из любой ее клетки можно добраться до любой другой, ходя только по клеткам фигуры и перемещаясь каждый раз в одну из 4-х соседних по стороне клеток). Никакие две фигуры не имели общих точек, в том числе не касались углами клеток.

<>Затем Алеша вырезал нарисованные фигуры, делая разрезы только по их границам. При этом оставшаяся часть листа осталась связной (то есть не распалась на несколько частей).
Лист с вырезами Алеша отсканировал. Сканер в своей памяти по результатам сканирования построил таблицу, состоящую из нулей и единиц, из M строк и N столбцов (строки нумеруются сверху вниз от 1 до M, столбцы — слева направо от 1 до N). Каждый элемент таблицы соответствовал клеточке исходного листа. Единица обозначала, что соответствующая клетка листа осталась на месте, ноль — соответствующая клетка была вырезана.

На рис. 1 приведен пример клетчатого листа, а на рис. 2 — соответствующая ему таблица в памяти сканера:

Рис 1.
Исходный клеточный лист с вырезанными фигурами
Размер листа: M=6, N=12.
Количество вырезанных фигур: 3

1	1	1	1	1	1	1	1	1	1	1	1
1	0	0	1	1	1	0	0	0	0	0	1
1	0	0	1	1	1	1	0	0	1	1	1
1	1	1	1	1	0	0	0	0	0	1	1
1	1	0	0	1	1	1	0	1	0	1	1
1	1	0	0	1	1	1	1	1	1	1	1

Рис 2.
Такая таблица строится в памяти сканера

После этого сканер представил полученную таблицу в специальном, описанном ниже формате и передал информацию на компьютер. Напишите программу, которая по полученной информации установит:
Пункт 1. Сколько клеток было вырезано из листа?
Пункт 2. Сколько фигур было вырезано? Описание формата представления таблицы Последовательность подряд идущих по горизонтали или вертикали единиц будем называть полосой. Полосу можно задаеть 4 числами:

направление (0—горизонтальная, 1—вертикальная)
(i, j) — координаты начальной клетки полосы (начальной является самая левая клетка для горизонтальной полосы, и самая верхняя — для вертикальной), i — номер строки клетки, j — номер столбца
d — длина полосы (количество подряд стоящих единиц).

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

В каждой клетке начинается не более одной полосы.
Полосы перечислены в порядке следования их начальных клеток (клетки перечисляются по строкам сверху вниз, в строке — слева направо).
Общее число полос не превышает 256000.

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

Входные данные
Во входном файле записано сначала число P (1 или 2) — номер пункта задачи, ответ на который требуется получить. Далее записаны размеры исходного листа — числа M и N (1 ≤ M ≤ 4000,1 ≤ N ≤ 4000) . Затем записано число K (0 ≤ K ≤ 256000) — количество полос в описании полученной таблицы. Затем идет K четверок чисел, описывающих полосы (полосы перечисляются в порядке начальных клеток полос: по строкам сверху вниз, в строке — слева направо).

Выходные данные
В выходной файл выведите искомое количество (если P=1, то — количество клеток, вырезанных из листа, если P=2, то — количество фигур, вырезанных из листа).

Обход в ширину Способы задания графа

✓ 2✗ 10—Войти и решать

Юный поджигатель#55547

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.

На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:

Спички длины 1 выкладывались по сторонам клеток.
Спички длины выкладывались по диагоналям клеток.

Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке, имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).

Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью). Спичка может гореть в нескольких местах (например, когда она загорается с двух концов; или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается по вновь подожженной спичке в обе стороны).

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

Входные данные
Во входном файле записано сначала число N — количество спичек (1<N<40). Затем идет N пятерок чисел вида X₁, Y₁, X₂, Y₂, T, задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или , все спички образуют связную фигуру, и положение никаких двух спичек не совпадает). Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее 10⁷.

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

Алгоритм Флойда Способы задания графа

✓ 3✗ 8—Войти и решать