Алгоритмы

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

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

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

Однако, при разработке плана захвата обнаружилось две трудности. Во-первых, выяснилось, что маг согласен принять участие в операции только если все маги, которые будут направлены в королевство, будут представлять ту же силу, что и он. То есть либо все участвующие в захвате маги должны быть светлыми, либо все они должны быть темными. Во-вторых, общее число магов, которые могут быть направлены в королевство не должно превышать K. Единственная надежда верховных магов заключается в том, что K достаточно велико, 2^k >= N.

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

Входные данные
В первой строке вводятся целые числа N и K ( 2≤N≤256, 2^k ≥ N, K≤N).

Следующие N строк содержат по N целых чисел каждая. На i-ой позиции i-ой из этих строк расположено число 0, которое означает, что город не соединен дорогой сам с собой. Для всех j≠i число на j-ой позиции i-ой из этих строк равно 1, если i-ый город соединен с j-ым белой дорогой, и равно 2, если они соединены черной дорогой. Числа в строках разделены пробелами.

Гарантируется, что входные данные корректны, то есть если i-ый город соединен с j-ым белой дорогой, то и j-ый соединен с i-ым белой дорогой, аналогично в случае черных дорог.

Выходные данные
Если захватить королевство при заданных условиях невозможно, выведите единственное число 0. В противном случае в первой строке выведите 1, если удастся захватить королевство с использованием светлых магов, и 2, если требуется использовать черных магов. В следующей строке выведите число L≤K – количество использованных магов. Третья строка должна содержать L целых чисел – номера городов, в которые следует направить магов. Заметьте, что вам не требуется минимизировать L. Если решений несколько, выведите любое.

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

Входные данные
В первой строке входных данных содержится число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000).

В каждой из следующих N строк записаны по два числа x_i, y_i – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 10⁶. Некоторые точки могут совпадать.

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

Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".

Для заданного числа K слово называется почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при K = 2 слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).

Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).

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

Входные данные
В первой строке вводятся два натуральных числа:N (1 ≤ N ≤ 5 000) – длина слова и K (0 ≤ K ≤ N).

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

Выходные данные
Требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).

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

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

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

Сначала вводится число N — количество отрезков (1≤N≤1000). Далее идет N четверок чисел X_i1, Y_i1, X_i2, Y_i2 задающих координаты концов отрезков. Все эти числа целые, по модулю не превосходящие 10000.

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

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

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

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

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

В результате небольшого исследования Иванушка установил, между какими компаниями существует взаимное доверие (причем всегда если компания доверяет компании B, то компания B доверяет компании A).

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

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

Будем считать, что Иванушка — честный предприниматель и он никогда не подтасовывает рассылаемые им списки.

Входные данные
В первой строке входных данных содержится число N — количество фирм (1≤N≤2000). Далее идут N чисел, описывающих ответ фирмы на первое предложение Иванушки (1 — согласие, 0 — отказ). Далее задается число M (0≤M≤200000) — количество пар компаний, между которыми существует доверие. Далее следуют M пар чисел, задающих номера фирм, между которыми существует взаимное доверие (числа в паре не могут быть одинаковыми). Любая пара компаний упоминается в этом списке не более одного раза.

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

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


Входные данные
Сначала вводятся два положительных числа X, Y, задающих координаты правого верхнего угла прямоугольника. Прямоугольник расположен в системе координат так, что левый нижний его угол имеет координаты 0,0 и стороны параллельны осям координат.

Далее записано целое число N - количество разрезов (1≤N≤200). Далее описываются сами разрезы. Все разрезы делались вдоль  прямых. Каждая прямая, соответствующая разрезу, задается тремя числами A, B, C такими, что все точки (x,y) этой прямой (и только они) удовлетворяют уравнению Ax+By+C=0 (при этом всегда A2+B2>0).

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

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

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

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

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

Входные данные
Комната Пети и ее план имеют форму прямоугольника. Первая строка содержит два вещественных числа: ширину X и длину Y комнаты Пети (1≤X≤1000, 1≤Y≤1000). Комната расположена в декартовой прямоугольной системе координат так, что углы комнаты расположены в точках с координатами (0,0), (X,0), (X,Y), (0,Y).

Вторая строка содержит восемь вещественных чисел, описывающих положение углов плана комнаты в той же самой системе координат. Сначала задаются координаты того угла плана, который соответствует углу комнаты с координатами (0,0), затем — (X,0), (X,Y), наконец, (0,Y). Гарантируется, что входные данные корректны, то есть план является прямоугольником, линейные размеры плана находятся в полном соответствии с линейными размерами комнаты, план не выходит за границы комнаты.

Все числа заданы с точностью 5 знаков после десятичной точки. План выполнен в масштабе не менее 0.0001 и не более 1. Масштаб не может быть равен 1. Карта расположена лицевой стороной вверх.

Выходные данные
В первую строку выведите 2 вещественных числа — координаты неподвижной точки плана и пола. Ответ нужно выдать с 3 знаками после десятичной точки.

K членов Жюри Десятой Всероссийской олимпиады школьников по информатике решили отметить столь круглую годовщину в одном из лучших ресторанов на Невском проспекте. На десерт вниманию Жюри предложили торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в основании. Жюри вооружается десертными ножами и собирается справедливо разделить торт на K частей равного объема. Ножами можно проводить прямые вертикальные разрезы от одной границы торта до другой; различные разрезы могут иметь общие точки лишь в своих концевых вершинах.

Напишите программу, помогающую членам Жюри построить требуемые K-1 разрезов.

Входные данные
В первой строке входных данных содержатся два целых числа K и N (1 <= K, N <= 50). Далее следуют N пар вещественных чисел - координаты последовательно расположенных вершин N-угольника.

Выходные данные
Каждый из K-1 разрезов в выходных данных должен быть представлен четверкой вещественных чисел с не менее чем 10 знаками после запятой - координатами концов соответствующего разреза. Все числа должны быть разделены пробелами и/или символами перевода строки.

Есть две системы координат - первая и вторая. Вторая система устроена так, что ее центр в первой системе имеет координаты (A,B). Ее оси параллельны осям первой системы. При этом точка, которая во второй системе имеет координаты (1,0) в первой имеет координаты (C,B), а точка, имеющая во второй координаты (0,1) - координаты (A,D).

Дана точка, которая в первой системе имеет координаты X1,Y1.
Какие координаты она будет иметь во второй системе?
Какие координаты будет иметь точка в первой системе, если ее координаты во второй - X2, Y2?

Входные данные
Даны вещественные числа A, B, C, D, X1, Y1, X2, Y2.

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

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

Входные данные
Сначала вводится  число N - количество точек, 3<=N<=100000. Далее идут N пар чисел, задающих координаты точек.  Координаты - вещественные числа.

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

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

Входные данные
Сначала вводится число N (3<=N<=100). Далее идут N пар вещественных чисел, задающих координаты вершин многоугольника. Последние два вещественных числа задают координаты точки.

Выходные данные
Выведите сообщение YES, если точка лежит внутри многоугольника, или NO, если нет. Гарантируется, что точка не лежит на границе многоугольника.

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

Решите задачу быстрым методом

Входные данные
Сначала вводится число N (3<=N<=100). Далее идут N пар вещественных чисел, задающих координаты вершин многоугольника. Последние два вещественных числа задают координаты точки.

Выходные данные
Выведите сообщение YES, если точка лежит внутри многоугольника, или NO в противном случае. Гарантируется, что точка не лежит на границе многоугольника.

Заданы полярные координаты двух точек на плоскости. Требуется найти расстояние между этими точками.

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

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

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

Входные данные
Сначала вводится число N - количество вершин многоугольника (3<=N<=100), затем N пар целых чисел, задающих координаты его вершин.

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

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите три числа X, Y, R, задающие координаты центра и радиус окружности, описанной вокруг треугольника, образованного данными точками. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите три числа: X, Y, R, задающие координаты центра и радиус окружности, вписанной в треугольник, образованный данными точками. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

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

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

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

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3. Все числа целые, по модулю не превосходят 1000.

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

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

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

Команда	Обозначение	Действия робота
Перемещение	(X)	Переместиться вперед на X километров, прокладывая за собой оросительный канал
Поворот налево	L	Повернуть налево на 90o
Поворот направо	R	Повернуть направо на 90o

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

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

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

Входные данные
Входные данные содержат команды поворота исходной программы в том порядке, в котором они в ней следовали. Каждая команда представляет собой символ «L» либо «R», команды друг от друга не отделяются. Количество команд не превышает 30 000.

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