시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 512 MB91302944.615%

문제

현욱은 루빅스 큐브를 갖고 놀다가, 비슷한 퍼즐을 이차원에서 만들 수는 없을까하는 생각이 들었다.

고민 끝에 현욱은 2D Cube라는 이름의 퍼즐을 만들었다. 크기가 $N$($ 2 \le N \le 50 $)인 2D 큐브는 처음에 다음과 같은 상태로 시작한다.

  • 퍼즐은 좌우로 $N$칸, 상하로 $N$칸, 총 $N^2$개의 칸으로 구성된 이차원 정사각형 판의 형태로 나타난다.
  • 위에서부터 순서대로 첫째 줄은 모두 $1$, 두번째 줄은 모두 $2$, ... $N$번째 줄은 모두 $N$으로 채워져 있다. 즉, 위에서 $i$번째, 왼쪽에서 $j$번째 칸에 적힌 값을 $Val(i,j)$라고 하면, $Val(i,j) = i$가 성립한다. 

$N=5$일 때 2D Cube의 초기 상태

여기서, 큐브를 맞추기 위해 플레이어는 아래 두 가지 종류의 동작을 할 수 있다.

  • R x k : 위에서 x번째 줄의 모든 값을 오른쪽으로 k칸 만큼 민다($ 1 \le x \le N, 1 \le k \le N - 1 $). 맨 오른쪽에 있는 칸은 밀리면 맨 왼쪽으로 돌아온다. 즉, 각 줄의 맨 오른쪽 칸과 맨 왼쪽 칸은 연결되어 있다고 생각할 수 있다.
  • D x k : 왼쪽에서 x번째 줄의 모든 값을 아래쪽으로 k칸 만큼 민다($ 1 \le x \le N, 1 \le k \le N - 1 $). 마찬가지로 각 줄의 맨 위 칸과 맨 아래 칸은 연결되어 있다고 생각할 수 있다.

현욱은 위 동작을 이용해서 섞어놓은 큐브를 다시 맨 처음 상태로 되돌리고 싶다. 이 때, 동작 횟수가 너무 많으면 수행하기 힘들기 때문에 동작을 최대 $20000$번 아래로 수행해서 큐브를 맞추고 싶다. 현욱을 도와 $20000$번 이하의 동작으로 큐브를 맞추는 방법을 찾는 프로그램을 작성해보자. 주어진 입력에서 큐브를 $20000$번 이하의 동작으로 맞추는 방법은 항상 존재한다.

입력

첫 줄에 큐브의 크기 $N$이 주어진다($ 2 \le N \le 50 $).

둘째 줄부터 $N$ 줄에 걸쳐 큐브의 맨 윗줄부터 순서대로 큐브의 현재 상태를 나타내는 값이 주어진다.

출력

첫 줄에 수행한 연산 횟수 $K$를 출력한다($ 0 \le K \le 20000$).

둘째 줄부터 $K$ 줄에 걸쳐 수행한 연산을 순서대로 출력한다.

서브태스크 1 (16점)

$N = 2$

서브태스크 2 (43점)

위에서 $i$번째 줄의 $j$번째 칸의 값($Val(i,j)$)이 $j$임을 만족하는 데이터만 주어진다.

서브태스크 3 (66점)

추가 제한 없음

예제 입력 1

2
2 1
2 1

예제 출력 1

2
R 1 1
D 2 1

예제 입력 2

2
1 2
1 2

예제 출력 2

2
R 1 1
D 1 1

이 입력은 서브태스크 2의 조건을 만족한다.

예제 입력 3

3
1 1 2
2 1 3
3 2 3

예제 출력 3

3
D 2 2
R 3 1
D 3 1

출처

Contest > 소프트콘 > 제3회 소프트콘 B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.