Make It Zero
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Aleksandra is the most popular girl in the city. Each boy can only dream about dating with her. Other girls want to be like she.
Aleksandra is going to find boyfriend. Of course such a beauty needs someone special. That's why she is going to announce a quiz. Even you can try your chances. Apart from boys, girl loves math. That's why this quiz is going to be mathematical.
Girl has a matrix with N rows and M columns whose each element is from 0 to 4 inclusive. Let Ai,j be the jth element of the ith row. She likes 0, so she is going to get rid of all non zero numbers. In each turn she'll choose four integers:
- 1 ≤ x1 ≤ x2 ≤ N
- 1 ≤ y1 ≤ y2 ≤ M
and after for all pairs (i,j) such that:
- x1 ≤ i ≤ x2
- y1 ≤ j ≤ y2
do the following:
- Ai,j = (1 + Ai,j) modulo 5
It takes she a lot of moves to do this. That's why she gives this problem to all boys in the city and promise to go for a date with the one who will solve this task with fewest number of moves.
It is your chance to walk with such a wonderful girl. Just use it!
The first line contains two space-separated integers N and M, denoting the size of the matrix. Then the ith line of the next N lines contains M space-separated integers Ai,1, Ai,2, ..., Ai,M.
In the first line, print the integer Q (0 ≤ Q ≤ 5 * N * M), denoting the number of the moves for erasing all non zero numbers from the matrix. In the i th line of the next Q lines, print 4 space-separated integers x1, y1, x2, y2, denoting the submatrix chosen by the ith move.
Note: Your solution will be judged as wrong answer if Q is larger then 5*N*M.
Constraints for the official judge data
- 111 ≤ N, M ≤ 222
- 0 <= Ai,j <= 4
Input: 2 2 4 4 0 4 Output: 5 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 1 2 2
For each test file, your score is calculated as 100 × Q / (N × M). Then the total your score is defined as the average of your score for the test files (see the next paragraph, for more details). The aim for this problem is to minimize the total your score.
We have 40 official test files. You must correctly solve all test files to receive accepted. During the contest, the scores of the last 30 test files are 0, that is, the total your score is calculated by only the first 10 tests. After the contest, all solutions will be rescored by the average of the scores of the all 40 test files, and it will be the final score.
In the official test file, N and M are choosing uniformly and randomly from [111, 222]. Each Ai,j is chosen randomly from 0 to 4 inclusive.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, JAR, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions