Bear and Three Colours
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Limak, a little polar bear, loves puzzles. He has recently found an especially interesting one.
There is a rectangular grid with N rows and N columns, both numbered 1 through N. Two cells are called adjacent if they share a side, i.e. all the cells other than those at boundary will have 4 adjacent cells. Every cell is colored in one of three colors. For convenience, let us label these colors by characters 'A', 'B' and 'C'.
In one move, Limak can choose any two adjacent cells of different colors and change them both to the third color. For example, if two adjacent cells have colors 'A' and 'C', then Limak can change them both to colour 'B'.
It's forbidden to choose two non-adjacent cells or to choose a cell with itself. It's allowed to choose two adjacent cells of the same color, but such a move does nothing.
The goal of the puzzle is to get all the cells of the grid in the same color. Limak is a smart bear, he would surely achieve that, but there is a problem, he is color-blind. He sees the size of the grid but he can't distinguish the colors of cells.
You are his only hope. Given an integer N, find a sequence of at most 100,000 moves such that it solves each grid of dimensions N × N.
The only line of the input contains a single integer N, denoting the dimension of the grid.
In the first line, output a single integer K (between 0 and 100,000, inclusive), denoting the number of moves.
Then print K lines. The i-th of them should contain four integers r1, c1, r2 and c2, meaning that in the i-th move, you choose cells (r1, c1) and (r2, c2). These two cells must be adjacent. All coordinates must be between 1 and N, inclusive. Here, (i, j) denotes a cell at the intersection of the i-th row and the j-th column.
- 2 ≤ N ≤ 20
- N is not divisible by 3. This condition guarantees that all initial grids are solvable.
There are eight subtasks, each worth 12 or 13 points. Every subtask contains only one test. Values of N are: 2, 4, 5, 8, 11, 13, 16, 20.
Checker and Correctness
The task will be graded by a custom checker. Your program will be judged AC (accepted) only if your solution follows the output format and the grader can't find any counterexample grid that breaks your solution. We tried to make the checker as strong as possible. The intended solution indeed solves all possible initial grids. It's possible that the checker is strong enough that all incorrect solutions are judged WA (wrong answer).
Input: 4 Output: 6 1 1 1 2 1 3 2 3 2 3 2 2 3 2 2 2 4 3 4 4 1 4 1 3
The provided output isn't correct because it doesn't solve all possible initial grids. Its only purpose is to show you a valid format. Below you can see how one example grid would change. Here we assume that columns are numbered from top to bottom, and rows are numbered from left to right. In every new grid two previously chosen cells are marked bold. Note that some moves don't affect the grid.AAAB AAAB AACB AACB AACB AACB AAAA
ABBA ABBA ABCA AAAA AAAA AAAA AAAA
AAAA AAAA AAAA AAAA AAAA AAAA AAAA
AABC AABC AABC AABC AABC AAAA AAAA
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.