Ada Bishop 2
All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/MARCH20/hindi/ADASHOP2.pdf), [Bengali](http://www.codechef.com/download/translated/MARCH20/bengali/ADASHOP2.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/MARCH20/mandarin/ADASHOP2.pdf), [Russian](http://www.codechef.com/download/translated/MARCH20/russian/ADASHOP2.pdf), and [Vietnamese](http://www.codechef.com/download/translated/MARCH20/vietnamese/ADASHOP2.pdf) as well. Ada is training for her match against Magnus Carlsen in the World Chess Championship 2020. Ada took a standard [chessboard](https://en.wikipedia.org/wiki/Chessboard) with $8$ rows (numbered $1$ through $8$) and $8$ columns (numbered $1$ through $8$); let's denote a cell in row $r$ and column $c$ by $(r, c)$. Then, Ada placed a [bishop](https://en.wikipedia.org/wiki/Bishop_(chess)) in a cell $(r_0, c_0)$; it is guaranteed that this cell is black. Ada's goal is to move the bishop in such a way that it visits all black cells. Remember that a bishop is a piece that moves diagonally ― formally, the bishop may move from a cell $(r_s, c_s)$ to a cell $(r_t, c_t)$ if and only if either $r_s+c_s=r_t+c_t$ or $r_s-c_s=r_t-c_t$. In such a move, the bishop visits all cells between $(r_s, c_s)$ and $(r_t, c_t)$ on this diagonal (inclusive). Help Ada find a sequence of at most $64$ moves for the bishop such that when the bishop follows this route, it visits all black cells on the chessboard. Note that each cell may be visited multiple times and it is not necessary to return to the starting point. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first and only line of each test case contains two space-separated integers $r_0$ and $c_0$. ### Output For each test case: - First, print a line containing a single integer $M$ ($M \le 64$) ― the number of moves in the bishop's route. - Then, print $M$ lines. For each $i$ ($1 \le i \le M$), the $i$-th of these lines should contain two space-separated integers $r_i$ and $c_i$, where the route followed by the bishop is $(r_0,c_0) \rightarrow (r_1,c_1) \rightarrow (r_2,c_2) \rightarrow \ldots \rightarrow (r_M,c_M)$. ### Constraints - $1 \le T \le 32$ - $1 \le r_0, c_0 \le 8$ - $(r_0, c_0)$ is a black cell, i.e. $r_0+c_0$ is even ### Subtasks **Subtask #1 (99 points):** $r_0 = c_0 = 1$ **Subtask #2 (1 points):** original constraints ### Example Input ``` 1 5 3 ``` ### Example Output ``` 31 3 5 4 6 7 3 5 1 1 5 [26 more lines follow] ``` ### Explanation **Example case 1:** The first five moves of the bishop are shown in the figure below.
|Tags||alei, constructive, march20, simple, tmwilliamlin|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.