Задача 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

Задача G. Google Maps

Вы пользовались сервисом Google Maps? http://kh3.google.com/kh?n=404&v=14&t=trtrstsrtstrt – это город Алматы. Параметр t формируется так: вся Земля это квадрат, заданный строкой «t»

, этот квадрат делится на 4 равных квадрата: «tq», «tr», «tt», «ts»

, далее каждый из полученных квадратов рекурсивно делится на 4 квадрата, добавляя к строке параметра какой-либо суффикс: «q» (левый верхний), «r» (правый верхний), «t» (левый нижний), «s» (правый нижний). Как вычислить параметр t, если вы знаете, где находитесь? Пусть левый нижний угол квадрата всей Земли имеет координаты (0,0), длина его стороны равна 2 в степени $N$. Необходимо определить строку параметра t для квадрата минимального размера, содержащего точно внутри себя (не на границе) точку P с целочисленными координатами (x,y). Входной файл содержит три целых числа – N (0 <$N$ < 1000) и координаты x и y точки Р, 0 < x,y < $2^N$ (2 в степени N). Выходной файл должен содержать одну строку – ответ на задачу. Вход

8 5 3

Ответ

tsq

правый нижний левый верхний

Задача H. Звездное небо

Денис Назаров, Уфа

Ясным зимним вечером член жюри республиканской олимпиады по информатике Иван Васильевич, не торопясь, шел домой. Взгляд его время от времени блуждал по безоблачному ночному небу, которое поражало своей неземной красотой. Придя домой, он решил составить карту звездного неба таким образом, чтобы звезды были расположены на координатной плоскости только в точках с целочисленными координатами. Единицей длины и ширины на координатной плоскости решено было выбрать 1 световой год. При этом Иван Васильевич захотел поделить звезды на созвездия по следующему правилу: звезда принадлежит некоторому созвездию, если в этом созвездии найдется еще хотя бы одна такая звезда, расстояние до которой на координатной плоскости не больше $К$ световых лет. Звезда не может принадлежать двум разным созвездиям сразу, и любое созвездие содержит хотя бы одну звезду. После этого Иван Васильевич решил определить центр созвездия следующим образом: центром созвездия назовем такую звезду, при удалении которой из карты, созвездие распадется на несколько созвездий. У одного созвездия может быть несколько центров. Созвездия, которые состоят из 2 и менее звезд, по определению не могут иметь центров. Помогите Ивану Васильевичу определить центры всех созвездий. Входной файл содержит координаты всех звезд (xi,yi). Координаты звезд попарно различны. Количество звезд меньше 3000, но больше 1. Координаты звезд – целые числа, по абсолютному значению меньшие 214. В последней строке расположено единственное целое неотрицательное число $K$, меньшее $10^9$. Ваша программа должна вывести в выходной файл два целых числа – количество созвездий и общее количество их центров на звездной карте. Вход

4
0 0
1 1
0 1
1 0

Ответ

3 4 1 1