Задача A. Домино (классика) ≡

Условие

Найти количество способов замостить домино 1 × 2 поле n × m.

Формат входного файла

Во входном файле содержатся числа n и m.

Формат выходного файла

В выходной файл выведите ответ.

Ограничения

1 ≤ n ≤ 16;

1 ≤ m ≤ 10;

Примеры тестов

2 3

3

Задача B. Цветные нули ≡

Условие

Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2,…, n. Получились числа 1, 10, 11, 100, 101, 110, 111, …

После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число k и в каждой строке, идя слева направо, выделил красным цветом каждый k-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, k + 1, 2 k + 1, … Например если k = 2, n = 56, то получились бы такие строки:

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4 1

3

56 2

74

Задача C. Плоттер ≡

Условие

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

Программа для плоттера требует вывода последовательность отрезков в определённом порядке. Каждый отрезок задан координатами своих вершин M₁(x₁, y₁) и M₂(x₂, y₂). Процесс рисования заключается в следующем: плоттер чертит первый отрезок, потом по прямой передвигает перо к начальной или конечной точке второго отрезка и чертит его. Так продолжается до тех пор, пока все отрезки не будут нарисованы.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2 
0 0 1 1 
3 0 2 1

0 1

Problem D. Graveyard Design ≡

Statement

King George has recently decided that he would like to have a new design for the royal graveyard. The graveyard must consist of several sections, each of which must be a square of graves. All sections must have different number of graves.

After a consultation with his astrologer, King George decided that the lengths of section sides must be a sequence of successive positive integer numbers. A section with side length s contains s² graves.

George has estimated the total number of graves that will be located on the graveyard and now wants to know all possible graveyard designs satisfying the condition. You were asked to find them.

The picture below illustrates the graveyard for the first example.

Input file format

Output file format

On the first line of the output file print k — the number of possible graveyard designs. Next k lines must contain the descriptions of the graveyards. Each line must start with l — the number of sections in the corresponding graveyard, followed by l integers — the lengths of section sides (successive positive integer numbers).

Change: sections must me enumerated in descending order.

Constraints

Sample tests

29

1
3  2 3 4

2030

2
4  21 22 23 24
3  25 26 27

Problem E. Honey and Milk Land ≡

Statement

Bad rumors are spreading over the Land of Honey and Milk. Informed people say that the milk in the famous grid of milk rivers is turning sour. Of course, the security service quickly found out that the people are informed by the Kingdom of Tar, which is jealous to tourist popularity of the land. However, this discovery does not help to stop these rumors. The government wants to prevent crisis of the tourist industry, so it wants to establish daily monitoring of the rivers.

A new Milk Security Department is established, which is responsible for preventing the milk from turning sour. It's equipped with powerful boilers and pasteurizer, so any danger for the milk can be quickly neutralized. To better fight the new threat, the department needs to know about possible dangers beforehand. They have a helicopter, capable to check milk freshness. The equipment is perfect. It's enough just to cross a river in any place in order to detect all its potentially dangerous places.

To start the Milk Security Department operations, the government needs to add funding of the Service to the Land budget. One of the issues is the morning route of the helicopter. The helicopter should check all the rivers in the shortest time. They need to determine the price of this flight to add it to the budget.

The grid consists of two sets of milk rivers. Rivers from the first set run from North to South, rivers from the second set — from East to West. The rivers are straight. The rivers from each set are parallel and the distance between the adjacent rivers is known. There are n rivers, running from North to South and e rivers, running from East to West.

The government needs to determine the minimal morning flight cost. Each kilometer costs 1 honey barrel, the Land national currency. The cost of take-off and landing is not included into this cost. You may freely choose the starting and ending points of the flight.

Input file format

The first line of the input file contains n and e. The second line contains n − 1 integer numbers that represent distances (in kilometers) between adjacent rivers running from North to South, listed from East to West. The third line contains e − 1 integer numbers that represent distances (also in kilometers) between adjacent rivers running from East to West, listed from North to South. The distance between any two adjacent rivers does not exceed 27 kilometers.

Output file format

Constraints

Sample tests

2 1
1

1

10 10
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2

26

1 1

0

Problem F. K-th Number ≡

Statement

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.

That is, given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: «What would be the k-th number in a[i…j] segment, if this segment was sorted?»

For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Input file format

Output file format

Constraints

Sample tests

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

5
6
3

Задача G. Сбалансированное дерево revisited ≡

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Задача H. Автомобильные номера ≡

Условие

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

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

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

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

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

Формат входного файла

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

Формат выходного файла

Примеры тестов

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача I. Планета Плюк ≡

Условие

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

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

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

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

Формат входного файла

Входной файл содержит четыре целых числа — x₁, y₁, x₂ и y₂, они не превышают 10⁴ по абсолютной величине.

Формат выходного файла

Выведите в выходной файл последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x₁, y₁) как можно ближе к точке (x₂, y₂).

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

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

Примеры тестов

3 1
3 -3

-A
+B
+B

0 0
3 0

-B
-B

Задача J. День бульдозериста ≡

Условие

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

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

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

Требуется определить минимально необходимое число бульдозеров.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 3
1 2 
2 3 
3 1

1

5 2 
1 2 
3 4

3

Задача K. Интернет по ЛЭП ≡

Условие

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

Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору. Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод, назовем нагрузкой на данный провод для i-го ретранслятора. Максимум из нагрузок на все провода для i-го ретранслятора называется нагрузкой на данный ретранслятор. Известно, что по проводам электросети сигнал может пройти от одного ретранслятора к другому единственным образом.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
1 2
2 3

2 1 2

4
1 2
1 3
1 4

1 3 3 3

Задача L. Репликация ≡

Условие

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

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

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

Рекомендуется рассмотреть частичные решения

• N ≤ 100

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 3
1 2
1 2
2 3

2
1
0

3 3
1 2
1 3
2 3

1
2
1

Задача M. Конденсация графа ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4

2
1 1 1 2 2 2

Задача N. Метро ≡

Условие

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

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

Формат входного файла

Во входном файле записано сначала число N — количество станций метро в городе. Далее записано число M — количество линий метро. Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

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

Формат выходного файла

Ограничения

Примеры тестов

5 2
4 1 2 3 4
2 5 3
3 1

0

5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5

2

10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8

1

4 2
2 1 2
2 3 4
1 3

-1

Problem O. Eulerian cycle ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2
2 3
3 1

1 2 3 1

Задача P. Морская метеорология ≡

Условие

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

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

Рекомендуется рассмотреть частичные решения для следующих случаев

• Участок — треугольник.
• Участок — прямоугольник со сторонами, параллельными осям координат.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
-1 -1
-1 1
3 -1

2 4

4
0 0  0 1  5 1  5 0

1 12

Problem Q. Half of a convex polygon ≡

Statement

You need to divide a non-degenerate convex polygon with a horizontal line into two parts of equal area.

The polygon is specified by N vertices in the clockwise order.

Input file format

Output file format

Constraints

3 ≤ N ≤ 1000000

1 ≤ x_i, y_i ≤ 1000000

Sample tests

4
1 1  1 3  3 3  3 1

2

Задача R. Пара ближайших точек ≡

Условие

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
1 1
5 2
2 3

5

Задача S. Точка Ферма-Торричелли ≡

Условие

Для заданных трёх точек A, B, C найти такую точку O, что AO + BO + CO — минимально.

Формат входного файла

Во входном файле содержатся целые числа X_A Y_A X_B Y_B X_C Y_C — координаты точек A, B, C соответственно.

Формат выходного файла

Выходной файл должен содержать два числа X_O Y_O — координаты точки O с точностью до 3-х знаков после запятой.

Ограничения

0 ≤ |X_A|, |Y_A|, |X_B|, |Y_B|, |X_C|, |Y_C| ≤ 10⁵

Никакие две точки не совпадают

Примеры тестов

4 2 0 0 2 2

2 2

-2 -3 1 3 4 -2

1.30120904214632 -0.720188590098661

Задача T. Задача Штейнера (приближение) ≡

Условие

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

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

Формат входного файла

В начале входного файла содержится число N. За ним следует N пар вещественных чисел x_i y_i - координаты точек.

Формат выходного файла

В начале выходного файла должно содержаться число дополнительных точек M, за которым должны следовать M пар вещественных чисел a_i b_i — координаты точек.

Далее выведите N + M − 1 пару целых чисел от 1 до N + M — описание отрезков. То есть, дополнительным вершинам присваиваются номера от N + 1 до N + M в том порядке, в котором они выведены участником.

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 50

 − 10⁴ ≤ x_i, y_i, a_i, b_i ≤ 10⁴

Примеры тестов

3
0 0
1 0
0 1

1
0.2 0.2
1 4
2 4
4 3

Задача U. Наименьший циклический сдвиг ≡

Условие

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

Формат входного файла

Формат выходного файла

Выведите получившееся слово.

Примеры тестов

abaa

aaab