Rotation PuzzleProblem code: STORO |
All submissions for this problem are available.
The sample Input/Output in the problem statement has been updated.
The constraints on M, N have been updated.
There was a problem with the scoring. The scoring has been updated (from K*/K to K*/K+1) and solutions have been re-judged.
Recently, with the release of the ultimate computing device bytePad, a platform game with the simple name "Rotation Puzzle" immediately became a phenomenon among Bytelandians. The game is extremely simple, yet quite additive. Here's the rule:
Given a MxN rectangular grid in which each cell contains a unique number from 1 to MxN. In each step, the player can pick any 2x2 subgrid and perform a rotation (whether clockwise or counterclockwise).
The task is to transform from the initial grid to the final configuration, using as few steps as possible.
The final configuration is the configuration
| 1 | 2 | ... | n |
| n+1 | n+2 | ... | 2n |
| ... | ... | ... | ... |
| (m-1)n+1 | (m-1)n+2 | ... | mn |
You may have guessed why this game is addictive: it requires a tremendous visualization skill!
Input
The first line contains a number T (about 5000), which is the number of test cases. Each test case has the following form.
The first line contains two numbers M and N (2 <= M, N <= 34).
The next M lines contains the description of the grid.
Each test case's input is separated by a blank line.
It is guaranteed that each input data has a solution.
Output
For each test case, output the result in the following format.
The first line contains a number K, the number of steps you need to solve the puzzle. K must not exceed 10000.
Each line of the next K lines contain three numbers c, i, j (c=0 or c=1, 1<=I < M, 1 <= J < N). (i,j) is the top-left coordinate of the 2x2 square that is need to be rotated. c=1 if the rotation if clockwise and c=0 if the rotation is counter-clockwise.
Prints a blank link after each test case's output.
Scoring
Given m and n, we pick a random positive integer K* and starting from the final configuration, we perform a random operation K* times to generate the test case. For each test case, your score is K*/K+1.
Example
Input:
2
2 3
1 5 2
4 6 3
2 3
5 6 2
1 4 3
Output:
1
0 1 2
2
1 1 1
0 1 2
| Author: | duc_admin |
| Date Added: | 6-04-2010 |
| Time Limit: | 7 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
If M comes before N as
If M comes before N as mentioned in input description, why are there 2 lines following in the sample but not 3 lines?
The sample input/output is
The sample input/output is incorrect. But the Test data is fine. The sample input output will be updated shortly. Sorry of the inconvenience caused.
if the output of a test case,
if the output of a test case, K exceed 10000, will it be judged as wrong answer ?
There was an issue with the
There was an issue with the size of the test cases. The problem has been re-judged. For those who do not have yet got an accepted solution please re-submit your solutions. Inconvenience is deeply regretted.
Should the scoring read
Should the scoring read K*/(K+1)?
@David: Yes. It should read,
@David: Yes. It should read, K*/(K+1)
Why I kept recieving Runtime
Why I kept recieving Runtime Error?
umm... can i get a
umm... can i get a clarification. If the value of K that we output is GREATER than 10000 for some test case, will it result in wrong answer or Runtime Error ?
Two beautiful simple problems
Two beautiful simple problems - Rotation puzzle and lights out and I absolutely dont have any clue in solving them. Editorial pls