Алгоритмы на графах. Задачи для самостоятельного решения

Общая постановка

Решение задач этого раздела предполагает использование известных и разработку новых алгоритмов на графах. Базовые алгоритмы не следует как-то модифицировать, вместо этого лучше грамотно построить граф-модель задачи, чтобы использовать их без изменений.

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

Задачи

Дерево (задача №1)

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

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

В первой строке входного файла записано целое число N — количество вершин в графе ($1 \leq N \leq 100$).

Далее записана матрица смежности графа: N строк по N чисел, каждое из которых — 0 или 1. Гарантируется, что матрица симметрическая и на главной диагонали все элементы нулевые.

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

Выведите Yes, если граф является деревом по одному из эквивалентных определений, и No — в противном случае.

Примеры

Остовное дерево (задача №2)

Задан неориентированный граф без петель и кратных ребер. Требуется построить какое-либо остовное дерево этого графа или сообщить, что его не существует.

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

В первой строке входного файла записано целое число N — количество вершин в графе ($1 \leq N \leq 100$).

Далее записана матрица смежности графа: N строк по N чисел, каждое из которых 0 или 1. Числа разделяются одиночными пробелами. Гарантируется, что матрица симметрическая, все элементы на главной диагонали нулевые.

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

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

Примеры

Наибольшее число маршрутов, не пересекающихся по ребрам (задача №3)

Задан граф. Необходимо найти наибольшее число не пересекающихся по ребрам маршрутов между заданными вершинами $\upsilon$ и $\omega$.

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

Первая строка содержит число N вершин и число М ребер графа ($1 \leq N \leq 100, 0 \leq M \leq 4\ 950$). Вершины графа пронумерованы целыми числами от 1 до N.

Каждая из следующих N строк файла задает множество вершин графа, смежных с очередной вершиной. Так, ($i + 1$)-я строка файла содержит вершины, смежные с вершиной i, последним в строке идет число 0 (если нет вершин, смежных с некоторой вершиной графа, то соответствующая строка содержит только число 0).

В последней строке файла находятся вершины $\upsilon$ и $\omega$. Все числа внутри одной строки разделены одним или несколькими пробелами.

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

В единственной строке выведите наибольшее число не пересекающихся по ребрам маршрутов между вершинами $\upsilon$ и $\omega$.

Лабиринт без пересечений по дорогам (задача №4)

Лабиринт задается матрицей смежности $С$ размера $N \times N$, где $C_{i, j} = 1$, если комната $i$ связана с комнатой $j$ посредством дороги ($i$ и $j$ целые числа от $1$ до $N$). Часть комнат является входами, часть выходами. Входы и выходы задаются наборами комнат $\{X_1, …, X_p\}$ и $\{Y_1, …, Y_k\}$ соответственно. Необходимо найти наибольшее число людей, которых можно провести от входов до выходов таким образом, чтобы их пути не пересекались по дорогам, но могли пересекаться по комнатам.

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

Первая строка содержит размер лабиринта $N$ ($1 \leq N \leq 300$), число входов $p$ и число выходов $k$. Ни одна из комнат не является одновременно и входом, и выходом.

Затем идут $N$ строк, которые содержат матрицу  смежности $C$ (каждой строке матрицы соответствует строка входного файла). Следующая строка содержит $p$ различных чисел — номера входов. Последняя строка содержит $k$ различных чисел — номера выходов. Комнаты нумеруются от $1$ до $N$.

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

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

Шестеренки (задача №5)

Каждой из $N$ шестеренок присвоен номер: число от $1$ до $N$. Задано $M$ соединений пар шестеренок в виде $\{i,\ j\}$ (шестеренка с номером $i$ находится в зацеплении с шестеренкой с номером $j$).

Необходимо определить, какое наименьшее число шестеренок нужно удалить, чтобы первая пришла в движение. Если таких вариантов несколько, то нужно выбрать тот, при котором вращаться будет наибольшее число шестеренок.

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

Первая строка содержит два числа, записанных через пробел: число $N$ шестеренок и число $M$ соединений пар ($0 \leq N \leq 10,\ 0 \leq M \leq 45$). Затем идут $M$ строк файла, каждая из которых задает пару $\{i,\ j\}$ соединенных шестеренок ($1 \leq i \lt j \leq N$).

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

Если первая шестерёнка пришла в движение без удаления других
шестерёнок, то в первой строке выведите Yes, а через пробел укажите число шестерёнок, которые пришли при этом в движение; во второй строке укажите (через пробел) номера шестерёнок, которые пришли в движение (в порядке возрастания их номеров).

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

Открытки и конверты (задача №6)

Имеется $N$ прямоугольных конвертов и $N$ прямоугольных открыток различных номеров. Необходимо определить, можно ли разложить все открытки по конвертам, чтобы в каждом конверте было по одной открытке. Открытки нельзя складывать, сгибать и т.п., но можно помещать в конверт под углом. Например, открытка с размерами сторон $5 \times 1$ помещается в конверты с размерами $5 \times 1$, $6 \times 3$, $4.3 \times 4.3$, но не входит в конверты с размерами $4 \times 1$, $10 \times 0.5$, $4.2 \times 4.2$.

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

Первая строка содержит число $N$ — число открыток (конвертов) ($1 \leq N \leq 500$). Затем идут $N$ строк, каждая из которых содержит два действительных числа, задающих размеры очередной открытки. Затем следуют $N$ строк файла, каждая из которых содержит два действительных числа, задающих размеры очередного конверта. Все числа положительны, не превосходят $1\ 000$ и записаны с не более чем одним знаком после точки.

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

Если все открытки можно разложить, то единственная строка файла должна содержать сообщение YES. Если все открытки нельзя разложить, то первая строка выходного файла должна содержать сообщение NO, а вторая — наибольшее число открыток, которые можно разложить по конвертам.

Пример

Разбиение на команды по численности (задача №7)

Необходимо определить, можно ли разбить $N$ студентов на две команды, численность которых отличается не более чем в два раза, если известно, что в каждой команде любых два студента должны быть знакомы друг с другом. Круг знакомств задается матрицей $A$ размера $N \times N$ с элементом $A_{i,\ j}$, равным $1$, если $i$-й студент знаком со студентом $j$, и элементом $A_{i,\ j}$, равным $0$, если $i$-й студент не знаком со студентом $j$.

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

Первая строка содержит число $N$ студентов ($1 \leq N \leq 1\ 000$). Затем идут $N$ строк, которые задают матрицу $A$ знакомств (каждой строке матрицы соответствует отдельная строка входного файла, числа в строках разделены пробелами).

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

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

Если нельзя разбить студентов на две команды, численность которых отличается не более чем в два раза, то единственная строка файла должна содержать сообщение NO.

Примеры

Разбиение на группы незнакомых (задача №8)

Имеется $N$ человек и матрица $A$ размера $N \times N$. Элемент $A_{ij}$ матрицы равен $1$, если человек $i$ знаком с человеком $j$ (если $i$-й человек знает $j$-го, то считаем, что и $j$-й человек знает $i$-го), и элемент $A_{ij}$ матрицы равен $0$, если $i$-й человек не знаком с человеком $j$. Можно ли разбить людей на две группы, чтобы в каждой группе были только незнакомые люди (в каждой группе должен быть хотя бы один человек)?

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

Первая строка содержит число $N$ людей ($2 \leq N \leq 500$). Затем идут $N$ строк файла, которые задают матрицу $A$ знакомств (каждой строке матрицы соответствует отдельная строка входного файла, числа в строках разделены пробелами).

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

Если можно разбить людей на две группы, чтобы в каждой группе были только незнакомые люди, то выведите в первой строке YES, а во второй — номера людей (люди нумеруются от $1$ до $N$), которые попали в одну из групп. Числа в строке упорядочены по возрастанию. Если разбить нужным образом нельзя, то выведите NO.

Примеры

Олимпиада (задача №9)

На олимпиаду прибыли $N$ человек. Некоторые из них знакомы между собой. Круг знакомств задан матрицей $А$ размера $N \times N$. Элемент $A_{ij}$ матрицы равен $1$, если человек $i$ знаком с человеком $j$ (если $i$-й человек знает $j$-го, то значит, что $j$-й человек знает $i$-го), и элемент $A_{ij}$ равен $0$, если $i$-й человек не знаком с человеком $j$.

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

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

Первая строка содержит число $N$ людей ($2 \leq N \leq 500$). Затем идут $N$ строк файла, которые задают матрицу знакомств $A$ (каждой строке матрицы соответствует отдельная строка входного файла).

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

Если можно опосредованно перезнакомить всех прибывших на олимпиаду между собой, то первая строка файла будет содержать сообщение YES; в противном случае строка файла должна содержать сообщение NO.

Примеры

Книга (задача №10)

Группа состоит из $N$ человек. В ней каждый имеет ровно $\frac{N}{2}$ друзей. Отношение дружбы симметрично (если $А$ друг $Б$, то и $Б$ друг $А$). У одного человека в группе (его номер $Х$) есть книга, которые все хотели бы прочитать и обсудить.

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

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

Первая строка файла содержит три числа $N$, $K$, $X$, где $N$ — число человек в группе, $K = \frac{N}{2}$ — число друзей у каждого человека, $X$ — номер обладателя книги ($2 \leq N \leq 1\ 000,\ 1 \leq X \leq N$).

Следующие $N$ строк содержат по $K$ различных чисел — номера друзей для $1$-го, $2$-го, …, $N$-го человека соответственно. Гарантируется, что в списке друзей $i$-го человека он сам (число $i$) не упоминается.

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

Выведите последовательность номеров людей в том порядке, в котором может осуществляться передача книги (первый и последний элементы этой строки должны соответствовать владельцу книги).

Пример

Станки (задача №11)

Конвейер состоит из $N$ различных станков. Есть $N$ рабочих. Известна матрица $С$ размера $N \times N$, где элемент $c_{ij}$ задает производительность $i$-го рабочего на $j$-м станке.

Необходимо определить, каким должно быть распределение рабочих по станкам (каждый рабочий может быть назначен только на один станок, на каждом станке может работать только один рабочий), чтобы производительность всего конвейера была максимальной. Производительность конвейера при некотором распределении рабочих по станкам равна минимальной производительности рабочих на назначенных им на конвейере станках.

Если решение не единственно, вывести решение, первое в лексикографическом порядке среди всех решений.

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

Первая строка содержит число рабочих (станков) $N$ ($1 \leq N \leq 500$). Затем идут $N$ строк файла, которые задают матрицу $C$ производительностей ($1 \leq c_{ij} \leq 1\ 000$).

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

В первой строке выведите максимальную возможную производительность конвейера. Во второй строке — номера станков, на которые должны быть распределены рабочие $1,\ 2,\ …,\ N$ соответственно.

Встреча (задача №12)

В городе $N$ домиков и $M$ дорог. В каждом домике живет по одному человеку. Необходимо найти точку (место встречи всех людей), от которой суммарное расстояние по дорогам до всех домиков будет минимальным. Место встречи следует искать среди точек, в которых расположены домики, а также точек, лежащих на дорогах и отстоящих от домиков на целое число единиц длины.

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

Первая строка содержит число $N$ домиков ($1 \leq N \leq 100$) и число $M$ дорог ($0 \leq M \leq N \times \frac{N — 1}{2}$). Домики пронумерованы числами от $1$ до $N$.

Затем идут $M$ строк файла, по три целых числа в каждой, задающие дороги: номера $u$ и $v$ домиков ($1 \leq u,\ v \leq N$), которые являются концами дороги, и длина $\omega$ дороги ($1 \leq \omega \leq 100\ 000$).

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

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

Если точка встречи лежит на дороге, то выведите три целых числа: номера конечных домиков дороги и расстояние от первого из них до этой точки.

Если точка совпадает с домом, то выведите его номер и суммарное расстояние от всех домиков до него.

Гарантируется, что решение существует. Если решений несколько, то выведите любое.

Замечание

В первом примере ответ «6 37» также будет считаться верным.

Янка (задача №13)

Янка положил на стол $N$ выпуклых $K$-гранников и $N$ различных типов наклеек по $K$ штук каждая. Ночью кто-то наклеил наклейки на грани, по одной на грань (на одном и том же многограннике могло оказаться несколько наклеек одного типа). Янке необходимо расставить многогранники так, чтобы наклейка каждого типа была видна ровно $K — 1$ раз (наклейка не видна, если она расположена на грани, на которой стоит многогранник). Предполагается, что такая расстановка всегда существует.

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

Первая строка содержит два целых числа: $N$ ($1 \leq N \leq 500$) и $K$ ($1 \lt K \leq 100$).

Затем идут $N$ строк файла по $K$ чисел в каждой. Каждая строка соответствует одному $K$-граннику и содержит номера наклеек, которые наклеены на $1$-ую, $2$-ую, …, $K$-ую грани данного многогранника соответственно.

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

Выведите в одну строку искомую расстановку: $i$-й элемент этой строки — номер наклейки на $i$-м многограннике, на которую его поставили (в результате в этой строке каждый тип из $N$ типов наклеек встретится ровно один раз). Числа в строке разделены одним пробелом.

Пример

Второй по длине маршрут (задача №14)

Задано $N$ городов с номерами от $1$ до $N$ и сеть из $M$ дорог с односторонним движением между ними. Каждая дорога определяется тройкой ($i,\ j,\ k$) натуральных чисел, где $i$ — номер города, в котором дорога начинается, $j$ — номер города, в котором дорога заканчивается, а $k$ — ее длина. Дороги друг с другом могут пересекаться только в конечных городах.

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

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

Первая строка содержит два целых числа $N$ и $M$ ($1 \leq N \leq 10\ 000,\ 1 \leq M \leq 100\ 000$). Затем идут $M$ строк файла по три числа в каждой: $i,\ j,\ k$. Последняя строка содержит номера городов $A$ и $B$.

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

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

Пример

Четно-нечетная магистраль (задача №15)

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

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

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

Первая строка содержит число $N$ городов ($1 \leq N \leq 300$). Следующие $N$ строк файла задают магистрали: ($i + 1$)-я строка содержит номера городов, которые связаны напрямую с городом $i$ (если таких городов нет, то строка содержит нуль; числа в строке разделены пробелами).

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

Если система магистралей является четно-нечетной, то выведите единственную строку YES. В противном случае в первой строке выведите NO, а во второй — мощность описанного наибольшего подмножества.

Примеры

Пересекающиеся дороги (задача №16)

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

Необходимо найти кратчайший маршрут машины от перекрестка $I$ до перекрестка $J$, если на перекрестке машина должна выждать время, равное числу пересекающихся дорог (для начального и конечного перекрестков маршрута ожидание не требуется). Движение по дороге возможно в обоих направлениях.

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

В первой строке находятся два числа: $N$ ($1 \leq N \leq 10\ 000$) и $K$ ($1 \leq K \leq 100\ 000$). Во второй строке заданы номера $I$ и $J$ перекрестков, между которыми надо найти кратчайший маршрут.

Каждая из следующих $K$ строк содержит по три числа (через пробел): номера перекрестков, задающих очередную дорогу, и время, требующееся на проезд по этой дороге (это число является неотрицательным и не превосходит $100\ 000$). Между любыми двумя перекрестками — не более одной дороги.

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

Выведите в первой строке минимальное время, а во второй — номера перекрестков при движении от перекрестка $I$ до перекрестка $J$, соответствующие найденному кратчайшему маршруту. Гарантируется, что маршрут между заданными перекрестками существует.

Пример

Домики (задача №17)

На прямоугольном участке расположены $N$ домиков. Левый нижний угол участка имеет координаты $(0, 0)$, а правый верхний — $(100, 100)$. Местоположение каждого домика задается целочисленными координатами его нижнего левого угла. Каждый домик имеет размер $5 \times 5$ м. Стороны домиков параллельны сторонам участка. Домики отстоят друг от друга не менее чем на 1 м. Необходимо найти один из кратчайших путей от точки $(0, 0)$ до точки $(100, 100)$. При движении можно затронуть только стены домиков. Найденный путь представить в виде координат концов прямолинейных отрезков, составляющих этот путь.

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

Первая строка содержит число $N$ домиков ($0 \leq N \leq 30$). Следующие $N$ строк содержат координаты домиков: ($i+1$)-я строка задает координаты левого нижнего угла $i$-го домика.

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

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

Пример

Хакеры (задача №18)

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

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

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

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

Первая строка содержит число $N$ ЭВМ в сети ($1 \leq N \leq 100\ 000$). Каждая из следующих $N$ строк содержит число $T_i$ терминалов у машины с номером $i$ ($1 \leq T_i \leq 1\ 000$).

Далее идут $K$ строк (список прав на запрос) по два числа в каждой: $A_j$ и $B_j$ — номера машин, соединённых между собой. Каждая пара ($A_j$, $B_j$) означает, что ЭВМ с номером $A_j$ имеет право запрашивать информацию, которая имеется у ЭВМ с номером $B_j$ ($A_j \neq B_j$). Пары не повторяются. Завершает файл строка, содержащая два нуля.

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

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

Пример

Пирамида Хеопса (задача №19)

Внутри пирамиды Хеопса имеется $N$ комнат, в которых установлены $2M$ модулей, составляющих $M$ устройств. Каждое устройство включает два модуля, располагающихся в разных комнатах, и предназначено для перемещения между парой комнат, в которых установлены эти модули. Перемещение происходит за $0.5$ условных единиц времени.

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

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

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

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

В первой строке содержится число $N$ комнат ($2 \leq N \leq 10\ 000$). Во второй строке — число $M$ устройств ($0 \leq M \leq 100\ 000$). В следующих $M$ строках находится информация об устройствах. Каждая строка содержит числа $R_{1,i}$, $T_{1, i}$, $R_{2,i}$, $T_{2,i}$ — информация об устройстве $i$:

• $R_{1,i}$ и $R_{2,i}$ — номера комнат, в которых располагаются модули устройств $i$;
• $T_{1,i}$ и $T_{2,i}$ — периоды времени, через которые включаются соответствующие модули ($R_{1,i}$ — в момент времени $T_{1,i}$ и $R_{2,i}$ — в момент времени $T_{2,i}$) ($1 \leq T_{1,i}, T_{2,i} \leq 100\ 000$, целые числа).

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

Первая строка выходного файла содержит оптимальное время (с абсолютной погрешностью не более $0.1$). Во второй строке указана последовательность устройств, которыми надо воспользоваться, чтобы попасть из комнаты $1$ в комнату $N$ за минимальное время. Если решений несколько, выведите любое. Гарантируется, что решение существует.

Пример

Без левых поворотов (задача №20)

План города представляет собой множество перекрестков, которые соединены дорогами (движение по дороге возможно в обоих направлениях). Перекрестки обозначаются точками на плоскости координатами ($x_1, y_1$), ($x_2, y_2$), …, ($x_n, y_n$), а дорогам соответствуют пары $\{i, j\}$, где $i$ и $j$ обозначают номера перекрестков, которые эта дорога соединяет. Каждая дорога является прямолинейным отрезком между соответствующими точками.

Необходимо определить, можно ли проехать от перекрестка $s$ до перекрестка $f$, не совершая левых поворотов, т.е. двигаясь только прямо или вправо. Если ответ положительный, то укажите последовательность перекрестков.

Замечания

1. Если координаты стартовой точки ($x, y$), то направление движения в эту точку происходило из точки с координатами ($x, y\ -\ 1$).
2. Разворачиваться на $180^{\circ}$ в точке запрещено.
3. Дороги пересекаются не обязательно под прямым углом. Например, какая-нибудь дорога может соединять перекрестки с координатами ($1, 0$) и ($2, 2$), а другая — перекрестки с координатми ($1, 0$) и ($1, 1$).

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

В первой строке входного файла находятся числа $N$ и $M$ — число перекрестков и дорог на плане соответственно ($1 \leq N, M \leq 10\ 000$). В каждой из следующих $M$ строк содержится информация о дороге (шесть целых чисел от $-10^9$ до $10^9$ через пробел): сначала указываются координаты перекрестков, которые соединяет дорога, а затем — номера этих перекрестков. В последней строке находятся номера перекрестков $s$ и $f$.

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

Если проехать нельзя, то выходной файл должен содержать единственную строку с сообщением No. В противном случае в первой строке файла нужно вывести сообщение Yes, а во второй — номера перекрестков (через пробел) в той последовательности, в которой по ним проезжали, не совершая левых поворотов (начинается строка с перекрестка $s$ и заканчивается перекрестком $f$).

Примеры

Кратчайший маршрут с дополнительным временем преодоления перекрестка (задача №21)

План города представляет собой множество перекрестков, соединенных дорогами (по дороге разрешено направление в обоих направлениях).

Каждая дорога задается номерами перекрестков, которые она соединяет, и временем движения по ней. Между двумя различными перекрестками может быть не более одной дороги. Дорога не может соединять перекресток сам с собой. Кроме того, время преодоления перекрестка $i$ равно $gk_i$, где $g$ — заданная константа, а $k_i$ — число дорог, подходящих к перекрестку $i$.

Необходимо найти кратчайший по времени маршрут от перекрестка $s$ до перекрестка $f$. Конечный перекресток $f$ преодолевать не надо, а стартовая вершина $s$ маршрута преодолевается как перекресток.

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

В первой строке находятся числа $N$ и $M$ — число перекрестков ($1 \leq N \leq 11\ 000$) и число дорог на плане города ($0 \leq M \leq 100\ 000$) соответственно.

В каждой из следующих $M$ строк файла сначала расположены номера перекрестков, которые связывает очередная дорога, а затем время движения по ней (от $0$ до $1\ 000$).

В последней строке находятся номера перекрестков $s$ и $f$ ($1 \leq s, f \leq N$), а также константа $g$ ($1 \leq g \leq 100$).

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

Если проехать от перекрестка $s$ до перекрестка $f$ можно, в первой строке выведите сообщение Yes, а во второй строке — минимальное время движения. Если проехать нельзя, то в единственной строке выведите сообщение No.

Пример

Железные и шоссейные дороги (задача №22)

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

Стоимость проезда зависит от набора проезжаемых дорог и от способа проезда. Так, если вы подъехали к городу С по шоссейной (железной) дороге $X \rightarrow C$ и хотите ехать дальше по дороге $C \rightarrow Y$ того же типа, то должны уплатить только базовую стоимость проезда по дороге $C \rightarrow Y$. Если тип дороги $C \rightarrow Y$ отличен от типа дороги $X \rightarrow C$, то нужно уплатить базовую стоимость проезда по дороге $C \rightarrow Y$ плюс $10\%$ от базовой стоимости проезда по этой дороге (страховой взнос). При выезде из города А страховой взнос платится всегда.

Необходимо найти стоимость самого дешевого маршрута, если он существует.

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

В первой строке находится целое число $N$ городов ($1 \leq N \leq 1\ 000$). Во второй строке задано целое число $M$ дорог ($0 \leq M \leq 1\ 000\ 000$). В каждой из следующих $M$ строк находятся четыре числа $x, y, t, p$ (разделенные пробелом), где $x$ и $y$ — номера городов, которые соеднияет дорога, $t$ — тип дороги (0 — шоссейная, 1 — железная), $p$ — базовая стоимость проезда по ней ($p$ — действительное число, $0 \leq p \leq 1\ 000$). В последней строке задаются номера А и В начального и конечного городов.

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

Если маршрута не существует, то в единственной строке выведите No. Если же маршрут существует, то в первой строке выведите Yes, а во второй — стоимость проезда по самому дешевому маршруту (с точностью до двух знаков после точки).

Пример

Кратчайший путь в зависимости от направления поворота (задача №23)

Заданы декартовы координаты $N$ перекрестков города, которые пронумерованы числами от $1$ до $N$. На каждом перекрестке имеется светофор. Некоторые перекрестки соединены дорогами с двусторонним (правосторонним) движением, пересекающимися только на перекрестках. Для каждой из $M$ дорог известно неотрицательное время, требуемое для проезда по ней от одного перекрестка до другого.

Необходимо проехать от перекрестка $А$ до перекрестка $В$ за минимальное время.

Время проезда зависит от набора проезжаемых дорог и от времени ожидания на перекрестках. Так, если вы подъехали от перекрестка $Х$ к перекрестку $С$ по дороге $X \rightarrow C$ и хотите ехать дальше по дороге $C \rightarrow Y$, то время ожидания на перекрестке С зависит от того, поворачиваете вы налево или нет. Если вы поворачиваете налево, то время ожидания равно $D \times K$, где $D$ — количество дорог, пересекающихся на перекрестке $C$, а число $K$ — некоторая константа. Если вы не поворачиваете налево, то время ожидания на перекрестке равно нулю. Разворот на перекрестке считается поворотом налево.

Замечание

Если первоначально машина находится на перекрестке с координатами ($x, y$), то предполагается, что она приехала в эту точку из точки с координатами ($x, y\ -\ 1$).

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

В первой строке входного файла находятся натуральные числа $N$, $M$ и $K$ ($N \leq 1\ 000, M \leq 1\ 000, K \leq 1\ 000$).

В каждой из следующих $N$ строк — пара целых чисел $x$ и $y$ (разделенных пробелом), которые задают координаты перекрестка города ($|x|, |y| \lt 1\ 000$).

В каждой из $M$ следующих строк — по три числа $p$, $r$ и $t$ (разделенные пробелами), где $p$ и $r$ — номера перекрестков, которые соединяет дорога, а натуральное число $t$ ($t \leq 1\ 000$) — время проезда по ней.

В последней строке файла находятся номера $A$ и $B$ начального и конечного перекрестков соответственно.

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

Если пути не существует, то единственная строка выходного файла должна содержать сообщение No.

Если путь существует, то в первой строке нужно вывести сообщение Yes, а во второй — натуральное число $t$ — время проезда по самому быстрому маршруту.

Пример

Уличная гонка (задача №24)

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

Назовём план улицы хорошим, если он обладает следующими свойствами:

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

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

Предположим, что гонка проводится на протяжении двух последовательных дней. Для этой цели план должен быть разбит на два «хороших» плана, по одному на каждый день. В первый день стартом является точка $0$, а финишем служит некоторая «точка разбиения». Во второй день старт находится в этой «точке разбиения», а финиш — в точке $N$.

Точка $S$ является «точкой разбиения» для «хорошего» плана $C$, если:

• $S$ отличается от старта и финиша плана $C$;
• план разбивается ею на два «хороших» плана без общих стрелок
  (т. е. между планами нет стрелок, их соединяющих) и с единственной
  общей точкой $S$.

Для заданного «хорошего» плана необходимо:

1. определить множество «неизбежных точек», которые должны
   посетить все участники гонки (за исключением старта и финиша);
2. определить множество всех возможных «точек разбиения».

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

В первой строке задано число $N$ точек ($0 \leq N \leq 50$). Следующие $N$ строк содержат конечные точки стрелок, исходящих соответственно из точек с номерами от $0$ до $N\ -\ 1$. Каждая из этих строк заканчивается числом $-2$.

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

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

Во второй строке — число «точек разбиения» в заданном плане, затем — их номера в порядке возрастания.

Если каких-либо точек нет, то соответствующая строка должна содержать число $0$.

Пример

Прогулка (задача №25)

Хозяин вышел на прогулку с собакой. Известно, что путь хозяина представляет собой ломаную линию, координаты отрезков ломаной заданы: ($X_i, Y_i$), $i = 1, …, N$. Точка ($X_1, Y_1$) — начальная точка ломаной линии, а точка ($X_N, Y_N$) — конечная точка ломаной. Хозяин во время прогулки двигается от стартовой точки по отрезкам ломаной линии и заканчивает путь в конечной точке ломаной. У собаки есть свои любимые места (координаты любимых мест заданы: ($X_j^{‘}, Y_j^{‘}$), $j = 1, …, M$), которые собака хотела бы посетить. В то время как хозяин проходит один отрезок ломаной, собака может посетить только одно из своих любимых мест. В начальной и конечной точке ломаной, собака обязана подбежать к хозяину. Известно, что скорость собаки в два раза выше скорости хозяина.

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

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

Первая строка содержит два числа: $N$ — число точек ломаной (включая начальную и конечную точки пути) и $M$ — число любимых мест собаки ($1 \leq N \leq 100,\ 0 \leq M \leq 100$).

В следующих $N$ строках идут координаты точек ломаной: сначала координата $x$, а затем через пробел — координата $y$ и т.д. (координаты точек ломаной следуют в той последовательности, в которой они соединяются отрезками, начиная от начальной точки и заканчивая конечной).

В следующих $M$ строках  — координаты любимых мест собаки: сначала координата $x$, а затем через пробел — координата $y$ и т.д.

Координаты — целые числа, по модулю не превосходящие $10\ 000$. Все точки попарно различны.

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

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

Пример

Сборка прибора (задача №26)

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

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

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

Первая строка содержит общее число узлов $N$ (узлы пронумерованы от $1$ до $N$, $N \leq 50$).
Вторая строка — номер узла, который надо собрать.
Каждая из следующих $N$ строк файла содержит информацию об отдельном узле: $L$ — его номер, $C$ — количество его комплектующих. Затем в этой же строке идут $C$ чисел, которые задают номера комплектующих узлов для $L$. Разделителем чисел в пределах строки является символ «:» (двоеточие).

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

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

Пример

Скрудж Мак-Дак (задача №27)

Скрудж Мак-Дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта функция довольна сложна. Его мехник делает устройство, вычисляющее эту функцию за несколько этапов с использованием промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется, чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для ее вычисления. Вычисление функции без параметров может производиться в любое время. После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функций такова, что каждая функция вычисляется не более одного раза и любой параметр используется не более одного раза. Любой параметр есть имя функции. Поскольку Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора.

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

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

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

Первая строка содержит общее число $N$ функций ($1 \leq N \leq 10\ 000$). Вторая строка — имя функции, которую необходимо вычислить (имя функции есть натуральное число от $1$ до $N$). Каждая из следующих $N$ строк содержит имя функции, число параметров и список имен параметров.

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

В первой строке выведите минимальное число ячеек памяти, во второй — последовательность вычисления функций.

Пример

Заправочные станции (задача №28)

Имеется $N$ городов, соединенных $M$ двусторонними дорогами. Для каждой дороги задана ее протяженность в километрах. Машина может поворачивать (изменять направление движения) только в городах. Машина имеет бак вместимостью $Z$ литров бензина. и для нее задан расход бензина $X$ литров на один километр.

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

Необходимо определить самый дешевый маршрут из города $A$ в город $B$, если первоначально бак машины полон.

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

В первой строке записаны два целых числа $N$ ($2 \leq N \leq 300$) и $M$ ($1 \leq M \leq 5\ 000$).
Во второй строке заданы два целых числа $Z$ ($1 \leq Z \leq 10\ 000$) и $X$ ($1 \leq X \leq 100$).
В третьей строке указаны числа $A$ и $B$ ($1 \leq A, B \leq N$ и $A \neq B$).

Далее строка из $N$ неотрицательных целых чисел, $i$-е число — стоимость $S_i$ дозаправки ($1 \leq S_i \leq 10\ 000$) или число $0$, если в этом городе заправки нет.

Далее $M$ строк занимают описания каждой дороги: первые два числа — номера городов, связанных двусторонней дорогой, и третье число — ее протяженность в километрах (целое число от $1$ до $10\ 000$).

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

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

Пример

Слова (задача №29)

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

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

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

Например, для последовательности слов

terminator, department, epic, cat, rapid, toothpaste

требуемая цепочка слов имеет вид

cat $\rightarrow$ terminator $\rightarrow$ rapid $\rightarrow$ department $\rightarrow$ toothpaste $\rightarrow$ epic

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

В первой строке находится число $N$ слов (от $1$ до $131\ 000$). Следующие $N$ строк содержат слова (по одному слову в каждой строке). Слова состоят из строчных букв английского алфавита. Размер входного файла не превосходит одного мебибайта.

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

Если цепочку нельзя составить, то выведите сообщение No. Если цепочку можно составить из всех слов, то в первой строке выведите сообщение Yes, а далее — непосредственно саму цепочку (по одному слову в строке).

Пример

Цепочка из домино (задача №30)

На столе выложены доминошки. Доминошка состоит из двух частей, и на каждой части изображено некоторое число точек (от $0$ до $6$). Доминошки могут выкладываться в ряд одна за другой по следующему правилу: число точек на примыкающих частях соседних в ряду доминошек должна совпадать.

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

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

В первой строке находится число $N$ доминошек ($2 \leq N \leq 10\ 000$). Следующие $N$ строк содержат данные о доминошках (два числа через пробел): число точек на верхней и нижней частях доминошки.

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

Если можно составить цепочку из всех доминошек, то первая строка файла должна содержать сообщение Yes.

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

Пример

Степенная последовательность (задача №31)

Назовем степенной последовательностью неориентированного графа $G\ =\ (V,\ E)$ упорядоченный по невозрастанию список степеней его вершин.

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

По заданному графу постройте его степенную последовательность.

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

В первой строке записаны два целых числа $N$ и $M$ — число вершин ($1 \leq N \leq 100\ 000$) и число ребер графа ($1 \leq M \leq 100\ 000$).

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

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

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

Пример

Отрезки (задача №32)

Пусть на плоскости с евклидовой метрикой задано $N$ красных и $N$ синих точек (красные точки имеют номера от $1$ до $N$, а синие — от $N + 1$ до $2 \cdot N$). Существует $N$ отрезков, соединяющих эти точки таким образом, что каждый отрезок соединяет точки разного цвета и каждая точка — концевая только для одного отрезка.

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

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

В первой строке находится натруальное число $N$ ($1 \leq N \leq 100$).

Следующие $N$ строк файла содержат по два целых числа: координаты красных точек (в первой строке — координаты красной точки с номером $1$, во второй — с номером $2$ и т.д.).

Затем идут $N$ строк файла, в каждом из которых указаны два целых числа: координаты синих точек (первая из этих строк — координаты синей точки с номером $N + 1$, вторая — с номером $N + 2$ и т.д.).

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

Координаты красных и синих точек по модулю не превосходят $1\ 000$.

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

Выведите в единственной строке сообщение Yes, если заданное соединение является минимальным по длине. Если оно таковым не является, то выведите сообщение No.

Пример

Трубопроводы (задача №33)

Имеется сеть трубопроводов по перекачке нефти, при этом у участков трубопроводов есть пропускная способность ($\frac{тонн}{час}$) и стоимость транспортировки (транзита) тонны нефти по участку.

Необходимо организовать перекачку максимального количества тонн нефти при минимальных суммарных затратах транзита из пункта $A$ в пункт $B$. Если два пункта $X$ и $Y$ связаны трубопроводом, то по этому трубопроводу можно перекачивать нефть как из $X$ в $Y$, так и из $Y$ в $X$.

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

В первой строке находится четыре натуральных числа, задающих сеть трубопроводов: число $N$ пунктов, число $M$ трубопроводов, номера пунктов $A$ и $B$ ($1 \lt N \leq 100,\ 0 \leq M \leq \frac{N(N — 1)}{2}$).

Каждая из следующих $M$ строк содержит по четыре целых числа, задающих информацию о некотором трубопроводе: два номера пунктов, связанных трубопроводом, его пропускная способность $P_i$ и стоимость $S_i$ транспортировки по нему ($0 \leq P_i \leq 100,\ 0 \leq S_i \leq 1\ 000$).

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

В первой строке выведите максимальное количество тонн нефти, которое можно перекачать из пункта $A$ в пункт $B$.

Во второй строке — минимальные затраты на транзит.

Пример

Таксист (задача №34)

Имеется $N$ городов, связанных $М$ дорогами (нумерация дорог и городов начинается с единицы). Движение по дорогам осуществляется только в одном направлении, и дороги пересекаются только в городах. Известна длина каждой дороги.

Необходимо найти все дороги, по которым потенциально может проехать таксист таким образом, чтобы длина его маршрута отличалась не более чем на величину $К$ от длины кратчайшего маршрута из $1$-го города в $N$-й.

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

Первая строка файла содержит числа $N$, $M$ и $K$ ($2 \leq N \leq 10\ 000$, $1 \leq M \leq 100\ 000,\ 0 \leq K \leq 10\ 000$). Каждая из последующих $М$ строк описывает дорогу: начальный город, конечный город и ее длина (целое число не более $10\ 000$).

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

Первая строка содержит число $L$ дорог, которые таксист потенциально может использовать.

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

Пример

Стрельба (задача №35)

На соревнованиях по стрельбе каждый участник будет стрелять в цель, которая представляет собой прямоугольник, разделенный на квадраты. Цель содержит $R \cdot C$ квадратов, расположенных в $R$ строках и $C$ столбцах. Квадраты выкрашены в белый или черный цвет.

В каждом столбце находится ровно $2$ белых и $R\ -\ 2$ черных квадрата. Строки пронумерованы от $1$ до $R$ сверху вниз, а столбцы — от $1$ до $C$ слева направо. Стрелок имеет ровно $C$ стрел. Последовательность из $C$ выстрелов называется корректной, если в каждом столбце поражен ровно один белый квадрат, а в каждой строке — не менее одного белого квадрата.

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

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

Первая строка содержит два целых числа $R$ и $C$ ($2 \leq R \leq C \leq 1\ 000$). Эти числа определяют количество строк и столбцов. Каждая из следующих $C$ строк в блоке содержит два натуральных числа, разделенных пробелом. Числа в $(i + 1)$-й строке определяют номера строк, где расположены белые квадраты в $i$-м столбце.

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

Выведите последовательность из $C$ чисел, соответствующих корректной последовательности выстрелов: $i$-й элемент последовательности — номер строки, белую клетку которой поразил выстрел $i$. Если такой последовательности не существует, то выведите сообщение No.

Пример

Инкассаторы (задача №36)

Когда Макс Крейзи закончил финансовый колледж, он стал управляющим городского банка. Уже с первых дней работы Макс столкнулся с одной неразрешимой для него проблемой. В стране, где живет Макс, есть $N$ городов. Некоторые из них связаны двусторонними дорогами, пересекающимися только в городах. Раз в месяц инкассаторы Макса должны доставить деньги в $K$ сберкасс. Все $K$ сберкасс находятся в разных городах. Банк Макса небогат и имеет одну машину для перевозки денег. Вам необходимо помочь Максу составить маршрут минимальной длины, который начинается в городе $L$ (в этом городе находится банк Макса), проходят по всем $K$ городам, где располагаются нужные сберкассы, и заканчивается также в городе $L$.

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

В первой строке через пробел указаны три числа: $N$, $M$ и $K$, где $N$ — общее число городов в стране, $M$ — общее число двусторонних дорог, $K$ — число сберкасс, которые должны посетить инкассаторы ($1 \lt N \leq 100,\ 0 \lt M \leq \frac{N \cdot (N — 1)}{2},\ 0 \lt K \lt 18,\ K < N$).

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

Следующие $M$ строк содержат описания дорог. В каждой строке тремя целыми числами $X$, $Y$ и $S$ описывается одна дорога, причем $X$ и $Y$ — номера городов, связанных дорогой, и $S$ — длина этой дороги ($0 \lt S \leq 50\ 000,\ 1 \leq X,\ Y \leq N$).

В последней строке дано число $L$ — номер города, где находится банк Макса ($1 \leq L \leq N$).

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

Единственная строка должна содержать набор чисел — номеров городов искомого маршрута в порядке обхода.

В случае когда такого маршрута не существует, выведите одно слово — No.

Примеры

Город С (задача №37)

Задана система дорог, определяемая набором пар городов. Каждая такая пара $\{i,\ j\}$ указывает, что из города $i$ можно проехать в город $j$ и в обратном направлении.

Необходимо определить, можно ли проехать из заданного города $A$ в заданный город $B$ таким образом, чтобы посетить город $C$, не проезжать ни по какой дороге более одного раза и не заезжать ни в какой город более одного раза.

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

В первой строке находится число $N$ городов (города нумеруются от $1$ до $N$, $1 \leq N \leq 5\ 000$).

Во второй строке — целое число $M$ дорог ($0 \leq M \leq 10\ 000$). Далее в каждой из $M$ строк — пара номеров городов, соединенных некоторой дорогой.

В последней, $(M + 3)$-й, строке находится номера городов $A$, $B$ и $C$.

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

В единственной строке выведите сообщение Yes, если искомая цепь существует, или No в противном случае.

Примеры

Расселение (задача №38)

Руководство фирмы ООО «Вектор», состоящей из двух отделов, решило на празднование годовщины основания организовать поездку всех сотрудников в санаторий. Санаторий располагает одноместными и двуместными номерами.

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

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

В первой строке задаются возрасты сотрудников первого отдела, разделенный пробелами. Во второй строке — возрасты сотрудников второго отдела. Возраст сотрудника должен лежать в интервале от $18$ до $60$.

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

Единственная строка должна содержать наименьший суммарный показатель недовольства (вычисляется как сумма показателей всех номеров). Число должно иметь одну цифру после точки.

Пример

Сеть дорог (задача №39)

В Байтленде было решено построить сеть автомобильных дорог с односторонним движением. Каждая дорога должна соединять только два города. Известно, какие дороги возможно построить, а также пропускная способность для каждой из них и стоимость одной единицы пропускной способности по конкретной дороге (удельная стоимость). Задача строителей — построить дороги так, чтобы максимизировать пропускную способность между городами $X$ и $Y$ и затратить на это минимальную сумму денег. Первоначально предложен некоторый вариант строительства дорог.

Определить, оптимален ли данный выбор.

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

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

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

Если предложенная сеть дорог является оптимальной, то в первой строке выведите Yes; во второй — максимальную пропускную способность между городами $X$ и $Y$; в третьей — минимальную стоимость, которая будет заплачена за провоз полученного значения пропусконой способности.

Если предложенная сеть дорог не является оптимальной, то в первой строке выведите No; во второй — максимальную пропускную способность между городами $X$ и $Y$ в оптимальной сети дорог; в третьей — минимальную стоимость, которая будет заплачена за провоз полученного значения пропускной способности для оптимальной сети дорог; в четвертой — максимальную пропускную способность между городами $X$ и $Y$ в предложенной сети дорог; в пятой строке — минимальную стоимость, которая будет заплачена за провоз полученного значения пропускной способности для предложенной сети дорог.

Пример

Боеприпасы (задача №40)

На складе хранится $N$ единиц боеприпасов. Было решено их уничтожить в течение $N$ дней по единице в день. Для каждой единицы боеприпаса известно, в какие дни она может быть уничтожена, и задана степень риска при уничтожении этой единицы в указанный день. Требуется уничтожить все боеприпасы так, чтобы суммарный риск был минимальным.

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

В первой строке задается число дней $N$, равное числу боеприпасов ($1 \leq N \leq 200$). В следующих $N$ строках — данные о риске уничтожения боеприпасов: в каждой строке сначала задается число $K_i$ ($1 \leq K_i \leq N$) — число дней, в которые соответствующая единица боеприпасов может быть уничтожена. Затем идут $2K_i$ чисел, описывающих риск уничтожения этой единицы боеприпасов: на нечетных позициях — номера дней от $1$ до $N$, а на четных — соответствующие им степени риска (целые числа в пределах от $0$ до $200$).

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

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

Во второй строке — $N$ чисел: $i$-е число означает, какой боеприпас в $i$-й день должен быть уничтожен.

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

Пример

Замечание

Во второй день с риском $1$ или в третий день с риском $4$ можно уничтожить боеприпас $1$. В первый день с риском $7$ или в третий день с риском $10$ можно уничтожить боеприпас $2$. В первый день с риском $1$ или во второй день с риском $4$ можно уничтожить боеприпас $3$. Безопаснее всего уничтожать боеприпасы в порядке $3,\ 1,\ 2$ с суммарным риском $12$.

Граф? Мультиграф? Псевдограф? (задача №41)

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

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

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

Проверьте, является ли заданная структура из $N$ вершин и $M$ ребер графом, мультиграфом или псевдографом.

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

В первой строке записаны два целых числа $N$ и $M$ — количество вершин ($1 \leq N \leq 500$) и количество ребер ($0 \leq M \leq 100\ 000$). Вершины пронумерованы целыми числами от $1$ до $N$.

В следующих $M$ строках описаны ребра: в каждой строке задается через пробел пара вершин $u$ и $v$ ($1 \leq u,\ v \leq N$), соединенных ребром.

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

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

• граф;
• мультиграф;
• псевдограф.

В случае утвердительного ответа на вопрос выведите Yes, иначе — No.

Пример

входной файл	выходной файл	пояснение
3 3 1 2 2 3 1 2	No Yes Yes

Экскурсия (задача №42)

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

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

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

Если мост соединяет острова $A$ и $B$, то можно выбрать любое из направлений с $A$ на $B$ или с $B$ на $A$, но только одно. Так, если хотя бы один из посетителей прошел по мосту в направлении с $A$ на $B$, то все остальные, кто будет проходить по этому мосту, должны проходить этот мост в этом направлении.

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

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

Первая строка содержит три целых числа, включающих общую информацию о системе мостиков: $N$ — число островов ($2 \leq N \leq 30$), $S$ — номер острова, откуда начинаются все экскурсии ($1 \leq S \leq N$), $F$ — номер острова, на котором группа должна собраться после экскурсии ($1 \leq F \leq N$). Гарантируется, что начальный и конечный острова не совпадают.

Каждая из следующих строк содержит по четыре целых числа, задающих информацию о каждом мостике: номера соединенных этим мостиком островов (от $1$ до $N$), максимальное число $M$ человек, которые могут пройти по данному мосту ($0 \leq M \leq 50$), и стоимость $C$ его прохождения ($0 \leq C \leq 1\ 000$). Между парой островов существует не более одного моста. Никакой мост не соединяет остров с самим собой.

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

Первая строка должна содержать максимальное число человек, которые смогут пройти по парку. Вторая строка — минимальную стоимость этой экскурсии.

Примеры

Машина времени (задача №43)

Между $N$ населенными пунктами совершаются пассажирские рейсы на машинах времени. В момент времени $0$ вы находитесь в пункте $A$. Вам дано расписание рейсов. Требуется оказаться в пункте $B$ как можно раньше (т.е. в наименьший возможный момент времени). При этом разрешается делать пересадки с одного рейса на другой. Если вы пребываете в некоторый пункт в момент времени $T$, то можете уехать из него любым рейсом, который отправляется из этого пункта в момент времени $T$ или позднее (но не раньше).

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

Первая строка содержит целое число $N$ ($1 \leq N \leq 1\ 000$) населенных пунктов. Вторая строка — два числа $A$ и $B$ — номера начального и конечного пунктов. Третья строка — число $K$ рейсов ($0 \leq K \leq 1\ 000$).

Следующие $K$ строк содержат описания рейсов, по одному на строке. Каждое описание представляет собой четверку целых чисел. Первое число каждой четверки задает номер пункта отправления, второе — время отправления, третье — пункт назначения, четвертое — время прибытия. Номера пунктов — натуральные числа в диапазоне от $1$ до $N$. Пункт назначения и пункт отправления могут совпадать. Время измеряется в некоторых абсолютных единицах и задается целым числом, по модулю не превышающим $10^9$.

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

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

Вывести минимальное время, в которое вы сможете оказаться в пункте $B$.

Пример

Максимальное число коней (задача №44)

Задана шахматная доска размера $N \cdot M$, часть клеток которой могут занимать черные фигуры. Необходимо на свободные клетки доски расставить максимальное число белых коней (количество белых коней не ограничено), чтобы они не били друг друга.

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

В первой строке находится число $N$ строк доски, во второй строке — число $M$ столбцов ($1 \leq N,\ M \leq 200$). В каждой из последующих строк — по два числа $x$ и $y$, разделенных пробелом, которые являются координатами черной фигуры ($x$ — номер строки, $y$ — столбца). Координаты верхнего левого угла доски — ($1,\ 1$).

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

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

Пример

Военный поход (задача №45)

В одном феодальном государстве средневековой Европы было $N$ городов и $M$ дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно из тех, которые она соединяла). Однажды правитель города $S$ решил объявить войну правителю города $T$. Перед ним сразу же встала нелегкая задача: как довести армию до города $T$.

Правитель каждого города требует плату за проход войск через его город. Кроме того, правитель города $S$ может перемещать войска только по городам, которые принадлежат ему. При этом он может купить любую дорогу у ее владельца за определенную плату (даже если владелец — правитель города $T$). К сожалению, все деньги из казны города $S$ были потрачены на предыдущий неудачный военный поход, поэтому сначала правителю придется продать некоторые свои дороги (разумеется, после этого он не сможет провести по ним войска).

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

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

Первая строка содержит целые числа $N$ и $M$ — количество городов и дорог соответственно ($2 \leq N \leq 2\ 000,\ 1 \leq M \leq 50\ 000$). Города нумеруются от $1$ до $N$, города $S$ и $T$ имеют номера $1$ и $N$ соответственно.

В каждой из следующих $N$ строк находится по одному целому числу $R_i$ — плата за проезд через город $i$ ($0 \leq R_i \leq 10\ 000$,\ R_1 = R_N = 0$).

Следующие $M$ строк содержат описания дорог. Дорога описывается четырьмя целыми числами: $A_i$, $B_i$, $P_i$ и $C_i$, где $A_i$ и $B_i$ — номера городов, которые соединяет дорога ($A_i \neq B_i$); $P_i$ — номер города, правителю которого она принадлежит; $C_i$ — ее стоимость ($1 \leq C_i \leq 10\ 000$).

По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более чем одной дорогой.

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

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

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

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

Если решений несколько, выведите любое. Если решения нет, выведите число $-1$.

Пример

План эвакуации (задача №46)

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

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

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

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

Собирая начальные сведения по своей задаче, вы выяснили, что город представляет собой прямоугольную сетку. Положение муниципальных зданий и убежищ определяется двумя целыми числами, а время перехода между муниципальным зданием в точке ($X_i, Y_i$) и убежищем в точке ($P_i, Q_i$) равно $D_{ij} = |X_i — P_i| + |Y_i — Q_i| + 1$ мин.

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

Первая строка содержит два числа $N$ и $M$ — число муниципальных зданий в городе (все они пронумерованы от $1$ до $N$) и число убежищ (все они пронумерованы от $1$ до $M$) соответственно ($1 \leq N,\ M \leq 100$).

Следующие $N$ строк описывают мунициальные здания. Каждая строка содержит целые числа $X_i$, $Y_i$ и $B_i$, где $X_i,\ Y_i$ — координаты зданий ($-1\ 000 \leq X_i,\ Y_i \leq 1\ 000$), а $B_i$ — число рабочих в соответствующем здании ($1 \leq B_i \leq 1\ 000$).

Следующие $M$ строк описывают убежища. Каждая строка содержит целые числа $P_i,\ Q_i$ и $C_i$, где $P_i,\ Q_i$ — координаты убежищ ($-1\ 000 \leq P_i,\ Q_i \leq 1\ 000$), а $C_i$ — вместимость убежища ($1 \leq C_i \leq 1\ 000$).

Затем следуют $N$ строк. Каждая строка описывает план эвакуации одного здания в том порядке, в котором они даны в описании города. План эвакуации $i$-го муниципального здания состоит из $M$ целых чисел $E_{ij}$, где $E_{ij}$ — число рабочих, которые должны эвакуироваться из здания $i$ в убежище $j$ ($0 \leq E_{ij} \leq 1\ 000$). Гарантируется, что план корректен, т.е. он позволяет эвакуировать из каждого здания ровно столько рабочих, сколько их там работает, и не превышает вместимость какого-либо убежища.

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

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

Примеры

Замечание

В первом примере план городского совета обеспечивает суммарное время эвакуации $56$, а ваш план — $54$, поэтому он более оптимален. Во втором примере суммарное время равно $1$, план оптимален.

Королевское задание (задача №47)

Жиль король и имел $N$ сыновей. И было в королевстве $N$ красавиц, и король знал, какая из них нравится каждому его сыну. Сыновья были молодые и легкомысленные, так что вполне вероятно, что одному сыну могли нравиться несколько девушек.

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

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

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

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

В первой строке содержится число $N$ сыновей ($1 \leq N \leq 2\ 000$). Следующие $N$ строк для каждого из сыновей содержат список девушек, которые ему нравятся: вначале число $K_i$ девушек, а затем $K_i$ различных целых чисел от $1$ до $N$, определяющих девушек. Сумма $K_i$ не превосходит $200\ 000$.

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

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

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

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

Пример

Платформы (задача №48)

Известная на весь Могилев компания «Headache» выпустила игру, для которой необходима конструкция, состоящая из маленьких платформ и труб. Платформы разделяются на стартовые (их $N_1$ штук), финишные ($N_3$ штук) и промежуточные ($N_2$ штук).

Все стартовые и финишные платформы находятся на одинаковой высоте. Все высоты промежуточных платформ различны. Они меньше высоты стартовых, но больше высоты финишных. Каждой платформе соответсвует уникальный номер от $1$ до $N_1 + N_2 + N_3$. Нумерация следующая: сначала все стартовые платформы, затем промежуточные и, наконец, фальшивые.

Все промежуточные платформы пронумерованы по убыванию высоты, т.е. если номер промежуточной платформы $A$ меньше номера платформы $B$, то высота $A$ больше высоты $B$.

На каждой из стартовых платформ находится шарик. Шарик может скатиться с платформы $A$ на платформу $B$, если они соединены трубой и высота $A$ больше высоты $B$. На каждой из финишных платформ может оказаться не более одного шарика. Если шарик находится на некоторой платформе, то игрок может выбрать направление дальнейшего пути шарика, т.е. выбрать платформу, на которую шарик скатится. Для каждой промежуточной платформы задано число $C$, равное максимальному количеству шариков, которые могут прокатиться по ней за время игры.

Цель игры заключается в том, чтобы на финишных платформах оказалось как можно больше шариков.

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

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

В первой строке записаны целые числа  $N_1,\ N_2,\ N_3$ — соответственно количество стартовых, промежуточных и финишных платформ, где $0 < N_1,\ N_3 \leq 50,\ 1 < N_1 + N_2 + N_3 \leq 200$.

В последующих $N_2$ строках для каждой промежуточной платформы $j$ ($N_1 + 1 \leq j \leq N_1 + N_2$) указано максимальное число шариков $C_j$, которые могут прокатиться по платформе за все время игры ($0 \leq C_j\ \leq 50$).

В каждой из следующих $N_1 + N_2$ строк для платформы с номером $i$ ($1 \leq i \leq N_1 + N_2$) сначала указывается число $K_i$ — количество труб, выходящих из платформы, а затем перечислены $K_i$ номеров платформ, на которые может скатиться шарик с платформы $i$.

Гарантируется, что не существует труб как между стартовыми платформами, так и между финишными.

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

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

Пример

Безопасные пути (задача №49)

В некотором далеком царстве есть система дорог, представляющая собой неориентированный граф. Каждая дорога соединяет два города. Между двумя городами — не более одной дороги. Известно, что с течением времени каждая дорога в этом царстве приобрела один из трех статусов. Первый — статус дороги, на которой стоит царская охрана (далее именуемой $R_1$), второй — статус дороги, на которой регулярно происходят грабежи проезжающих дилижансов (далее именуемой $R_2$), и третий — статус нейтральной дороги ($R_3$). Отсюда видно, что население страны делится на два слоя — добропорядочных граждан и бандитов. Ясно, что обычные граждане ходят только по дорогам тип $R_1$ и $R_3$, а бандиты — по $R_2$ и $R_3$. Поскольку царская казна тратит много денег на содержание данных дорог, то царь решил убрать максимальное число дорог так, чтобы можно было пройти из любого города в любой другой как добропорядочному гражданину, так и грабителю (иначе в стране поднялся бы бунт — взбунтуются или мирные граждание, или бандиты). Необходимо найти максимальное число удаляемых дорог и их номера в соответствии с требованиями царя.

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

В первой строке записано сначала число $N$ городов ($1 \leq N \leq 500$), затем число $M$ дорог в царстве ($1 \leq M \leq 10\ 000$).

Затем идут $M$ троек чисел, описывающих дороги: первые два задают номера городов, которые она соединяет, а третье — статус: $1 — R_1$, $2 — R_2$, $3 — R_3$. Между любыми двумя городами существует не более одной дороги.

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

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

Пример

Светофоры (задача №50)

Дорожное движение в городе Дингилвилле устроено необычным образом. В городе есть перекрестки и дороги, которыми перекрестки связаны между собой. Любые два перекрестка могут быть связаны не более чем одной дорогой. Не существует дорог, соединяющих один и тот же перекресток с самим собой. Время проезда по дороге в обоих направлениях одинаково. На каждом перекрестке находится один светофор, сигнал которого в каждый момент времени может быть либо голубым, либо розовым. Сигнал каждого светофора изменяется периодически: в течение некоторого интервала времени он голубой, а затем в течение другого интервала — розовый. Движение по дороге между любыми двумя перекрестками разрешено тогда и только тогда, когда светофоры на обоих перекрестках этой дороги имеют один и тот же сигнал в момент въезда на эту дорогу. Если транспортное средство прибывает на перекресток в момент переключения светофора, то его поведение будет определяться новым сигналом светофора. Транспортные средства могут находиться в состоянии ожидания на перекрестках.

У вас есть карта города, которая показывает время прохождения  каждой дороги (целые числа); длительность каждого сигнала для каждого светофора (целые числа); начальный сигнал и оставшееся время действия этого сигнала (целые числа) для каждого светофора.

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

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

Первая строка содержит два числа: номер начального и номер конечного перекрестков.

Во второй строке записано число перекрестков $N$ ($2 \leq N \leq 300$) и число дорог $M$ ($1 \leq M \leq 14\ 000$). Перекрестки нумеруются от $1$ до $N$.

Следующие $N$ строк содержат информацию об $N$ перекрестках.

Отдельная строка содержит информацию о перекрестке с номером $i$: $C_i$, $R_i$, $T_i^B$, $T_i^P$. Здесь прописная латинская буква $C_i$ обозначает начальный свет светофора на перекрестке (В — голубой, Р — розовый). Далее $R_i$ — оставшееся время действия начального сигнала ($1 \leq R_i$). Числа $T_i^B$ и $T_i^P$ — длительность действия голубого и розового сигнала светофора соответственно на перекрестке $i$ ($1 \leq T_i^B,\ T_i^P \leq 100$). Число $R_i$ не превосходит длительности действия соответствующего сигнала $C_i$.

Следующие $M$ строк описывают $M$ дорог. Каждая строка имеет вид $i,\ j,\ L_{ij}$, где $i$ и $j$ — номера перекрестков, которые связывает эта дорога, $L_{ij}$ — время, необходимое для перемещения по дороге ($1 \leq L_{ij} \leq 100$).

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

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

Пример

Достроить дороги (задача №51)

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

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

В первой строке записано целое число $N$ — количество городов ($1 \leq N \leq 100\ 000$). Во второй строке — целое число $M$ — количество уже существующих дорог ($0 \leq M \leq 100\ 000$). В последующих $M$ строках описаны дороги: пара чисел $u$ и $v$, записанных через пробел, что свидетельствует о том, что между городами $u$ и $v$ построена дорога ($1 \leq u,\ v \leq N$ и $u \neq v$).

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

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

Примеры

Минимальная плата за проезд (задача №52)

В одной далекой стране есть очень интересная система налогообложения автомобилистов. За проезд по дороге из города $i$ в город $j$ необходимо уплатить налог $C_{ij}$. Система дорог в этой стране также очень интересная, она удовлетворяет трем правилам:

• из каждого города можно проехать в любой другой;
• если по дороге можно проехать из города $i$ в город $j$, то по ней можно проехать и обратно;
• между любой парой городов существует ровно один путь.

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

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

В первой строке входного файла находится натуральное число $N$ ($N \leq 50\ 000$) — количество городов (города нумеруются от $1$ до $N$).

Далее в $N — 1$ строках — описание дороги: номера городов, которые она соединяет, и налог (натуральное число, не превосходящее $10\ 000$), который необходимо заплатить за проезд по ней.

В $N + 1$ строке находится натуральное число $M$ ($M \leq 50\ 000$) — количество запросов в вашей программе.

Далее в $M$ строках файла — пара номеров городов, для которых необходимо рассчитать суммарный налог для проезда из одного города в другой.

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

В выходной файле должно быть ровно $M$ строк, ответы на запросы в том порядке, в котором они идут во входном файле.

Пример

Максимальное ребро (задача №53)

В одной далекой стране существует очень интересная система налогообложения автомобилистов. Чтобы проехать из города $i$ в соседний город $j$ необходимо уплатить «местный» налог $C_{ij}$. Для того чтобы проехать из города $A$ в город $B$, необходимо уплатить налог, равный максимальному из всех «местных» налогов пути из $A$ в $B$. Система дорог в этой стране также очень интересная, она удовлетворяет трем правилам:

• из каждого города можно проехать в любой другой;
• если по дороге можно проехать из города $i$ в город $j$, то по ней можно проехать и обратно;
• между любой парой городов существует ровно один путь.

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

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

В первой строке находится число $N$ городов ($N \leq 50\ 000$). В каждой из следующих $N — 1$ строк — описание дороги: номера городов, которые она соединяет, и местный налог, необходимый для проезда по ней.

В ($N + 1$)-й строке находится целое число $M$ ($M \leq 50\ 000$) — количество запросов в вашей программе.

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

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

Выведите ровно $M$ строк: ответы на запросы в том порядке, в котором они идут во входном файле.

Пример

Ровно К (задача №54)

Вася — большой любитель настольных игр. Недавно он приобрел новую игру для одного игрока с интригующим названием «Ровно К» — это продолжение популярной серии игр «Ровно 1», «Ровно 2», «Ровно 3» …

На игровом поле отмечено $N$ позиций, пронумерованных натуральными числами от $1$ до $N$. Фишка игрока первоначально располагается на первой позиции. Некоторые пары позиций соединены линиями. По правилам игры за один ход фишку нужно обязательно переместить из текущей позиции в другую, соединенную с текущей. Если это сделать невозможно, то игра заканчивается и игроку засчитывается поражение. Между двумя позициями может быть проведено не более одной линии. Однако бывают линии, которые ведут из позиции в нее же, тогда фишка в течение одного хода может оставаться неподвижной. Все соединения действуют в обе стороны: если позиция $i$ соединена с позицией $j$, то фишку можно передвигать как из позиции $i$ в позицию $j$, так и обратно.

Игра состоит из нескольких независимых партий. Каждая партия описывается двумя числами: $V$ и $K$. Чтобы выиграть партию, игроку нужно переместить фишку из позиции $1$ в позицию $V$, сделав ровно $K$ ходов.

Вася распаковал коробку, разложил на столе игровое поле, извлек брошюру с правилами игры и списком из $Q$ пар чисел — это числа $V$ и $K$ для каждой партии.

Какие партии Вася сможет выиграть при оптимальной игре, а какие выиграть принципиально невозможно?

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

В первой строке входного файла записаны два целых числа $N$ ($1 < N \leq 5\ 000$) и $M$ ($0 \leq M \leq 500\ 000$) — количество позиций и соединительных линий на игровом поле соответственно.

Последующие $M$ строк описывают соединения: линия задается парой номеров позиций, которые она соединяет.

Затем в отдельной строке записано число партий $Q$ ($1 \leq Q \leq 5\ 000$), которые предстоит сыграть Васе.

Затем в $Q$ строках описаны партии: каждая пара чисел $V$ и $K$ ($1 \leq V \leq N,\ 0 \leq K \leq 1\ 000\ 000\ 000$) задана в отдельной строке.

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

Выходной файл должен содержать ровно $Q$ строк, по одной для каждой партии.

В случае если существует путь фишки из позиции $1$ в позицию $V$, содержащий ровно $K$ ходов, выведите в соответствующей строке Yes, иначе выведите No.

Пример

Надежная сеть (задача №55)

Акула хочет быть в курсе всех дел Квадратного Бизнесмена. Для этого он поручил Фицджеральду новое задание: связать в сеть компьютеры Акулы и Квадратного Бизнесмена, используя для этого, возможно, промежуточные компьютеры, стоящие в цехах «Сыр Индастриз». Акуле также известно, что Квадратный Бизнесмен имеет достаточно могущества, чтобы отключить от сети одновременно $K$ промежуточных компьютеров, но на отключение $(K + 1)$-го компьютера его власти уже недостаточно. Квадратный Бизнесмен никогда не выключает свой компьютер и не может отключить компьютер Акулы, ведь они в деле. Акула хочет, чтобы сеть была надежной, т.е. чтобы Квадратный Бизнесмен не смог прервать связь между компьютерами Акулы и Квадратного Бизнесмена, даже если бы очень этого захотел.

Все компьютеры пронумерованы уникальными натуральными числами от $1$ до $N$. Компьютер Акулы имеет номер $A$, а компьютер Квадратного Бизнесмена — номер $B$.

Фиц уже определил, какие пары компьютеров можно связать между собой непосредственно и сколько метров провода понадобится для этого. Но теперь он решил, что ему нужно зайти в бар к Роде, чтобы немного освежиться. А вы как его Друган должны посчитать, можно ли построить надежную сеть. Если это возможно, то узнайте наименьшую суммарную длину проводов (в метрах), которая понадобится для этого, если нет — определите минимальное число компьютеров, которое нужно отключить Квадратному Бизнесмену, чтобы Акула не мог быть в курсе его дел.

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

В первой строке входного файла содержатся два целых числа $N$ и $M$ ($1 \leq N,\ M \leq 10\ 000$) — соответственно количество компьютеров и количество пар компьютеров, которые возможно соединить.

У каждой из следующих $M$ строк есть по три целых числа $X,\ Y,\ Z$ ($1 \leq X,\ Y \leq N,\ 1 \leq Z \leq 20\ 000$), означающих, что компьютеры $X$ и $Y$ можно соединить непосредственно и на это уйдет $Z$ метров провода.

Последняя строка содержит три целых числа: $A,\ B$ и $K$ ($1 \leq A,\ B \leq N,\ 0 \leq K \leq N$).

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

Первая строка выходного файла должна содержать сообщение Yes, если можно построить надежную сеть, в противном случае — No.

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

Иначе во второй строке выведите одно целое число — минимальное количество компьютеров, которое нужно отключить Квадратному Бизнесмену, чтобы Акула не мог быть в курсе его дел.

Примеры

Острова (задача №56)

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

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

Строить все мосты дорого, да и нет необходимости: достаточно связать лишь три острова, на которых располагаются города, можно не напрямую, а через другие острова. Какой минимальный объем финансирования потребуется для этого?

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

В первой строке входного файла записаны через пробел целые числа $N$ ($3 \leq N \leq 100\ 000$) и $M$ ($1 \leq M \leq 100\ 000$) — соответственно количество островов и количество мостов, которые можно построить. Острова имеют номера от $0$ до $N — 1$.

В последюущих $M$ строках описываются мосты: каждая строка содержит три числа $A,\ B\ (0 \leq A,\ B < N$) и $K$ ($1 \leq K \leq 1\ 000\ 000$), которые свидетельствуют, что строительство моста между островами $A$ и $B$ стоит $K$ у.е.

В последней строке записано три различных числа $X,\ Y$ и $Z$ ($0 \leq X,\ Y,\ Z < N$) — номера островов, между которыми следует организовать сухопутные перемещения.

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

Выведите одно число — минимальную сумму (в у.е.), которую потребуется потратить на строительство мостов. Гарантируется, что решение существует.

Примеры

Снести (задача №57)

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

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

На первом этапе реализации этой программы чиновники предлагают объявить бесперспективными два хутора, расположенных в разных изолированных областях. Однако король перед утверждением этого плана потребовал (наверное, по своей прихоти), чтобы число изолированных областей в Байтландии не изменилось после сноса бесперспективных хуторов. И теперь советники задались вопросом: какую же пару хуторов снести? Помогите им, рассчитав число вариантов выбора такой пары.

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

В первой строке заданы число $N$ хуторов и число $M$ дорог в Байтландии ($3 \leq N \leq 100\ 000,\ 0 \leq M \leq 100\ 000$).

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

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

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

Примеры

Сталкер: туда и обратно (задача №58)

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

Лабиринт, оказывается, состоит из квадратных комнат, образующих прямоугольник. Некоторые комнаты замурованы (там, видно, хранится что-то ценное, но у вас не хватает опыта, чтобы туда проникнуть). Из каждой комнаты можно перейти в комнаты, которые имеют общую сторону (соседние комнаты), естественно, не выходя за пределы лабиринта и не проникая в замурованные комнаты. Единственный выход из лабиринта находится в той комнате, куда вы так неудачно попали (эта комната — крайняя на плане лабиринта). Ключ от двери находится в другой комнате, так что вам предстоит добраться до ключа и вернуться обратно. Одно радует — монстров в этом лабиринте нет.

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

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

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

В первой строке входного файла записаны два числа $M$ и $N$ — количество строк и столбцов в плане лабиринта ($1 \leq M,\ N \leq 50$).

Далее следуют $M$ строк, каждая из которых содержит $N$ символов — план лабиринта.

В этих строках допускаются следующие символы:

• . — пустая комната;
• * — замурованная комната;
• $M$ — комната, в которой находится вход и выход из лабиринта;
• $G$ — комната, в которой находится ключ.

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

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

Если решение задачи по какой-либо причине невозможно, выведите число $-1$.

Примеры

Полет с пересадками (задача №59)

У Квадратного Бизнесмена очень много дел в разных городах. Поэтому нередко ему приходится перемещаться из одного города в другой. Сегодня как раз такой случай. Квадратный Бизнесмен предпочитает передвигаться на самолете, потому что это очень быстро и удобно.

Поскольку Квадратный Бизнесмен летает часто, он пронумеровал все города, в которых приходится бывать, целыми числами от $0$ до $N — 1$. Сегодня Квадратный Бизнесмен находится в городе $S$, но на днях он должен оказаться на важном совещании, которое проходит в городе $T$.

Зная цены билетов на все авиарейсы, найдите наилучший по стоимости перелет из $S$ в $T$, совершающий не более $Q$ пересадок (Квадратный Бизнесмен, как автор задачи, считает очень утомительным большое число пересадок при авиаперелете). Для примера, если совершается полет из города $0$ в город $4$, а затем из города $4$ в город $3$, то использовано два рейса и сделана одна пересадка.

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

В первой строке содержатся два целых числа $N$ и $M$ — число городов и число рейсов соответственно ($1 \leq N,\ M \leq 10^5$).

Каждая из следующих $M$ строк имеет три целых числа $X,\ Y$ и $Z$, означающих, что из города $X$ в город $Y$ есть авираейс стоимостью $Z$ ($0 \leq X,\ Y < N,\ 1 \leq Z \leq 1\ 000$). Между одной и той же парой городов может быть несколько авиарейсов, возможно, в различных направлениях. Однако нет авиарейса, которые ведет из города в этот же город.

Последняя строка содержит три числа $S,\ T$ и $Q$ ($0 \leq S,\ T,\ Q < N$). Города $S$ и $T$ не совпадают. Известно также, что $N \cdot Q \leq 5 \cdot 10^6,\ M \cdot Q \leq 5 \cdot 10^6$).

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

В первой строке выведите Yes, если можно удовлетворить требования Квадратного Бизнесмена, в противном случае — No. Если ответ положительный, то во второй строке выведите два целых числа: стоимость $C$ и число $R$ пересадок в наилучшем по стоимости перелете из тех, которые требуют не более $Q$ пересадок, в третьей строке через пробел $R + 2$ целых числа — номера городов, которые посетит Квадратный Бизнесмен на этом пути (в порядке посещения).

Примеры

Нефть (задача №60)

В некоторой стране имеются $N$ нефтяных вышек, $i$-я из которых способна выкачать до $a$ тысяч баррелей нефти в сутки, и $M$ нефтеперерабатывающих заводов, каждый из которых в свою очередь, способен переработать до $b_j$ тысяч баррелей нефти в сутки.

Заводы и вышки связаны трубопроводами; ввиду различных причин стоимость транспортировки одной тысячи баррелей от $i$-й вышки к $j$-му заводу составляет $c_{ij}$ денежных единиц; объем перекачки не ограничен.

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

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

В первой строке входного файла находится целые числа $N$ и $M$ ($1 \leq N,\ M \leq 300$) — число вышек и заводов соответственно.

Во второй строке через пробел перечислены $N$ целых чисел — значения $a_i$ ($1 \leq a_i \leq 30\ 000$).

В третьей строке через пробел даны $M$ целых чисел — значения $b_j$ ($1 \leq b_j \leq 30\ 000$). Сумма всех $a_i$ равна сумме всех $b_j$.

В последующих $N$ строках по $M$ целых чисел записаны стоимости транспортировки одной тысячи баррелей нефти от соответствующей вышки к заводу; $j$-е число в ($i + 2$)-й строке задает $c_{ij}$ ($1 \leq c_{ij} \leq 10\ 000$).

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

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

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

Пример