Алгоритмы

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

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

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

Входные данные
В первой строке вводится число N (1 <= N <= 100) - количество кубиков в наборе у Пети. Во второй строке задано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.

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

В случае положительного ответа, во второй строке выведите M различных чисел из диапазона 1…N, где M - количество букв в имени Петиной сестры. i-е число должно быть номером кубика, который следует положить на i-е место при составлении имени Петиной сестры. Кубики нумеруются с 1, в том порядке, в котором они заданы во входных данных. Если решений несколько, выведите любое. Разделяйте числа пробелами.

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K
 различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце - это конечно же нули - ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули, начиная с 5!=1·2·3·4·5 . А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 - так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N!=1·2·3·...·(N-1)·N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

Входные данные
В первой строке входных данных содержатся числа N и K, разделенные пробелом, (1 <= N <= 10⁹, 2 <= K <= 1000).

Выходные данные
Выведите число X - количество нулей в конце записи числа N! в системе счисления с основанием K.

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

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

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

Входные данные
В первой строке вводится число n
 - количество дырок (2 <= n <= 1000). Следующие n строк содержат по два целых числа - координаты дырок. Координаты не превышают 10⁴
 по абсолютной величине.

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

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

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

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

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

Формат выходных данных
Выведите границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходном файле не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все числа должны быть целыми и не превосходить \(10^5\) по абсолютной величине. При проходе вдоль описанной границы выпуклая оболочка углов должна быть справа.

На первой строке выведите \(l\) — количество объектов в ответе. Следующие \(l\) строк должны содержать описание объектов. Объекты описываются следующим образом:

• Отрезок: <<segment \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) и \((x_2, y_2)\) — концы отрезка, отрезок считается направленным от \((x_1, y_1)\) к \((x_2, y_2)\).

• Луч, направленный от начала: <<outray \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) — начало луча, а \((x_2, y_2)\) — произвольная точка на луче, отличная от начала.

• Луч, направленный к началу: <<inray \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_2, y_2)\) — начало луча, а \((x_1, y_1)\) — произвольная точка на луче, отличная от начала.

• Прямая: <<line \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) и \((x_2, y_2)\) — две точки на прямой, причем при движении вдоль прямой в ее направлении точка \((x_1, y_1)\) следует ранее точки \((x_2, y_2)\).

Если выпуклой оболочкой является вся плоскость, то выведите \(l = 0\).

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

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

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


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

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

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

Входные данные
В первой строке вводятся два числа: h₁ и w₁ (1 <= h₁, w₁ <= 10). Следующие h₁
строк содержат по w₁ символов и описывают первую фигуру, вид сверху. Каждый из этих символов - либо "*" (звездочка), либо "." (точка), звездочка обозначает кубик, а точка – пустое место.

Далее в отдельной строке вводятся два числа: h₂ и w₂  (1 <= h₂,  w₂ <= 10). Следующие h₂ строк содержат по w₂ символов и описывают вторую фигуру в формате, аналогичном формату первой. Каждая из фигур связна и содержит хотя бы один кубик.

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

«Соединение точек» – это игра для одного игрока. Игровое поле строится следующим образом. Выбираются два целых числа, каждое из которых больше 2, которые обозначаются g и r. Затем на плоскости рисуются четыре точки в вершинах квадрата, две верхние из них становятся зелеными точками, а две нижние – красными. Далее внутри квадрата рисуются зеленые и красные точки таким образом, что никакие три точки, включая вершины квадрата, не лежат на одной прямой. Процесс продолжается до тех пор, пока общее количество зеленых точек не станет равным g, а количество красных точек – равным r.

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

Будем считать, что две точки u и v принадлежат одной компоненте, если от u до v можно дойти по нарисованным отрезкам.

Цель игры – соединить все зеленые точки в одну компоненту с помощью (g – 1) отрезков, а все красные точки – в другую компоненту с помощью (r – 1) отрезков. Можно доказать, что при вышеописанном способе расположения точек всегда существует способ выиграть игру.

Вам будет задано квадратное игровое поле со стороной s, а также g зелеными и r красными точками. Координаты точек задаются парами целых чисел (x_i, y_i). Зеленые точки пронумерованы числами от 1 до g так, что верхняя левая точка (0, s) имеет номер 1, верхняя правая точка (s, s) – номер 2, а остальные точки – номера от 3 до g (в произвольном порядке). Красные точки пронумерованы числами от 1 до r так, что нижняя левая точка (0, 0) имеет номер 1, нижняя правая точка (s, 0) – номер 2, а остальные точки – номера от 3 до r (в произвольном порядке).



На рисунке показан пример игры, где зеленые точки соединены в одну компоненту, а красные точки – в другую.

Легко видеть, что никакие три точки на рисунке не лежат на одной прямой, и никакие два отрезка не пересекаются, кроме как по концам.
Задание
Напишите программу, которая по заданным координатам g зеленых точек и координатам r красных точек находит способ, как нарисовать (g – 1) зеленых отрезков и (r – 1) красных отрезков таким образом, чтобы все зеленые точки принадлежали одной компоненте, а все красные точки – другой, и никакие два отрезка не пересекались.

Ограничения
3≤g≤50000,g – количество зеленых точек 
3≤r≤50000
0<s≤200000000,r – количество красных точек

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

СТРОКА 1: Содержит целое число g.

СЛЕДУЮЩИЕ g
СТРОК: Каждая строка содержит два целых числа – координаты xi и yi каждой из g зеленых точек, начиная с точки с номером 1 и заканчивая точкой с номером g. Эти два числа разделены пробелами.

СТРОКА g + 2: Содержит целое число r.

СЛЕДУЮЩИЕ r СТРОК: Каждая строка содержит два целых числа – координаты xi и yi каждой из r красных точек, начиная с точки с номером 1 и заканчивая точкой с номером r. Эти два числа разделены пробелами.

Выходные данные
Ваша программа должна вывести (g – 1) + (r – 1) строк, каждая из которых описывает один отрезок, соединяющий две точки.

Каждая строка должна содержать два целых числа и один символ, разделенные пробелом. Числа представляют собой номера точек, соединенных этим отрезком. Если точки зеленые, то последним символом в строке должен быть g, если точки красные, то последним символом в строке должен быть r.

Ни порядок, в котором выводятся отрезки, ни порядок точек в строке не имеют значения.

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

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

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

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

Выясните, какие яблоки упадут с Петиной яблони.

Входные данные
В первой строке вводится число N - количество яблок на Петиной яблоне (1 <= N <= 200). Следующие N строк содержат описания яблок. Будем считать все яблоки шарами. Каждое яблоко задается координатами своей самой верхней точки (той, где оно исходно прикреплено к дереву, длиной черенка пренебрежем) x_i, y_i и z_i и радиусом r_i ( -10000 <= x_i, y_i, z_i <= 10000, 1 <= r_i <= 10000, все числа целые). Гарантируется, что изначально никакие яблоки не пересекаются (даже не соприкасаются). Ось OZ направлена вверх.

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

Фирма Macrohard получила заказ от армии одной страны на реализацию комплекса программного обеспечения для нового суперсекретного радара. Одной из наиболее важных подпрограмм в разрабатываемом комплексе является процедура сортировки.

Однако в отличие от обычной сортировки, эта процедура должна сортировать не произвольный массив чисел, который передается ей на вход, а специальный заранее заданный массив из N чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до N, и кроме того, ни одно число в нем изначально не находится на своем месте (то есть на позиции с номером i изначально не находится число i).

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

Например, если массив из 6 элементов в некоторый момент имеет вид <2, 1, 3, 6, 4, 5>, то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

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

Подсказка

Найти такую последовательность обменов всегда возможно.

Входные данные
В первой строке вводится целое число N - размер входного массива (1 <= N <= 100). Вторая строка содержит N целых чисел - исходную перестановку чисел от 1 до N в массиве. Изначально ни одно число не стоит на своем месте.

Выходные данные
Выведите K строк, где K - количество обменов в Вашей сортировке. На каждой строке выведите по два числа x_i и y_i, разделенных пробелом - позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |x_i - y_i| = 1 и что нельзя перемещать число, которое уже стоит на своем месте.

Пояснение к примеру
В приведенном примере массив последовательно имеет следующий вид:
исходный вид массива
2 3 1 6 4 5
поменяли местами числа на 2 и 3 позициях
2 1 3 6 4 5
поменяли местами числа на 1 и 2 позициях
1 2 3 6 4 5
поменяли местами числа на 4 и 5 позициях
1 2 3 4 6 5
поменяли местами числа на 5 и 6 позициях
1 2 3 4 5 6

В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с N вершинами. Сам Петя находится в точке с координатами (x, y).

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

Петя может перемещаться по плоскости со скоростью v. Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).

Выясните, какое минимальное время требуется Пете, чтобы оказаться в освещенной точке.


Входные данные
В первой строке вводятся координаты Пети – два неотрицательных вещественных числа, не превышающих 1000, и его скорость v – вещественное число, 10^-2≤ v≤ 10⁴.

Вторая строка содержит N – число вершин в многоугольнике, задающем Петин дом ( 3≤N≤100). Далее в N строках вводится по два вещественных числа – координаты вершин многоугольника в порядке их обхода против часовой стрелки. Все координаты неотрицательны и не превышают 1000.

Гарантируется, что входные данные корректны, в частности, многоугольник выпуклый, и никакие три его последовательные вершины не лежат на одной прямой. Также гарантируется, что и Петя, и лампочка находятся снаружи от многоугольника, в частности, не находятся на его границе. Расстояние от точки, где находится Петя, до многоугольника и от начала координат до многоугольника не меньше 10^-2, расстояние от Пети до начала координат не меньше 10^-2.

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

Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида \(a_1+a_2+\ldots +a_n\) и \(a_1\cdot a_2 \cdot \ldots \cdot a_n\) не зависит от порядка выполнения в них действий и следовательно не меняется при произвольной расстановке в этих выражениях скобок.

В отличии от сложения и умножения, деление — операция не ассоциативная. Так, значение выражения вида \(a_1/a_2/\cdots /a_n\) может меняться при расстановке в нем скобок.

Рассмотрим выражение вида \[p_1 / p_2 / \cdots / p_n,\] где все \(p_i\) — простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений.

Например, выражение \(3/2/2\) после расстановки скобок может принять два значения: \(3/4 = (3 / 2) / 2\) и \(3 = 3 / (2 / 2)\).

Формат входных данных
Первая строка содержит число \(n\) (\(1 \le n \le 200\)). Следующая строка содержат \(n\) натуральных чисел — \(p_1, p_2, \dots, p_n\). Все числа \(p_i\) простые и не превосходят \(10^4\).

Формат выходных данных
На первой строке выведите количество возможных значений, которые может принять выражение \(p_1 / p_2 / \cdots / p_n\) при заданных \(p_i\) после расстановки в нем скобок. На второй строке выведите количество целых чисел среди этих значений.

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

Петя предположил, что между цивилизациями A и B
происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.

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

Входные данные
В первой строке вводится число N – количество цивилизаций, культура которых интересует Петю (1≤N≤100 000). Следующие N строк содержат описание цивилизаций – в каждой строке задаются два целых числа Si и E_i
 – год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят 10⁹
 по абсолютной величине, S_i < E_i.

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

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

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

Входные данные
В первой строке входных данных содержатся два числа N и M – количество автобусных остановок и станций метро соответственно (2 ≤ N ≤ 50 000, 1 ≤ M ≤ 1 000, M < N).

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

В следующих N – 1 строках записано по два числа – номера автобусных остановок, между которыми курсирует автобус. (Автобус ходит в обоих направлениях. Каждый маршрут указан один раз.)

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

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

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

Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Входные данные
Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1≤K≤100000, 1≤N≤100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 10⁹. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.

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

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

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

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

Входные данные
Cначала вводится целое число N - количество деревьев (1≤N≤50000). Затем идут два числа, задающих координаты наблюдателя. Затем идет N троек чисел, задающих деревья  (первые два числа тройки задают координаты центра, а третье - радиус). Все координаты задаются точно и выражаются вещественными числами, по модулю не превосходящими 100000 и записанными не более чем с 2 знаками после десятичной точки.

Выходные данные
В первой строке выведите сообщение YES, если лес является дремучим, и NO  - иначе. Во втором случае во вторую строку необходимо вывести координаты точки, глядя в направлении которой наблюдатель не видит деревьев (то есть луч, вдоль которого смотрит наблюдатель, не проходит внутри деревьев и не касается ни одного из деревьев). Координаты нужно вывести не менее, чем с 3 знаками после десятичной точки. Координаты не должны превышать 300000. Расстояние между выданной точкой и наблюдателем должно быть не меньше 1.

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

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

Для любой пары атомов стабильного нанокристалла определена их взаимная удаленность – минимальная длина цепочки из связей, которая их соединяет. Например, рассмотрим описанный выше нанокристалл. Взаимная удаленность атомов A и B равна единице (они соединены напрямую), а взаимная удаленность C и D равна двум (они соединены цепочками C - B - D и C - A - B - D, длина кратчайшей цепочки равна двум).

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

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

Входные данные
На вход программы поступает число c (1<c<10 000).

Выходные данные
В первой строке  выведите два целых числа n и m – количество атомов и связей в разработанном нанокристалле, соответственно. Будем считать, что атомы нанокристалла пронумерованы от 1 до n. Следующие m строк должны содержать по два целых числа – пары атомов, которые следует соединить торсионными связями. Если решений несколько, выведите любое.

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

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

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

Речь политика в реальном времени оцифровывается, распознается и подается на вход программе как последовательность фраз. Каждая фраза состоит из слов, записанных в одну строку. Слово представляет собой последовательность символов, ограниченную с обеих сторон границами фразы, пробелами или знаками препинания (символами «.», «!», «?», «:», «-», «,», «;», «(» или «)»).

Слово считается подозрительным, если в него входит не более трех различных букв (любой символ, кроме пробелов и знаков препинания считается буквой, большие и маленькие буквы считаются различными). Например, слова «дом», «мама» или «шалаш» являются подозрительными, а слова «привет», «Шалаш» или «hello» – нет.

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

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

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

Вводится не более 1000 фраз, каждая из которых представляет собой строку не длиннее 250 символов. Фраза содержит только символы с ASCII кодами от 32 до 255.

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

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

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

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

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

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

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

Следующие две строки содержат по два вещественных числа – координаты точки, где Петя заезжает на дорожку, и точки, в которой Петя съезжает с дорожки. Гарантируется, что каждая из точек с высокой точностью лежит на одной из дорожек (расстояние от точки до центра одной из окружностей отличается от ее радиуса не более, чем на 10^-8). Точки могут лежать как на одной дорожке, так и на разных.

Выходные данные
Выведите  минимальное расстояние, которое следует проехать Пете по велосипедным дорожкам, чтобы попасть из дома в школу. Ответ должен отличаться от правильного не более, чем на 10^-4.

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

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

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

Если вершина \(Y\) — ребенок вершины \(X\), то говорят, что вершина \(X\) является родителем вершины \(Y\). У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

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

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

1. если вершина красная, то ее родитель — черный;

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

Примеры двоичного дерева, вершины которого раскрашены в два цвета, приведены на следующем рисунке.

Если считать закрашенные вершины черными, а незакрашенные — красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) — нет. Для дерева на рисунке (б) нарушается первое свойство — у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство — на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 — две.

Для заданного двоичного дерева подсчитайте число способов раскрасить его вершины в черный и красный цвет так, чтобы оно стало красно-черным деревом.

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

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

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

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

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

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

Степень точки \(A\) относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке \(A\), имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки \(A\) до некоторой точки многоугольника: \(d_{min}\) и \(d_{max}\). Степенью точки относительно данного многоугольника назовем минимум величины \(d_{min}\times d_{max}\) по всем таким лучам.

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

Будем считать, что наблюдательный центр находится в точке \((0, 0)\). Входной файл содержит описание полигона.

Формат входных данных
Первая строка содержит число \(n\) — количество вершин полигона (\(3 \le n \le 100\)). Следующие \(n\) содержат по два вещественных числа — координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают \(1000\) по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.

Формат выходных данных
Выведите одно число — степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на \(10^{-4}\).

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

Например, если повернуть пепелац, находящийся в точке \((3, 1)\) на 90 градусов против часовой стрелки относительно станции \(A\), то он переместится в точку \((-1, 3)\), если его затем повернуть на 90 градусов по часовой стрелке относительно станции \(B\), то он переместится в точку \((4, 2)\), если затем повернуть его вокруг станции \(B\) по часовой стрелке еще раз, он переместиться в точку \((3, -3)\).

Один житель планеты недавно решил отправиться на своем пепелаце в гости к другу. Житель проживает около точки с координатами \((x_1, y_1)\), а его друг — около точки с координатами \((x_2, y_2)\). Помогите жителю с помощью станций управления пепелацем оказаться как можно ближе к месту, где проживает его друг, чтобы потом меньше было идти по пустыне.

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

Формат входных данных
Входные данные содержит четыре целых числа — \(x_1\), \(y_1\), \(x_2\) и \(y_2\), они не превышают \(10^4\) по абсолютной величине.

Формат выходных данных
Выведите последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки \((x_1, y_1)\) как можно ближе к точке \((x_2, y_2)\).

Поворот по часовой стрелке относительно станции \(A\) обозначается как <<+A>>, поворот против часовой стрелки относительно станции \(A\) обозначается как <<-A>>, соответствующие повороты относительно станции \(B\) обозначаются как <<+B>> и <<-B>>. Выводите по одному перемещению на строке.

Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более \(10^6\) действий.