1550. The Snake Numbering
An R by C grid is numbered 1 to R * C by walking it like a snake: row 1
left to right, row 2 RIGHT TO LEFT, row 3 left to right again, and so on
alternating. Rows and columns are numbered from 1.
The grid itself is never given. Then q questions arrive, each of one of two
kinds:
at k print the row and column of the cell numbered k
of r c print the number of the cell at row r, column c
``` R = 3, C = 4 1 2 3 4 8 7 6 5 9 10 11 12
at 1 -> 1 1 at 5 -> 2 4 at 8 -> 2 1 of 2 1 -> 8 of 3 4 -> 12 ```
R = 1, C = 6 1 2 3 4 5 6 row 1 is never reversed
R = 2, C = 2 1 2
4 3
## What most people try first
Building the numbering. With R and C at 10^9 the grid can hold 10^18
cells, so it cannot exist and every answer has to be arithmetic.
The second reflex is to reuse the plain reading-order formulas of problem 1549 and patch the reversed rows afterwards. That works and it is easy to patch the wrong direction: the correction applies to the COLUMN within the row, not to the row number, and it applies to the rows numbered 2, 4, 6, which are the ones with an EVEN 1-based index and therefore an odd 0-based one.
## Both directions, from the same two lines
Work 0-based inside, then add one on the way out. With n = k - 1:
``` at k: i = n / C the 0-based row off = n mod C how far along that row j = off if i is even = C - 1 - off if i is odd print (i + 1, j + 1)
of r c: i = r - 1; j = c - 1 off = j if i is even = C - 1 - j if i is odd print i * C + off + 1 ```
## Why the offset is the right thing to reverse
Every row holds exactly C numbers and the rows are numbered in order, so the
first number on 0-based row i is i * C + 1 whichever way that row runs.
What the direction changes is only WHICH cell of the row gets the first of
those numbers: the leftmost on an even row, the rightmost on an odd one. So the
row index is computed exactly as in reading order, and only the position within
the row is mirrored.
## Why the two directions are genuinely inverse
Mirroring is its own inverse: applying off -> C - 1 - off twice returns
off. So the of computation undoes the at one and the tests can check each
against the other. That is worth using: the declared cases include both kinds
of question about the same cells.
## The parity that is easy to get backwards
Rows are given to the user 1-based, and the reversed ones are rows 2, 4, 6.
Working 0-based those are i = 1, 3, 5, the ODD ones. Testing r % 2 == 0 on
the 1-based number and i % 2 == 1 on the 0-based one are the same condition,
and mixing the two reverses exactly the wrong rows. A single row is never
reversed, and a grid of two very tall columns has nearly every row reversed;
both are declared.
## Overflow
R * C reaches 10^18 and so does k, far past the 2147483647 a signed 32
bit integer holds, so every variable is 64 bit. Note that i * C is the
dangerous product: i fits in 32 bits and C fits in 32 bits, and the product
does not.
## Cost
O(1) per question and O(1) memory. Problem 1549 is the same kind of index
arithmetic without the alternation.
Constraints - `1 ≤ R ≤ 10^9` - `1 ≤ C ≤ 10^9` - `R * C ≤ 10^18` - `1 ≤ q ≤ 200000` - `1 ≤ k ≤ R * C` - `1 ≤ r ≤ R` and `1 ≤ c ≤ C` - `R` and `C` are independent; the grid need not be square
Input
The first line contains three integers R, C and q.
Each of the next q lines is either at k, with k a position in the snake numbering, or of r c, with r and c 1-based.
Output
Print q lines, one per question in arrival order. An at question prints two integers separated by a single space, the 1-based row then the 1-based column. An of question prints one integer, the snake number of that cell.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.