Задача A. Манхэттенское расстояние

На плоскости дано $N$ различных точек. Расстоянием между точками (x1, y1) и (x2, y2) будем считать $|x1 - x2| + |y1 - y2|$. Для каждой точки требуется найти одну из ближайших к ней точек. Первая строка входного файла содержит целое число $N$ ($1$ < $N$ <= $10^5$). Следующие N строк содержат по два числа — координаты точек. Координаты — целые числа, по модулю не превышающие $10000$. Числа в строках разделены пробелами. Выходной файл должен содержать $N$ целых чисел, разделенных пробелом: i-е число есть номер одной из точек, ближайших к i-й. Точки нумеруются в том порядке, в котором они даны во входном файле, начиная с единицы. Вход

4
0 0
1 1
0 1
1 0

Ответ

3 4 1 1

Задача B. Подпоследовательность

Дана последовательность из $N$ целых чисел. Требуется найти ее $K$-ю в лексикографическом порядке возрастающую подпоследовательность. Подпоследовательность получается из исходной последовательности вычеркиванием нуля или более, но не всех, чисел. В возрастающей последовательности каждое число строго больше предыдущего, если оно существует. Последовательность $A = {a_1, a_2, \dots a_n}$ считается лексикографически меньше последовательности $B = {b_1, b_2, \dots b_m}$, если $A$ — префикс (начальная часть) последовательности B, или существует такое $k$, что $a_i = b_i$ при $i < k$, и $a_k < b_k$. Первая строка входного файла содержит два целых числа $N$ и $K$ ($1 < N <= 60$, $K >= 1$). На следующей строке записаны N целых чисел в пределах от $0$ до $10^9$. Числа в строках разделены пробелом. Гарантируется, что искомая подпоследовательность существует. Первая строка выходного файла должна содержать число $M$ — количество чисел в найденной подпоследовательности. Вторая строка должна содержать $M$ разделенных пробелом целых чисел — саму найденную подпоследовательность. Вход

3 2
1 1 2

Ответ

2
1 2

Задача C. Трубы

Сколькими способами на площадке из $NxM$ ячеек можно расставить трубы 11-ти различных типов, приведенных на рисунке

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

. На площадке могут остаться пустые ячейки. Ответ необходимо вывести по модулю числа P ($0$ <= ответ < $P$). Первая строка входного файла содержит три целых числа $N$, $М$ и $P$ (1 <= $N$ <= $8$, 1 <= $M$ <= $8$, 2 <= $P$ <= $10^9$). Числа разделены пробелом. Выходной файл должен содержать одно целое число — ответ на задачу. Вход

2 2 10

Ответ

1

Пример из ответа:

Задача D. Обои

Рабочим надо оклеить обоями одну стену шириной $X$ и высотой $Y$. Рулон обоев представляет собой прямоугольник шириной A и высотой B сантиметров, разделенный на B горизонтальных полосок одинаковой высоты. Полоски раскрашены в K цветов следующим образом (полоски нумеруются снизу вверх):
полоски номер 1, K + 1, 2K + 1, ... в цвет номер 1;
полоски номер 2, K + 2, 2K + 2, ... в цвет номер 2;
...
полоски номер K, 2K, 3K, ... в цвет номер K.
Стена должна быть обклеена так, чтобы цвета соседних по горизонтали полосок совпадали, а вертикально чередовались так же, как и в рулоне (однако цвет нижней полоски может быть любым). После оклеивания предыдущих стен осталось $N$ обрезков. Ширина каждого из обрезков равна ширине рулона. Какое минимальное количество целых рулонов надо докупить, чтобы оклеить стену полностью. Покупать часть рулона нельзя. Обои можно разрезать по границам полосок. Первая строка входного файла содержит шесть целых положительных чисел $X$, $Y$, $A$, $B$, $K$, $N$ (1 <= $X, Y, A, B$ <= $10^9$, 1 <= $K, N$ <= $5 * 10^5$, $X mod A = 0$, $B mod K = 0$). Следующие $N$ строк содержат по два целых числа — номер цвета нижней полоски обрезка и высоту обрезка в сантиметрах. Гарантируется, что каждый обрезок — часть целого рулона. Числа в строках разделены пробелами. Выходной файл должен содержать одно целое число — минимальное количество докупаемых рулонов. Вход

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

Ответ

2

Задача E. Раскраска графа

Рассмотрим неориентированный граф из $N$ вершин и $M$ ребер. Сколькими способами можно раскрасить его вершины в $K$ цветов? Две раскраски считаются одинаковыми, если существует такая перенумерация вершин графа, при которой список ребер остается тем же, и цвета соответствующих вершин совпадут. К примеру, две раскраски на рисунке одинаковы (соответствующая перенумерация: 1->1, 2->2, 3->4, 4->3).

Первая строка входного файла содержит три целых числа $N$, $М$ и $K$ (1 <= $K$ <= 10, 1 <= $N$ <= 10, 1 <= $M$ <= 100). Следующие $M$ строк содержат по два целых числа в пределах от 1 до $N$ — ребра графа. Граф может содержать кратные ребра и петли. Каждое ребро встречается не более 7 раз. Числа в строках разделены пробелом. Выходной файл должен содержать одно целое число — количество различных раскрасок. Вход

4 3 2
1 2
2 3
2 4

Ответ

8

Задача F. Многоугольник

От вас требуется посчитать, сколько точек с целочисленными координатами лежит внутри или на границе заданного простого многоугольника. Стороны многоугольника не пересекаются. Первая строка входного файла содержит целое число $N$ (1 <= $N$ <= $10^5$). Следующие $N$ строк содержат по два вещественных числа по модулю не превышающих 10000 и имеющих не более чем три знака после запятой — (x, y) координаты точек многоугольника в порядке обхода (x, y не целые). Периметр многоугольника не превышает $10^6$ (1,000,000). Числа в строках разделены пробелами. Выходной файл должен содержать одно целое число — ответ на задачу. Вход

3
14.815 43.958
21.457 34.883
21.802 50.559

Ответ

48