## Google Code Jam '22 Round 2 Problem A - Spiraling Into Control

View as PDF

Points: 10 (partial)
Time limit: 20.0s
Memory limit: 1G

Problem types

As punishment for being naughty, Dante has been trapped in a strange house with many rooms. The house is an grid of rooms, with odd and greater than . The upper left room is numbered , and then the other rooms are numbered , 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 is odd, there is always a room in the exact center of the house, and it is always numbered .

For example, here are the room numberings for houses with and :

Dante starts off in room and is trying to reach the central room (room ). 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.)

Dante knows that he could walk from room to room in consecutive numerical order — i.e., if he is currently in room , he would move to room , and so on. This would take him exactly moves. But Dante wants to do things his way! Specifically, he wants to reach the central room in exactly moves, for some strictly less than .

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 house above,

• If Dante is at , he cannot move to , but he can move to or to . The move to is not a shortcut, since . The move to is a shortcut, since .
• From , it is possible to move to (not a shortcut) or to (a shortcut), but not to , , or .
• From , Dante can only move to (not a shortcut).
• It is not possible to move out of room .

As a specific example using the house above, suppose that . One option is for Dante to move from to , then move from to (which is a shortcut), then move from to , then move from to (which is another shortcut). This is illustrated below (the red arrows represent shortcuts):

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

#### Input Specification

The first line of the input gives the number of test cases, . test cases follow. Each test case consists of one line with two integers and , where 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 is the exact number of moves that Dante wants to make while traveling from room to room .

#### Output Specification

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

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

Otherwise, 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 moves, he must always use at least one shortcut.) Then, output more lines of two integers each. The -th of these lines represents the -th time in Dante's journey that he takes a shortcut, i.e., he moves from some room to another room such that .

Notice that because these lines follow the order of the journey, for all .

#### Limits

.

.

. ( is odd.)

Test Set 1

Time limit: 5 seconds.

.

Test Set 2

Time limit: 20 seconds.

.

Test Set 3

Time limit: 20 seconds.

.

#### Sample Input

4
5 4
5 3
5 12
3 1

#### Sample Output

Case #1: 2
2 17
18 25
Case #2: IMPOSSIBLE
Case #3: 2
11 22
22 25
Case #4: IMPOSSIBLE

Sample Case #1 is described in the problem statement. Dante's route is . Because and are moves between consecutively numbered rooms, they are not included in the output. Only the shortcuts ( and ) are included.

In Sample Case #2, there is no solution. (Recall that there is no way for Dante to move diagonally.)

In Sample Case #3, observe that appears both as the end of one shortcut and the start of the next. It would not be valid to include the line 11 22 25 in the output; each line must represent a single shortcut.

The image shows a grid of rooms numbered as described in the statement. A path with arrows is shown as described above. The arrows between and as well as and are red to show they are shortcuts.

There is another solution that uses only one shortcut: Dante can move from , then move from (a shortcut), then move from . This is also valid; there is no requirement to minimize (or maximize) the number of shortcuts taken.

In Sample Case #4, Dante cannot get to the central room (, in this case) in just one move.

#### Note

This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >20.000s regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.