Информатика

В точке (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\) после расстановки в нем скобок. На второй строке выведите количество целых чисел среди этих значений.

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

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

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

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

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

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

Дан набор натуральных чисел: a₁, …, a_N. По этому набору строится таблица чисел размером N x N по следующему правилу: в клетку i-го столбца j-й строки записывается большее из чисел a_i и a_j при i ≠ j (если a_i = a_j, то записывается это число); на пересечении i-го столбца и i-й строки записывается число 0.

Дана таблица чисел. Требуется определить, могла ли она быть построена по данным правилам из какого-либо набора чисел a₁, …, a_N.

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

Выходные данные
В одну строку выведите через пробел числа a₁, …, a_N. Если решений несколько, выведите любое из них. Если набора, удовлетворяющего данной таблице, не существует, выведите одно число "-1".

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

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

Входные данные
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.

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

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

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

Календарь состоит из блоков, каждый из которых соответствует одному месяцу. Блоки расположены в виде таблицы из \(k\) столбцов и \(12/k\) строк (\(k\) выбирается делителем числа 12). Месяцы выводятся в следующем порядке: первая строка содержит блоки, соответствующие месяцам с первого по \(k\)-ый, следующая — с \((k + 1)\)-го по \(2k\)-ый, и т. д.

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

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

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

Формат входных данных
Входной файл содержит описание года, календарь для которого следует вывести — три числа: \(d\) — день недели, на который приходится первое января (\(1 \le d \le 7\)), \(l\) — является ли год високосным (\(l = 1\) означает, что год является високосными, \(l = 0\) — что не является) и \(k\) — количество столбцов в календаре (\(k\) — одно из чисел \(1, 2, 3, 4, 6, 12\)).

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

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

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

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

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

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

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

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

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

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

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

При разработке программ для просмотра веб-страниц одной из наиболее сложных задач является корректное отображение таблиц. Компания <<Kozilla>>, в которой вы работаете, планирует разработать новую версию браузера <<Waterrat>> для работы в терминальном режиме, и просит вас написать фрагмент ядра отображения веб-страниц, ответственный за формирование структуры таблиц.

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

Таблица состоит из строк, каждая строка состоит из одной или нескольких ячеек, \(j\)-я ячейка \(i\)-й строки имеет ширину \(a_{i,j}\).

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

Формат входных данных
Первая строка содержит \(n\) — количество строк в таблице (\(1 \le n \le 100\)). Следующие \(n\) строк входного файла содержат описание строк таблицы.

Описание каждой строки включает число \(m_i\) — количество ячеек этой строки, и \(m_i\) целых чисел \(a_{i,1}, a_{i,2}, \dots, a_{i,m_i}\) — ширину каждой из ячеек строки (\(1 \le m_i \le 10\), \(1 \le a_{i,j} \le 20\)).

Формат выходных данных
Выведите символическое изображение структуры таблицы.

Изображение \(i\)-й строки таблицы должно начинаться изображением горизонтальной линии, составленным из символов <<+>> (плюс) и <<->> (минус). Затем должна следовать строка, содержащая пробелы и символы <<|>> (вертикальная черта). Первым символом строки должна быть вертикальная черта, затем \(a_{i,1}\) пробелов, затем вертикальная черта, затем \(a_{i,2}\) пробелов, и так далее, всего \(m_i\) блоков пробелов. После последнего блока должна следовать вертикальная черта. После последней строки таблицы также должно следовать изображение горизонтальной линии.

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

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

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

Если вершина \(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\) действий.

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

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

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

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

На рисунке приведена возможная схема метро, соответствующая второму примеру.

Формат входных данных
В первой строке содержится число \(k\) — количество линий метро в городе (\(1 \le k \le 10\)). Все линии пронумерованы от 0 до \(k - 1\), кольцевая линия имеет номер 0. Во второй строке записано число \(n\) — количество пересадочных станций. Каждая из следующих \(n\) строк описывает линии, пересекающиеся на соответствующей пересадочной станции, причем сначала следуют описания пересадочных станций, расположенных на кольцевой линии, в порядке их расположения на ней. Описание каждого узла начинается с количества пересекающихся в нем линий, затем следуют номера линий.

Формат выходных данных
Выведите слово YES, если по описанию можно построить схему метро, и NO в противном случае.

Вася пишет новую версию своего офисного пакета <<Closed Office>>. Недавно он начал работу над редактором <<Dword>>, входящим в состав пакета.

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

Документ в формате редактора <<Dword>> представляет собой последовательность абзацев. Каждый абзац представляет собой последовательность элементов — слов и рисунков. Элементы одного абзаца разделены пробелами и/или переводом строки. Абзацы разделены пустой строкой. Строка, состоящая только из пробелов, считается пустой.

Слово — это последовательность символов, состоящая из букв латинского алфавита, цифр, и знаков препинания: <<.>>, <<,>>, <<:>>, <<;>>, <<!>>, <<?>>, <<->>, <<’>>.

Рисунок описывается следующим образом: <<(image параметры рисунка)>>. Каждый параметр рисунка имеет вид <<имя=значение>>. Параметры рисунка разделены пробелами и/или переводом строки. У каждого рисунка обязательно есть следующие параметры:

Документ размещается на бесконечной вверх и вниз странице шириной \(w\) пикселей (разбиение на конечные по высоте страницы планируется в следующей версии редактора). Одна из точек на левой границе страницы условно считается точкой с ординатой равной нулю. Ордината увеличивается вниз.

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

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

Слова размещаются следующим образом. Считается, что каждый символ имеет ширину \(c\) пикселей. Перед каждым словом, кроме первого во фрагменте, ставится пробел шириной также в \(c\) пикселей. Если слово помещается в текущем фрагменте, то оно размещается на нем. Если слово не помещается в текущем фрагменте, то оно размещается в первом фрагменте текущей строки, расположенном правее текущего, в котором оно помещается. Если такого фрагмента нет, то начинается новая строка, и поиск подходящего фрагмента продолжается в ней. Слово всегда <<прижимается>> к верхней границе строки.

Размещение рисунка зависит от его расположения относительно текста.

Если расположение рисунка относительно текста установлено в <<embedded>>, то он располагается так же как слово, за тем исключением, что его ширина равна ширине, указанной в параметрах рисунка. Кроме того, если высота рисунка больше текущей высоты строки, то она увеличивается до высоты рисунка (при этом верхняя граница строки не перемещается, а смещается вниз нижняя граница). Если рисунок типа <<embedded>> не первый элемент во фрагменте, то перед ним ставится пробел шириной \(c\) пикселей. Рисунки типа <<embedded>> также прижимаются к верхней границе строки.

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

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

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

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

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

По заданным \(w\), \(h\), \(c\) и документу найдите координаты верхних левых углов всех рисунков в документе.

Формат входных данных
Первая строка содержит три целых числа: \(w\), \(h\) и \(c\) (\(1 \le w \le 1000\), \(1 \le h \le 50\), \(1 \le c \le w\)).

Далее следует документ. Размер входного файла не превышает 1000 байт. Гарантируется, что ширина любого слова и любого рисунка не превышает \(w\). Высота всех рисунков не превышает \(1000\). Относительное смещение всех рисунков типа <<floating>> не превышает \(1000\) по абсолютной величине.

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

В комнате у Аркадия Семеновича Тапкина стоят электронные часы. Цифры на этих часах показываются в специальной псевдографике. А именно каждое поле, на котором изображается цифра, состоит из \(w\) ячеек в ширину и \(h\) ячеек в высоту (при этом ячейки на поле имеют форму квадратов).

Но недавно у Аркадия Семеновича появилась проблема. Последнее время он стал плохо видеть. В связи с этим он хочет увеличить изображение этих цифр. Он уже приладил старый \(19''\) монитор к часам, и теперь дело осталось за малым. Осталось написать программу, которая будет рисовать цифры на дисплее. Аркадий Семенович хочет увеличить изображение в \(k\) раз и сделать толщину линий равной \(d\). Помогите ему в этом.

Опишем более формально понятие <<увеличить в \(k\) раз>>. Занумеруем ячейки поля \(w \times h\) сверху вниз и слева направо. Таким образом, верхняя левая ячейка имеет координаты \((0, 0)\), правая нижняя — \((w - 1, h - 1)\), правая верхняя — \((w - 1, 0)\), левая нижняя — \((0, h - 1)\). Кроме этого, введем декартову прямоугольную систему координат так, что начало координат находится в центре верхней левой ячейки, ось \(Ox\) направлена вправо, ось \(Oy\) — вниз, длину единичного отрезка примем равной длине стороны ячейки. Таким образом, координаты центра ячейки совпадают с ее координатами во введенной нумерации.

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

Увеличенная в \(k\) раз цифра рисуется на поле размером \((w - 1) \cdot (k - 1) + w\) ячеек по горизонтали на \((h - 1) \cdot (k - 1) + h\) ячеек по вертикали.

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

После этого, для того, чтобы получить толщину линий равную \(d\), дополнительно закрашиваются те ячейки, центры которых располагаются на расстоянии, не превышающем \((d - 1)\) от центров основных ячеек. Расстоянием между точками \(A(x_A, y_A)\) и \(B(x_B, y_B)\) будем называть число \(\rho(A, B) = |x_A - x_B| + |y_A - y_B|\).

По описанию цифры и параметрам \(k\) и \(d\) выведите изображение цифры, увеличенное в \(k\) раз, с толщиной линий \(d\).

Формат входных данных
Первая строка содержит целые числа \(k\) и \(d\) (\(1 \le k \le 100\), \(1 \le d \le 500\)). Вторая строка содержит целые числа \(w\) и \(h\) (\(1 \le w, h \le 10\)).

Третья строка содержит целое число \(n\) (\(1 \le n \le 100\)) — количество отрезков в описании цифры. Далее следуют \(n\) строк, каждая из которых описывает один отрезок. Описание отрезка состоит из четырех целых чисел: \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(0 \le x_1, x_2 < w\), \(0 \le y_1, y_2 < h\)) — координат концов отрезка.

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

Формат выходных данных
Выходные данные должны содержать ровно \((h - 1) \cdot (k - 1) + h\) строк по \((w - 1) \cdot (k - 1) + w\) символов в каждой, \(j\)-ый символ \(i\)-ой строки должен быть равен символу <<*>> (звездочка), если ячейка с центром в точке \((j,i)\) закрашена, и символу <<.>> (точка) — иначе.

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

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

Входные данные
Во входном файле сначала записано число K (0 < K < 101) и далее K2 неотрицательных целых чисел, не превосходящие 20000, описывающих матрицу K x K, времен решения каждым из участников каждой из задач.

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

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

Города во Флатопии пронумерованы от 1 до N и город с номером i имеет декартовы координаты (x_i, y_i). Каждая дорога соединяет ровно два города. Все дороги (уже построенные и те, которые собираются построить) лежат на прямых линиях и их длина равна декартовому расстоянию между городами. Все дороги имеют двухстороннее движение. Дороги могут пересекаться, но водитель может переезжать с дороги на дорогу только в городах.

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

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

Первая строка входного файла содержит единственное целое число N (1 <= N <= 750), обозначающее число городов. Следующие N строк содержат по два целых числа, x_i и y_i, разделённых пробелом. Эти числа являются координатами соответствующих городов (для i от 1 до N). Координаты по модулю не превосходят 10000. Никакие два города не совпадают.

Следующая строка содержит одно число M (0 <= M <= 1000), представляющее количество уже построенных дорог. Следующие M строк содержат по два целых числа, разделённых пробелом. Эти два числа обозначают пару городов, которые уже соединены дорогами. Каждая пара соединена не более чем одной дорогой.

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

Наверняка все слышали про карточную игру "Покер". В джентльменском покере все, как и в обычном - игроки сидят за круглым столом, ставят ставки, повышают их, и кто-то в конце каждого раунда забирает выигрыш - банк. Только в джентльменском покере выигрыш раунда достается не одному игроку, а делится на K человек (K - степень щедрости). А точнее, банк делится поровну между победителем раунда и следующими K-1 игроками, сидящими за выигравшим (за последним сидит первый игрок). В случае, если сумма выигранного банка не делится поровну между K игроками, то излишек забирает победитель. Так, например, если играют 4 человека и степень щедрости равна 3, то при выигрыше первого игрока банк поделится между 1-ым, 2-ым и 3-им игроками, а при победе четвертого - между 4-ым, 1-ым и 2-ым. Ваша задача по протоколу игры сосчитать, сколько денег у каждого из игроков оказалось в конце игры. Т.к. покер джентльменский, то разрешается играть в долг.

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

В первой строке содержатся три положительных целых числа: N, K и S, где N - число игроков (игроки пронумерованы от 1 до N по направлению хода игры), K - степень щедрости и S - начальная сумма денег у каждого игрока, 2 <= N <= 30000, 1 <= K <= N, S <= 10500. Гарантируется, что долг игрока будет не менее, чем -2¹⁵-1 и выигрыш не более, чем 2¹⁵. Далее идут строки, описывающие протокол игры. Протокол игры состоит не более, чем из 2¹⁰ событий. Возможные строки протокола игры:
BET A B - игрок под номером А добавляет в банк сумму B. В начале каждого раунда банк пуст.
WIN A - означает конец раунда и игрок под номером А забирает банк и делит его со следующими K-1 игроками.
END - означает конец игры. Данная строка является последней во входном файле.

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

Вывести конечные суммы, которые оказались у игроков к концу игры. Первое число - сумма денег первого игрока, затем через пробел - сумма второго, и т.д. до последнего. Всего N чисел.

Входные данные
Вводятся 5 чисел: a, b, c, d и e.

Выходные данные
Найдите все целые решения уравнения ( ax³ + bx² + cx + d ) / ( x - e ) = 0 на отрезке [0,1000] и выведите их количество.