Checker Beating Master
Limits: 2 sec., 512 MiB
This statement was translated automatically from Ukrainian.
Zenyk got bored at work, so he came up with the following problem. There is a chessboard of size \(n \times m\), an unlimited number of white checkers, and one black checker. He wants to place as many white checkers as possible so that one can place a single black checker and capture all the white checkers in one move. A move is defined as the following process:
If there is an opposing checker diagonally in front of the black checker (in any of the four directions), and the cell immediately behind it is empty, the checker can jump over the opponent’s checker. The checker that was jumped over is removed from the board and considered captured.
After jumping one checker, the checker can continue jumping (possibly in other diagonal directions) if such an opportunity exists.
You need to find the maximum number of white checkers that can be placed such that all of them can be captured by the black checker in one move. In addition, sometimes Zenyk is interested not only in the maximum number of checkers, but also in the placement of the checkers and the moves that need to be made to capture all the white checkers.
Input
The first line contains two integers \(n\) and \(m\) — the dimensions of the board.
The second line contains a string \(s\), which is equal to Yes or
No and indicates whether the placement of checkers and
moves need to be printed.
Output
In the first line, print a single integer \(c\) — the maximum number of white checkers that can be placed on the board.
If the string \(s\) is equal to
No, nothing more needs to be printed. If it is equal to
Yes, then:
In the next \(c\) lines, print two positive integers \(wx_i, wy_i\) (row number and column number, separated by a space) — the locations of the white checkers.
In the next line, print two positive integers \(bx_0, by_0\) — the initial location of the black checker.
In the next \(c\) lines, print two positive integers \(bx_i, by_i\) — the location of the black checker after each subsequent move made.
If there are multiple correct answers, you are allowed to print any of them.
Constraints
\(1 \le n \cdot m \le 10^5\),
Scoring consists of the following subtasks:
1 point for each example from the statement,
8 points: \(n \le 2\), \(s =\)
No,14 points: \(n = 3\), \(s =\)
No,25 points: \(n \cdot m \le 10^5\), \(s =\)
No,18 points: \(n, m \le 10\), \(s =\)
Yes,20 points: \(n \% 4 = m \% 4 = 1\), \(s =\)
Yes,13 points: no additional constraints.
You will receive points for a subtask only if your program passes all tests in that subtask.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 4 No | 3 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 3 Yes | 2 4 2 2 2 1 3 3 1 5 3 |
Notes
One of the possible placements of checkers and moves of the black checker in the second example:
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|