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

Автор:Фольклор   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 16;

1 ≤ m ≤ 10;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
3

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

Автор:XII Командный чемпионат школьников Санкт-Петербурга по программированию   Ограничение времени:2 сек
Входной файл:zeroes.in   Ограничение памяти:8 Мб
Выходной файл:zeroes.out  
Максимальный балл:100  

Условие

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

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

1 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0
1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1
1 1 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0
1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1
1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 1 1
1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0
(красные нули выделены жирным шрифтом и подчеркнуты)

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

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

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

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

Выходной файл должен содержать одно число — количество красных нулей.

Ограничения

1 ≤ n < 231, 1 ≤ k ≤ 30

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

Входной файл (zeroes.in) Выходной файл (zeroes.out)
1
4 1
3
2
56 2
74

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

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

Программа для плоттера требует вывода последовательность отрезков в определённом порядке. Каждый отрезок задан координатами своих вершин M1(x1, y1) и M2(x2, y2). Процесс рисования заключается в следующем: плоттер чертит первый отрезок, потом по прямой передвигает перо к начальной или конечной точке второго отрезка и чертит его. Так продолжается до тех пор, пока все отрезки не будут нарисованы.

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

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

Входной файл содержит число N, за которым следует описание N отрезков в том порядке, в каком их и будет рисовать плоттер. Каждому из отрезков соответствует 4 числа x1 y1 x2 y2 — координаты точек M1 к M2 для соответсвующего отрезка. Все числа во входном файле целые.

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

Выходной файл должен содержать N чисел, разделенных пробелами, где i-е число равно 0, если i-й отрезок следует рисовать от M1 к M2, либо 1, если его следует рисовать от M2 к M1.

Ограничения

1 ≤ N ≤ 100000. Все координаты по модулю не превосходят 10000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 
0 0 1 1 
3 0 2 1
0 1

Problem D. Graveyard Design

Author:Nick Durov, Andrew Stankevich   Time limit:2 sec
Input file:graveyard.in   Memory limit:64 Mb
Output file:graveyard.out  
Maximum points:100  

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 s2 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

Input file contains n — the number of graves to be located in the graveyard.

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

1 ≤ n ≤ 1014.

Sample tests

No. Input file (graveyard.in) Output file (graveyard.out)
1
29
1
3  2 3 4
2
2030
2
4  21 22 23 24
3  25 26 27

Problem E. Honey and Milk Land

Author:Georgiy Korneev, Dmitriy Shtukenberg   Time limit:2 sec
Input file:honey.in   Memory limit:64 Mb
Output file:honey.out  
Maximum points:50  

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

Output the minimal morning flight cost in honey barrels. Since there is no smaller denomination, you must output the minimal integer number of honey barrels that would be sufficient to support the flight.

Constraints

1 ≤ n, e ≤ 1000.

Sample tests

No. Input file (honey.in) Output file (honey.out)
1
2 1
1
1
2
10 10
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
26
3
1 1
0

Problem F. K-th Number

Author:Andrew Stankevich   Time limit:2 sec
Input file:kth.in   Memory limit:128 Mb
Output file:kth.out  
Maximum points:100  

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[ij] 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

The first line of the input file contains n — the size of the array, and m — the number of questions to answer. The second line contains n different integer numbers not exceeding 109 by their absolute values — the array for which the answers should be given. The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 ≤ ijn, 1 ≤ kj - i + 1) and represents the question Q(i, j, k).

Output file format

For each question output the answer to it — the k-th number in sorted a[ij] segment.

Constraints

1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000.

Sample tests

No. Input file (kth.in) Output file (kth.out)
1
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
5
6
3

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

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

Входной файл содержит последовательность чисел.

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

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от  − 231 до 231 − 1.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1 3 0
1 2 3
2
5 -1 6 -5 5 0
5 6

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

Автор:VI Всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:numbers.in   Ограничение памяти:64 Мб
Выходной файл:numbers.out  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

Входной файл (numbers.in) Выходной файл (numbers.out)
1
X772KX
9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

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

Автор:VI Всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:pluk.in   Ограничение памяти:64 Мб
Выходной файл:pluk.out  
Максимальный балл:100  

Условие

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

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

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

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

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

Входной файл содержит четыре целых числа — x1, y1, x2 и y2, они не превышают 104 по абсолютной величине.

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

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

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

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

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

Входной файл (pluk.in) Выходной файл (pluk.out)
1
3 1
3 -3
-A
+B
+B
2
0 0
3 0
-B
-B

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

Автор:И. Олейников, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

Входной файл содержит числа N и M за которыми идут M пар чисел ai bi — номера площадей, соединенных i-й улицей (по улице, соединяющей площади ai и bi, можно проехать либо из ai и bi, либо из bi в ai). Две площади могут быть соединены больше чем одной улицей.

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

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

Ограничения

2 ≤ N ≤ 40000, 1 ≤ M ≤ 40000, 1 ≤ ai, biN

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
1 2 
2 3 
3 1
1
2
5 2 
1 2 
3 4
3

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

Автор:И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

Во входном файле содержится число N — количество ретрансляторов, за которыми следуют N − 1 пар чисел ui vi, означающих, что i-ый провод соединяет ретрансляторы ui и vi.

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

В выходном файле должно содержаться N чисел a1 a2… aN, где ai — нагрузка на i-ый ретранслятор.

Ограничения

1 ≤ N ≤ 100000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2
2 3
2 1 2
2
4
1 2
1 3
1 4
1 3 3 3

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

Автор:И. Туфанов, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

Во входном файле содержатся числа N M, где N — число серверов, M — число кабелей. За ними идут M пар чисел ai bi, — номера серверов, соединённых i-м кабелем. Сервер не может быть соединён сам с собой, но два сервера могут быть соединены несколькими кабелями.

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

В выходном файле должно содержаться M чисел di, равных 0, 1 или 2. di = 0 означает, что для соответствующего кабеля следует сохранить двустороннюю передачу данных, di = 1 — что следует фиксировать направление от ai к bi, di = 2 — что следует фиксировать направление от bi к ai. Если имеется несколько оптимальных решений, следует вывести любое из них.

Ограничения

1 ≤ N ≤ 2 × 105; 0 ≤ M ≤ 2 × 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
1 2
1 2
2 3
2
1
0
2
3 3
1 2
1 3
2 3
1
2
1

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

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

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

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

Граф задан во входном файле следующим образом: первая строка содержит числа N и M. Каждая из следующих M строк содержат описание ребра - два целых числа из диапазона от 1 до N - номера начала и конца ребра.

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

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

Ограничения

1 ≤ N ≤ 20000, 1 ≤ M ≤ 2000000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4
2
1 1 1 2 2 2

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

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:e.in   Ограничение памяти:64 Мб
Выходной файл:e.out  
Максимальный балл:100  

Условие

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

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

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

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

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

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

В выходной файл выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, выведите в выходной файл одно число  − 1 (минус один).

Ограничения

2 ≤ N ≤ 100, 1 ≤ M ≤ 20, 2 ≤ Pi ≤ 50.

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

Входной файл (e.in) Выходной файл (e.out)
1
5 2
4 1 2 3 4
2 5 3
3 1
0
2
5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
2
3
10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
1
4
4 2
2 1 2
2 3 4
1 3
-1

Problem O. Eulerian cycle

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  
Maximum points:100  

Statement

You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of following M lines contains a pair of vertex numbers, connected by some edge. There is at most one edge connecting two vertices.

Output file format

Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle. If there does not exist any Eiler cycle, output file must contain  − 1.

Constraints

1 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2
2 3
3 1
1 2 3 1

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

Автор:И. Туфанов, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

Во входном файле содержится число вершин многоугольника N. За ним следует N пар целых чисел xi yi, — координаты вершин многоугольника, перечисленных в порядке обхода. Граница многоугольника не имеет самопересечений, но многоугольник не обязательно является выпуклым.

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

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

Ограничения

3 ≤ N ≤ 100,  − 5000 ≤ xi, yi ≤ 5000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
-1 -1
-1 1
3 -1
2 4
2
4
0 0  0 1  5 1  5 0
1 12

Problem Q. Half of a convex polygon

Author:T. Chistyakov, A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:24 Mb
Output file:output.txt  
Maximum points:100  

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

Input file contains integer N, then N pairs of floating-point numbers xi yi describing the vertices of the polygon.

Output file format

Output a single number — the ordinate of the horizontal line dividing the polygon as requested. The result must be rounded to 10-2.

Constraints

3 ≤ N ≤ 1000000

1 ≤ xi, yi ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
1 1  1 3  3 3  3 1
2

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

Автор:Фольклор   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

Входной файла содержит число N, за которым следует N пар чисел x y — координаты точек.

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

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

Ограничения

2 ≤ N ≤ 100000. Все координаты — целые числа, не превышающие по модулю 16000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1
5 2
2 3
5

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

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:50  

Условие

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

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

Во входном файле содержатся целые числа XA YA XB YB XC YC — координаты точек A, B, C соответственно.

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

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

Ограничения

0 ≤ |XA|, |YA|, |XB|, |YB|, |XC|, |YC| ≤ 105

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2 0 0 2 2
2 2
2
-2 -3 1 3 4 -2
1.30120904214632 -0.720188590098661

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

Автор:Я. Штейнер   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 50

 − 104 ≤ xi, yi, ai, bi ≤ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
0 0
1 0
0 1
1
0.2 0.2
1 4
2 4
4 3

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

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

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

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

В первой строке входного файла записана длина слова. Во второй строке записано само слово длиной не более 2 × 105.

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abaa
aaab

1.516s 0.015s 57