Chef and Painting
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef wants to paint with you today:)
- The field of the game is a matrix that has N rows and M columns.
- The rows of the matrix are numbered from 1 to N.
- The columns of the matrix are numbered from 1 to M.
- Initially some cells are painted with black color. All other are painted with white.
- On each step Chef can choose any white cell and the direction: Left-Right or Up-Down.
- Left-Right direction means that Chef goes left from chosen cell and paint each cell on his way with red color until he reach the board or some already painted with red or black color cell. Then he do the same in right direction (goes right from the chosen cell) and then he paint chosen cell with red color.
- Up-Down direction means the same for appropriate directions
- The aim of game is to paint all white cells with red color in the minimal number of steps.
The first line of each test case contains three integers N, M, K denoting the size of matrix and the number of painted with black color cells.
Each of next K lines contains two integers i, j denoting the painted with black color cells.
In the first line print integer P - the number of steps.
Next P lines should describe steps. Each step in a single line.
The description of each step contains two integers i, j denoting the cell you choose and string "0" or "1", according to the directions you choose ("0" - Left-Right, "1" - Up-Down).
- For each test your score will be defined as number of steps.
- The total score for a submission is the sum of the scores for all test cases.
- 1 ≤ N, M ≤ 100
- 1 ≤ K ≤ min(N*M - 1, 3000)
- 1 ≤ i ≤ N
- 1 ≤ j ≤ M
- Initially we take N, M, and K with uniform random in the range under constraints
- Then in a loop from 1 to K we take uniform random row number (from 1 to N) and uniform random column number (from 1 to M) and while the cell aij is already painted we take new uniform random i and j.
- Test cases contains max tests, tests with big (close to N*M) and small K.
Input: 6 7 6 1 3 3 2 2 4 4 5 5 6 6 4 Output: 12 3 1 1 6 7 1 1 2 1 2 3 1 1 5 0 4 2 1 3 4 0 2 5 0 5 5 0 6 5 0 4 4 1 4 6 1
|Tags||berezin, challenge, oct14, randomized|
|Time Limit:||3 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, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.