#112579

Спасти наш мир!

Темы: [Бинарный поиск] [Паросочетания]

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

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

В этом мире случилось несчастье. На TheBestWorld нападают темные силы. У генерала главнокомандующего армией супергероев есть в распоряжении n + m супергероев, из них n — выпускники первой школы, m — второй. Главнокомандующий подсчитал количество супергероев k , которые смогут спасти лучшее, что у них есть, — планету.

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

Проблема в том, что генерал забыл искомое d . Вам известны координаты каждого из супергероев. Генерал просит вас вычислить максимальное d , при котором он все еще может спасти мир. И выдать список супергероев, которые спасут мир при данном d .

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

В первой строке входного файла заданы три числа n , m и k ( 1 ≤ k , n , m ≤ n + m ≤ 200 ) — количество супергероев, выпустившихся из первой и второй школы, и количество супергероев, которое необходимо, чтобы спасти мир, соответственно. Следующие n + m строк описывают супергероев: в каждой строке заданы два целых числа — текущие координаты супергероя. Первые n строк содержат информацию о выпускниках первой школы, следующие m — о выпускниках второй школы. Все координаты не превышает по модулю 10000 . Известно, что никакие два супергероя не стоят в одной точке.

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

В первую строку выходного файла выведите одно вещественное число: максимальное значение d , которое позволяет спасти мир, либо -1, если при любом значении d мир можно спасти. Относительная или абсолютная погрешность вашего ответа не должна превышать 10 ⁻⁶ . В следующих k строках выведите список номеров супергероев по одному числу в строке, которых можно взять при данном d , либо, если спасти мир можно при любом d , выведите список героев, которые позволяет спасти мир вне зависимости от d . Супергерои нумеруются числами от 1 до n + m в том порядке, в котором они идут во входном файле.

Примеры

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

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

2.000000000000000000
1
3
4
5

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

1 1 2
1 1
1 10

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

9.000000000000000000
1
2

#112580

Гангстер

Темы: [Вычислительная геометрия]

Рассмотрим 3D модель системы координат OXYZ . Ось OX направлена направо, ось OY наверх, ось OZ от нас. В пространстве находятся прямоугольные окна. Плоскость каждого окна параллельна плоскости OXY , т.е. его стороны параллельны осям OX и OY . Все окна находятся на разной глубине (различные координаты z > 0).

$\text{[math]}$

Гангстер с ружьем двигается вдоль оси OX ( y = 0, z = 0 ). Он может выстрелить пулей по прямой линии. Его цель одним выстрелом пробить все окна. Просто касания окна по ребру достаточно, чтобы оно разбилось. Ваша задача определить как совершить такой выстрел.

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

Первая строка содержит одно число n ( 2 ≤ n ≤ 100 ) - число окон в пространстве. Следующие n строк описывают окна. Каждая строка содержит 5 целых чисел x _{1

i} , y _{1

i} , x _{2

i} , y _{2

i} , z _i ( 1 ≤ x _{1

i} , y _{1

i} , x _{2

i} , y _{2

i} , z _i ≤ 1000 ). Здесь ( x _{1

i} , y _{1

i} , z _i ) - координаты нижнего левого угла, а ( x _{2

i} , y _{2

i} , z _i ) - координаты верхнего правого угла. Все окна имеют ненулевую площадь. Окна отсортированы по координате z .

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

Выведите единственное слово "UNSOLVABLE", если гангстер не может достичь своей цели.

Иначе выведите слово "SOLUTION". На следующей строке выведите x координату точки из которой должен выстрелить гангстер. В следующих n строках выведите x , y , z - координаты точек в которых пуля пробьет i -ое окно. Все координаты должны быть выведены с точностью 6 знаков после запятой.

Примеры

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

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

SOLUTION
-5.0000000000
1.0000000000 3.0000000000 3.0000000000
5.0000000000 5.0000000000 5.0000000000
7.0000000000 6.0000000000 6.0000000000

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

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

UNSOLVABLE

#112589

Министерство

Темы: [Алгоритмы на графах] [Хеш]

Источники: [ Личные олимпиады, Central European Olympiad in Informatics , Central European Olympiad in Informatics 2007, Министерство ]

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

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

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

Есть два особых случая:

Департамент, в котором должностное лицо — сам министр, тогда этот департамент есть всё министерство.
Департамент, в котором у должностного лица нет ни одного подчинённого.

Высотой департамента назовем длину максимальной последовательность сотрудников x ₁ , ..., x _d такую, что сотрудник x _i является начальником сотрудника x _{i

+ 1} для всех 1 ≤ i < d . Заметим что высота департамента, состоящего из одного сотрудника равна 1 .

Два департамента A и B совпадают, если существует взаимно-однозначное отображение, сопоставляющее каждому сотруднику x _A из департамента A сотрудника x _B из департамента B , таким образом, что сотрудник x _A является начальником сотрудником y _A , тогда и только тогда, когда x _B является начальником y _B . Заметим, что если два департамента совпадают, то они имеют одинаковую высоту, одинаковое количество сотрудников и начальнику первого департамента соответствует начальник второго.

На приведенных картинках департаменты A и B совпадают, а C не совпадает ни с A , ни c B .

$\text{[math]}$

Вам необходимо для каждой высоты вычислить количество различных департаментов имеющих такую глубину. Формально требуется построить последовательность n ₁ , ..., n _d , где d это высота всего министерства, а n _i — количество различных департаментов высоты i .

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

Входной файл содержит единственную строку, которая описывает иерархическую структуру министерства, используя следующую нотацию. Каждый департамент кодируются строкой "( x ₁ ... x _k )", где k — количество подчинённых у начальника департамента, а строки x _i — коды им подчиняющихся департаментов. Департамент, состоящий из одного человека, кодируется строкой "()". Структура министерства задается кодом всего министерства. Количество сотрудников министерства не превосходит 1 000 000 (включая министра).

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

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

Примечание

Приведенная картинка иллюстрирует пример из условия. $\text{[math]}$

Примеры

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

(((())())((()())(()()()))(()(())))

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

#112597

Совершенно секретно (HARD)

Темы: [Паросочетания] [Эйлеров цикл]

В секретном 240 отделе ИПФ РАН $N$ сотрудников и $N$ компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно $K$ компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно $K$ сотрудников.

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

Обратите внимание, что значение $K$ тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что $K$ будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений $K$.

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

В первой строке входного файла записаны натуральные числа $N$ и $K$ ($1\leq N \leq 100 000$). Далее следуют $KN$ строк, в каждой из которых записаны два натуральных числа — номер сотрудника и номер компьютера, к которому этот сотрудник имеет допуск.

Гарантируется, что каждый сотрудник имеет допуск ровно к $K$ компьютерам, что к каждому компьютеру ровно $K$ сотрудников имеют допуск, и что $K$ равно либо 1, либо 2, либо 4.

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

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

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

Примеры

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

#112598

Два пути

Темы: [Динамическое программирование на поддеревьях]

Как вы знаете, Васин брат живет во Флатландии. Во Флатландии n городов, соединенных n - 1 двухсторонней дорогой. Города пронумерованы от 1 до n . Из любого города можно добраться до любого другого.

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

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

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

В первой строке записано целое число n (2 ≤ n ≤ 100 000) , где n количество городов в стране. Далее в n - 1 строке записаны сами дороги. Каждая строка содержит пару номеров соединяемых дорогами a _i , b _i (1 ≤ a _i , b _i ≤ n )

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

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

Примеры

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

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

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

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

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

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