[Solution] Spiraling Into Control Solution Round 2 2022 - Code Jam 2022

[Solution] Spiraling Into Control Solution Round 2 2022 - Code Jam 2022

Problem

As punishment for being naughty, Dante has been trapped in a strange house with many rooms. The house is an N×N$\mathbf{N}\times \mathbf{N}$ grid of rooms, with N$N$ odd and greater than 1$1$. The upper left room is numbered 1$1$, and then the other rooms are numbered 2$2$, 3$3$, ..., N2${\mathbf{N}}^2$, in a clockwise spiral pattern. That is, the numbering proceeds along the top row of the grid and then makes a 90 degree turn to the right whenever a grid boundary or an already numbered room is encountered, and finishes in the central room of the grid. Because N$N$ is odd, there is always a room in the exact center of the house, and it is always numbered N2${\mathbf{N}}^2$.

Solution Click Below:-  CLICK HERE

For example, here are the room numberings for houses with N=3$\mathbf{N}=3$ and N=5$\mathbf{N}=5$:

Dante starts off in room 1$1$ and is trying to reach the central room (room N2${\mathbf{N}}^2$). Throughout his journey, he can only make moves from his current room to higher-numbered, adjacent rooms. (Two rooms must share an edge — not just a corner — to be adjacent.)

Spiraling Into Control Solution Round 2 2022

Pixelated Solution Circle Round 2 2022 

Saving the Jelly Solution Round 2 2022

I, O Bot Solution Round 2 2022 

Dante knows that he could walk from room to room in consecutive numerical order — i.e., if he is currently in room x$x$, he would move to room x+1$x+1$, and so on. This would take him exactly N2−1${\mathbf{N}}^2-1$ moves. But Dante wants to do things his way! Specifically, he wants to reach the central room in exactly K$K$ moves, for some K$K$ strictly less than N2−1${\mathbf{N}}^2-1$.

Dante can accomplish this by taking one or more shortcuts. A shortcut is a move between rooms that are not consecutively numbered.

For example, in the 5×5$5\times 5$ house above,

• If Dante is at 1$1$, he cannot move to 17$17$, but he can move to 2$2$ or to 16$16$. The move to 2$2$ is not a shortcut, since 1+1=2$1+1=2$. The move to 16$16$ is a shortcut, since 1+1≠16$1+1\ne 16$.
• From 2$2$, it is possible to move to 3$3$ (not a shortcut) or to 17$17$ (a shortcut), but not to 1$1$, 16$16$, or 18$18$.
• From 24$24$, Dante can only move to 25$25$ (not a shortcut).
• It is not possible to move out of room 25$25$.

As a specific example using the 5×5$5\times 5$ house above, suppose that K$K$ = 4$4$. One option is for Dante to move from 1$1$ to 2$2$, then move from 2$2$ to 17$17$ (which is a shortcut), then move from 17$17$ to 18$18$, then move from 18$18$ to 25$25$ (which is another shortcut). This is illustrated below (the red arrows represent shortcuts):

Can you help Dante find a sequence of exactly K$K$ moves that gets him to the central room, or tell him that it is impossible?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow. Each test case consists of one line with two integers N$N$ and K$K$, where N$N$ is the dimension of the house (i.e. the number of rows of rooms, which is the same as the number of columns of rooms), and K$K$ is the exact number of moves that Dante wants to make while traveling from room 1$1$ to room N2${\mathbf{N}}^2$.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1).

If no valid sequence of exactly K$K$ moves will get Dante to the central room, y$y$ must be IMPOSSIBLE.

Otherwise, y$y$ must be an integer: the number of times that Dante takes a shortcut, as described above. (Notice that because Dante wants to finish in strictly less than N2−1${\mathbf{N}}^2-1$ moves, he must always use at least one shortcut.) Then, output y$y$ more lines of two integers each. The i$i$-th of these lines represents the i$i$-th time in Dante's journey that he takes a shortcut, i.e., he moves from some room ai$a_i$ to another room bi$b_i$ such that ai+1<bi$a_i+1<b_i$.

Notice that because these lines follow the order of the journey, ai<ai+1$a_i<a_{i+1}$ for all 1≤i<y$1\le i<y$.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤K<N2−1$1\le \mathbf{K}<{\mathbf{N}}^2-1$.
Nmod2≡1$\mathbf{N}\mathrm{mod}2\equiv 1$. (N$N$ is odd.)

Test Set 1 (Visible Verdict)

Time limit: 5 seconds.
3≤N≤9$3\le \mathbf{N}\le 9$.

Test Set 2 (Visible Verdict)

Time limit: 20 seconds.
3≤N≤39$3\le \mathbf{N}\le 39$.

Test Set 3 (Hidden Verdict)

Time limit: 20 seconds.
3≤N≤9999$3\le \mathbf{N}\le 9999$.