시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 50 | 26 | 20 | 51.282% |
Luka has mastered the Towers of Hanoi puzzle and has invented a somewhat similar game with disks and rods. The puzzle consists of n wooden disks of different sizes and 36 rods. The disks are numbered with integers 1 through n in the order of increasing size. The rods are organized in 6 rows numbered 1 through 6 top to bottom and 6 columns numbered 1 through 6 left to right.
An example step
The puzzle starts with all n disks stacked in arbitrary order on the rod in the upper-left corner. In each step, a player can pick up a stack of one or more disks from the top of a single rod R and transfer them (without reordering) to the top of the rod that is either immediately below R or immediately to the right of R. The goal of the game is to have all the disks stacked on the rod in the lower-right corner neatly ordered by increasing size top to bottom.
Given the initial order of the disks on the rod in the upper-left corner, find any valid sequence of steps that solves the puzzle. You may assume that a solution always exists.
The first line contains an integer n (1 ≤ n ≤ 40 000) — the number of disks. The following line contains a sequence of n different integers d1, d2, . . . , dn (1 ≤ dk ≤ n) — the initial order of disks, bottom to top, on the rod in the upper-left corner.
Output m lines where m is the number of steps in your solution. The k-th line should contain four tokens rk , ck , pk , nk , describing the k-th step in your solution. The tokens should be as follows:
All steps have to be valid according to the rules above and solve the puzzle correctly.
6 1 6 5 4 3 2
1 1 D 6 2 1 D 6 3 1 D 6 4 1 D 6 5 1 D 6 6 1 R 6 6 2 R 6 6 3 R 6 6 4 R 6 6 5 R 5 6 5 R 1
In the example above, the first 9 steps simply move all the disks, without reordering, to the rod in row 6, column 5 — immediately to the left of the target rod in the lower-right corner. In the following step, the stack of five disks from the top of the rod — (6, 5, 4, 3, 2) bottom to top — are moved to the target rod. Finally, disk 1 is moved to the target rod obtaining the target bottom-to-top order (6, 5, 4, 3, 2, 1).