Аттракцион
(Время: 1 сек. Память: 16 Мб Сложность: 50%)
На протяжении многих лет в Байтландии существует парк развлечений “Funny byte”, в котором представлено много различных аттракционов: колесо вычислений, веселые горки с трассами в форме интегралов, равнобедренная ромашка и многие другие.
В последние годы популярность “Funny byte” стала неуклонно падать. В целях привлечения посетителей руководство парка решило открыть новый аттракцион, который представляет собой сложный механизм.
Кресла аттракциона расположены в N рядов по M кресел в каждом. То есть каждое кресло характеризуется номером ряда и номером колонки, в котором оно находится. Ряды нумеруются последовательно сверху вниз начиная с единицы, колонки нумеруются слева направо начиная с единицы. Каждое кресло имеет свой уникальный номер. Кресло, находящееся в i-м ряду и в j-ой колонке, имеет номер (i-1)*M + j.
После посадки отдыхающих, кресла поднимают вверх над землей. И начинается веселье! Механизм аттракциона случайным образом производит некоторое количество операций. Под одной операцией понимается взаимная перестановка двух рядов либо двух колонок. При взаимной перестановке двух рядов или колонок каждое кресло в ряду или колонке заменятся на соответствующее ему кресло в другом ряду или колонке.
И вот аттракцион завершил свою работу. Но есть одна трудность! Кресла надо вернуть в начальное положение при помощи таких же операций. Как количество, так и сами операции не обязательно должны быть идентичны тем, которые производил аттракцион во время сеанса. Руководство парка решило, что вернуть кресла в начальное положение необходимо не более чем за 1000 операций.
Такая задача оказалась не по силам разработчикам механизма. Помогите им! От вас требуется разработать программу, позволяющую вернуть кресла в начальное положение. Гарантируется, что решение существует.
Входные данные
В первой строке входного файла INPUT.TXT заданы два натуральных числа N и M (1 ≤ N, M ≤ 250). В последующих N строках задано по M натуральных чисел, где j-е число в i+1-й строке соответствует номеру кресла после окончания сеанса аттракциона. Числа в строках разделяются одиночными пробелами.
Выходные данные
В первой строке выходного файла OUTPUT.TXT должно быть выведено количество операций перестановки K, которое не должно превышать 1000. Каждая из следующих K строк описывает одну операцию. Каждая операция описывается строкой вида Q X Y, где Q – символ 'R'(ASCII 82) либо символ 'C'(ASCII 67). Если Q равно 'R', то данная операция является перестановкой рядов, если Q равно 'C', то операция является перестановкой колонок. X и Y – два натуральных числа, соответствующие номерам рядов (колонок), которые будут переставлены в результате данной операции. Операции должны быть выведены в порядке осуществления, то есть последовательное применение которых позволит вернуть кресла в начальное положение.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 2
4 3
2 1 | 2
C 1 2
R 1 2 |
| 2 | 3 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15 | 0 |
| 3 | 4 5
10 7 9 8 6
15 12 14 13 11
20 17 19 18 16
5 2 4 3 1 | 5
R 1 4
C 1 5
C 3 4
R 2 4
R 3 4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
