Цветные перестановки

Задача A Цветные перестановки

Имя входного файла:	a. in
Имя выходного файла:	a. out
Ограничение по времени:	3 секунды
Ограничение по памяти:	32 мегабайта
Максимальный балл:	100 баллов

Даны две перестановки A=(a1, a2,…, aN) и B=(b1, b2, …, bN) целых чисел от 1 до N (перестановкой чисел от 1 до N называется последовательность длины N, в которой каждое из чисел от 1 до N встречается ровно один раз).

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

Например, если A=(1, 2, 3), а B=(2, 3, 1), то можно покрасить 1 в красный цвет, а 2 и 3 — в синий, после чего преобразовать A в B так: (1, 2, 3) → (2, 1, 3) → (2, 3, 1).

Ваша задача: написать программу для нахождения искомой раскраски чисел от 1 до N.

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

В первой строке входного файла записано число N (1≤N≤100000). Во второй и третей строках указаны перестановки A и B соответственно. Числа в перестановках отделены пробелами.

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

Если искомой раскраски не существует, то выведите в выходной файл слово NO. В противном случае выведите строку из N символов. i-й символ данной строки должен определять цвет числа i (1≤i≤N), причем красный цвет представляется символом R, зеленый — G, а синий — B.

Примеры

a. in	a. out
3 1 2 3 2 3 1	RBB
4	NO

Задача B Дороги

Имя входного файла:	b. in
Имя выходного файла:	b. out
Ограничение по времени:	3 секунды
Ограничение по памяти:	64 мегабайта
Максимальный балл:	100 баллов

В некоторой плоской стране есть N городов, заданных своими координатами (xi,yi), i=1..N, а также M дорог, соединяющих города. Требуется построить некоторые дополнительное число дорог (возможно, нулевое), так чтобы из любого города можно было доехать в любой другой, двигаясь по дорогам. При этом сумма длин вновь построенных дорог должна быть минимально возможной.

Замечания

·  Дорога представляет собой отрезок с концами в городах, которые она соединяет, и предполагается неориентированной, то есть движение по ней возможно в обе стороны.

·  Точки пересечения дорог не выполняют никакой функции, в частности, “пересадка” в них невозможна.

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

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

В первой строке входного файла записаны числа N и M (1≤N≤3000). В последующих N строках содержатся координаты (xi,yi) городов, по одной паре в строке. Координаты представляют собой целые числа, не превышающие по модулю 104. Затем следуют M строк, описывающих дороги, по одной в строке. Каждая дорога задается указанием пары номеров городов, которые она соединяют. Числа в строках разделяются пробелами.

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

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

Примеры

b. in	b. out
3 1 0 0 3 0 0 1 1 2	1 1 3

Задача C Симпатичные таблицы

Имя входного файла:	c. in
Имя выходного файла:	c. out
Ограничение по времени:	3 секунды
Ограничение по памяти:	32 мегабайта
Максимальный балл:	100 баллов

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

Заданы две симпатичные таблицы: A и B. Требуется выяснить, можно ли от A перейти к B, если за один ход разрешается изменить значение одного элемента таблицы (ноль на единицу, а единицу на ноль), при этом необходимо, чтобы все промежуточные таблицы также были симпатичными. При этом число ходов в вашем решении не должно превышать 7MN.

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

В первой строке входного файла записаны числа N и M (1≤N,M≤1000). В последующих N строках содержится описание таблицы A (по M чисел в строке, разделенных пробелами), а в следующих за ними N строках — описание таблицы B в том же формате, что и A.

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

Если не существует способа перевести таблицу A в таблицу B c соблюдением указанных в условии ограничений, то выходной файл должен содержать число –1.

В противном случае в первой строке выходного файла должно располагаться число K шагов преобразования. В последующих K строках должно располагаться описание этим шагов, по одному в строке. Каждый шаг задается координатами (i, j) изменяемого элемента, где i — номер строки (1≤i≤N), а j — номер столбца (1≤j≤M). Числа в строках должны разделяться пробелами.

Примеры

c. in	c. out
2 2 0 0 1 0 0 1 0 0	2 1 2 2 1