2176. A Diagonal Folded in a Box

A single point moves inside an r by c box, on the cells with rows 0 to r - 1 and columns 0 to c - 1. It starts at (i, j) and moves diagonally: every tick it changes its row by di and its column by dj, where each of di and dj is 1 or -1.

The walls reflect, and each axis reflects on its own. One tick, in order:

if the row would leave the box, di flips sign first if the column would leave the box, dj flips sign first then the row changes by di and the column changes by dj

After exactly t ticks, print the row and the column, separated by a single space.

``` r = 3, c = 3, start (0,0), direction (1,1), t = 4

ticks: (1,1), (2,2), then both axes reflect, giving (1,1), (0,0) -> 0 0 ```

r = 3, c = 4, start (2,3), direction (-1,-1), t = 10^18 -> 2 1

## What most people try first

Stepping the ticks. t runs to 10^18, so that is out, and the second worked example is the one that says so.

The next instinct is to notice the whole thing repeats and look for the period of the pair. That works, but it is more than the problem needs, because the two axes do not interact at all: the rule flips di using only the row, and dj using only the column. So the row after t ticks depends on i, di, t and r, and nothing else. Solve the two axes separately and print both.

## One axis, folded

A point bouncing between 0 and m with unit steps traces a triangle wave: 0, 1, ..., m, m-1, ..., 1, 0, 1, ..., which has period 2m. The axis of a box with r rows runs from 0 to r - 1, so its m is r - 1, and likewise the column axis has m = c - 1.

Unroll the walls. With no walls the coordinate after t ticks would be u = i + di * t. Folding that back in is one modulo:

m = r - 1 f = u mod 2m, taken non-negative row = f if f <= m 2m - f otherwise

## Why the fold is the same as the reflection rule

Let g(x) be the folded value of an unrolled coordinate x. The sequence g(0), g(1), g(2), ... is 0, 1, ..., m, m-1, ..., 1, 0, 1, ... by the definition above. Walking that sequence one entry at a time changes the value by exactly +1 while climbing and -1 while descending, and it turns around exactly at 0 and at m, which is where the statement says the direction flips. So stepping the unrolled coordinate by one and folding gives the same move as applying the rule, and by induction over t the two agree for every t.

This also explains why the direction never has to be tracked: it is recoverable from where u sits in its period, and the question does not ask for it.

## The boundary that breaks a careless implementation

r and c are at least 2, so m is at least 1 and the modulus 2m is never zero. A box one cell wide would be a different problem, since a point there cannot move along that axis at all, and the constraints rule it out rather than leaving it unsettled.

t may be 0, in which case the answer is the start.

## Overflow

u = i + di * t reaches 10^18 in magnitude. That is far outside a signed 32 bit integer, whose top is 2147483647, so u and the modulus must be 64 bit. A declared test uses 10^18 ticks for exactly this reason.

Watch the sign of the remainder. In C, C++, Java and JavaScript, % keeps the sign of the left operand, so -1 % 6 is -1 and not 5. A negative direction makes u negative, so add 2m back when the remainder comes out below zero.

## Cost

O(1) time and O(1) memory, with no dependence on t, r or c.

Constraints - `2 ≤ r, c ≤ 10^9` - `0 ≤ i < r` and `0 ≤ j < c` - `di` and `dj` are each 1 or -1 - `0 ≤ t ≤ 10^18` - each axis reflects independently, and the direction flips before the move - the box is at least 2 cells each way, so neither axis is degenerate