графы

Проверьте, является ли данный JSON корректным деревом решений.

Дерево корректно, если:

• Есть узел с id=0 (корень)
• Все ссылки left_child и right_child указывают на существующие узлы
• Нет циклов (каждый узел кроме корня имеет ровно одного родителя)
• Все листья достижимы из корня

Формат входных данных
JSON с предполагаемым деревом решений.

Формат выходных данных
VALID если дерево корректно, иначе INVALID

 

Подземный бункер состоит из \(n\) комнат, соединённых \(n - 1\) коридорами. Каждый коридор соединяет две различные комнаты и имеет определённую длину. Бункер устроен таким образом, что из любой комнаты \(i\) можно дойти в любую другую комнату \(j\). Заметим, что существует единственный такой путь, не проходящий по одному и тому же коридору дважды. Сумма длин коридоров, составляющих этот путь, называется расстоянием между комнатами \(i\) и \(j\) и обозначается \(\rho(i, j)\).

Каждая комната бункера оборудована звуковой сигнализацией, состоящей из сирены и датчика звука, который её включает. Сирена, включённая в комнате \(i\), активирует датчик звука в каждой комнате, расстояние до которой не превосходит расстояние \(d_i\), определяемое мощностью этой сирены. Другими словами, включение сирены в комнате \(i\) автоматически включает сирену во всех комнатах \(j\), таких что \(\rho(i, j) \leq d_i\). Эта сирена, в свою очередь, может вызвать автоматическое включение других сирен и так далее.

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

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

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

Первая строка входных данных содержит единственное число \(n\) — количество комнат.

Вторая строка содержит последовательность из \(n\) целых чисел \(d_i\), \(i\)-е из них равно максимальному расстоянию, на котором расположенная в комнате \(i\) сирена активирует датчики (\(0 \leq d_i \leq 10^9\)).

Последующие \(n - 1\) строк описывают коридоры бункера. В \(i\)-й из них находятся три целых числа: \(u_i\), \(v_i\), \(l_i\), где \(u_i\), \(v_i\) — номера различных комнат, соединённых коридором \(i\), а \(l_i\) — длина этого коридора (\(1 \leq u_i, v_i \leq n\); \(1 \leq l_i \leq 10^9\)).

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

Замечание
В тесте из примера сирена в комнате 4 включает сирену в комнате 5, которая, в свою очередь, включает сирены в комнатах 6 и 7. Сирена в комнате 2 включает сирену в комнате 3. Сирена в комнате 8 включает сирены в комнатах 1, 9 и 10.

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

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

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

Входные данные
Первая строка входных данных содержит два целых числа \(a\) и \(b\) — размеры полотенца в клетках по горизонтали и вертикали.

Вторая строка содержит два числа \(n\) и \(q\) — количество жемчужин в узоре и количество фрагментов соответственно.

Следующие \((n - 1)\) строк содержат описания стежков. Каждый стежок имеет один из следующих видов:

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

Следующие \(q\) строк описывают фрагменты. Каждое описание содержит четыре целых числа \(x_1\), \(y_1\), \(x_2\) и \(y_2\) — координаты левой нижней и правой верхней клетки фрагмента (\(1 \leq x_1 \leq x_2 \leq a\); \(1 \leq y_1 \leq y_2 \leq b\)).

Выходные данные
Выходные данные должны содержать \(q\) строк, где \(i\)-я строка содержит количество связных частей узора в \(i\)-м фрагменте.

Замечание
Пояснение к тесту из условия.

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

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

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

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

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

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

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

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

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

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

Заданы точки A и B. Требуется определить, за какое минимальное время солдат во время учений сможет переместиться из А в B. Шириной траншей и окопов можно пренебречь.

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

Первая строка содержит число n — количество окопов на полигоне (1 ≤ n ≤ 500). Введем систему координат на полигоне таким образом, чтобы ось OX была ориентирована с запада на восток, а ось OY — с юга на север. Следующие n строк описывают окопы, каждый окоп описывается четырьмя целыми числами x₁, y₁, x₂, y₂ — координатами юго-западного и северо-восточного углов, соответственно (–10⁴ ≤ x₁ < x₁ ≤ 10⁴, –10⁴ ≤ y₁ < y₂ ≤ 10⁴).

Последние две строки содержат по два целых числа: x_A, y_A — координаты точки A и x_B, y_B — координаты точки B, соответственно (–10⁴ ≤ x_A, y_A, x_B, y_B ≤ 10⁴). Гарантируется, что точки A и B находятся в окопах. Все координаты заданы в метрах.

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

Выведите одно вещественное число — количество часов, которое потребуется солдату, чтобы добраться из точки A до точки B. Ответ должен отличаться от правильного не более чем на 10^-6.

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

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

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

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



На рисунке показано озеро и города вокруг него. Тонкие и жирные линии отрезков обозначают коммерческие соглашения между городами. Жирные линии показывают маршрут грузоперевозок, начинающийся в городе 2 и заканчивающийся в городе 5.

Этот маршрут нигде не имеет самопересечений. Но если построить маршрут, идущий из города 2 в город 6, затем в город 5, а затем в город 1, то он будет неправильным, поскольку имеет самопересечения.

Города нумеруются целыми числами от 1 до c по направлению часовой стрелки.
Задание
Напишите программу, которая по заданному числу городов c и списку коммерческих соглашений между городами, найдет маршрут товароперевозок, удовлетворяющий указанным выше условиям.

Ограничения
3 ≤ c ≤ 1000, c – число городов вокруг озера

Входные данные
На вход Вашей программы поступают данные в следующем формате:

СТРОКА 1: Содержит целое число c.
СТРОКА 2: Содержит целое число n – количество коммерческих соглашений.
СЛЕДУЮЩИЕ n СТРОК: Каждая строка описывает одно коммерческое соглашение (одно соглашение описывается один раз). В строке задаются два целых числа, разделенных пробелами, которые соответствуют номерам городов, заключивших между собой коммерческое соглашение.

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

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

Два неориентированных графа G и H называются изоморфными , если:

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

Например, следующие два графа изоморфны, хотя выглядят по-разному:


 

Возможным однозначным соответствием, показывающим, что эти два графа изоморфны, является {a-1, b-6, c-8, d-3, g-5, h-2, i-4, j-7}, хотя существуют и другие подобные соответствия.

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

Говорят, что граф G содержит другой граф H , если существует хотя бы один подграф H ’ графа G , который изоморфен H . Следующий рисунок показывает граф G , который содержит граф H .



ЗАДАНИЕ

По двум заданным неориентированным графам G и H постройте подграф G’ графа G такой, что:

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

БАЗОВЫЙ АЛГОРИТМ

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

ОГРАНИЧЕНИЯ

3 ≤ m ≤ 4    m – количество вершин в H.
3 ≤ n ≤ 1000    n – количество вершин в G .

ВВОД

Вы получите 10 тестов каждый со следующими данными:
 

Пример ввода

ОПИСАНИЕ

3 5 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0

СТРОКА 1: Содержит два целых числа, разделенных пробелом, соответственно m и n. СЛЕДУЮЩИЕ m СТРОК: Каждая строка содержит m целых чисел, разделенных пробелами, и представляет одну вершину из H в порядке 1, ..., m . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в H , и равняется 0 в противном случае. СЛЕДУЮЩИЕ n СТРОК : Каждая строка содержит n целых чисел, разделенных пробелами, и представляет одну вершину из G в порядке 1, ..., n . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в G , и равняется 0 в противном случае.

 

Заметьте, что за исключением строки 1, приведенные входные данные представляют собой матрицы смежности графов H и G .

ВЫВОД

Вы должны создать 10 выводов по одному на каждый входной. Каждый тест должен содержать следующие данные:

Пример вывода

ОПИСАНИЕ

#FILE forbidden K 5 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

СТРОКА 1: Заголовок файла. Заголовок файла должен содержать #FILE forbidden K где K – это число между 1 и 10, которое соответствует решенному входному файлу. СТРОКА 2: Содержит одно целое число : n . СЛЕДУЮЩИЕ n СТРОК : Каждая строка содержит n целых чисел, разделенных пробелом, и представляет одну вершину из G’ в порядке 1, ..., n . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в G’ , и равняется 0 в противном случае.

Заметьте, что за исключением строк 1 и 2, приведенные входные данные представляют собой матрицу смежности графа G’. Обратите внимание, что есть много вариантов ответа, и приведенный вариант является корректным, но не оптимальным.

Планируется строительство новой магистрали <<Урал>>. Долговечность автомагистрали зависит от пластов пород, залегающих под ней. Пластом называется геологическое тело, состоящее из одной горной породы.

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

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

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

Формат входных данных
Первая строка входного файла содержит целое число \(n\) "— количество пластов. Пласты пронумерованы целыми числами от \(1\) до \(n\) в произвольном порядке.

В \(i\)-й из следующих \(n\) строк содержатся целые числа \(l_i\) и \(r_i\) (\(0 \leqslant l_i < r_i\leqslant 10^9\)) "— расстояния от начала магистрали до точек, под которыми начинается и заканчивается \(i\)-й пласт.

В следующей строке записано целое число \(m\) "— количество скважин, в которых проводилось бурение. Следующие \(m\) строк описывают результаты бурения: в каждой строке сначала указаны два целых числа \(x\) (\(0 \leqslant x \leqslant 10^9\)) и \(k\) (\(0 \leqslant k \leqslant n\)) "— расстояние от начала магистрали до скважины и количество обнаруженных в данной скважине пластов, затем "— целые числа \(s_1, s_2, \ldots, s_k\) "— номера пробуренных пластов, перечисленные в порядке залегания сверху вниз. Скважины перечислены в порядке возрастания расстояния \(x\).

Гарантируется, что решение существует.

Формат выходных данных
Первая строка выходного файла должна содержать \(n\) целых чисел \(p_1, p_2, \ldots , p_n\), описывающих возможный порядок залегания пластов сверху вниз. Среди чисел \(p_1, p_2, \ldots , p_n\) каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером \(p_j\) не должен нигде проходить выше пластов с номерами \(p_1, \ldots ,p_{j-1}\) или ниже пластов с номерами \(p_{j+1}, \ldots , p_n\).

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

Примечание
Рисунок в условии соответствует примеру. Для приведенного примера правильным также является ответ 2 3 1 4. Обратите внимание, что тест из примера не соответствует подзадаче 1. Для того, чтобы решение было принято на проверку, оно должно проходить тест из примера, даже если решена только эта подзадача.

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

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

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

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

• появление новой траектории частицы,

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

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

Формат входных данных
В первой строке задано одно целое число \(n\) (\(1 \leqslant n \leqslant 200\,000\)) — общее количество событий. В следующих \(n\) строках заданы описания событий.

Описание каждого события состоит из пяти элементов. Первый элемент является символом <<+>>, если это событие является появлением новой траектории, или символом <<?>>, если это событие является получением фотоснимка. Последующие четыре элемента — целые числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(-10\,000 \leqslant x_1, y_1, x_2, y_2 \leqslant 10\,000\)) — координаты двух несовпадающих точек. Для событий первого типа указанные точки лежат на траектории частицы. Все траектории различны. Для событий второго типа указанные точки лежат на направляющей прямой камеры.

Формат выходных данных
Пусть \(q\) — количество полученных фотоснимков. Выходной файл должен содержать \(q\) вещественных чисел — минимальные возможные площади фотоснимков, перечисленные в порядке их получения камерой. Тест будет успешно пройден, если для каждой из \(q\) выведенных площадей выполняется условие \(\frac{|a - b|}{\max(1, b)} \leqslant 10^{-4}\), где \(a\) — площадь, выведенная участником, \(b\) — площадь, полученная решением жюри.

Примеры

№	Входные данные	Выходные данные	Иллюстрация
1	6 + 0 0 0 1 + 0 0 1 0 + 1 0 0 2 ? 0 0 0 1 + 2 4 3 6 ? 0 0 1 1	2.0 3.000
2	7 ? 11 4 -7 8 + -2 -2 1 1 ? 0 0 0 1 + 0 1 1 0 + 0 2 2 0 ? 0 0 0 1 ? 0 0 1 1	0.0 0.0 0.25 0.0000000

Робинзон живет на острове, который представляет собой прямоугольник размером \(n \times m\) клеток.

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

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

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

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

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

Формат входных данных
В первой строке записаны числа \(n\) и \(m\) "— размеры острова с севера на юг и с запада на восток. Последующие \(n\) строк по \(m\) символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой <<.>>, а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: <<N>> "— север, <<S>> "— юг, <<E>> "— восток, <<W>> "— запад.

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

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