DMOPC '22 Contest 5 P4 - Ricochet

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

You are playing a game within an (N+1) by (M+1) grid enclosed by walls, where rows are numbered 0 to N from top to bottom and columns are numbered 0 to M from left to right. Let (i,j) denote the position of the cell in row i and column j.

At the start of the game, a circular bullet with diameter equal to the size of each cell is inscribed in cell (D,0) next to the left wall of the grid. The bullet is then shot from cell (D,0) and initially travels upwards and to the right with a constant speed that can be represented as a pair (X,Y), the number of seconds it takes to move 1 cell in the x and y direction, respectively.

Bullets ricochet off walls with the following rules:

  • If the bullet hits the top or bottom wall, it ricochets and travels in the reverse y direction. The x direction is unchanged.
  • If the bullet hits the left or right wall, it ricochets and travels in the reverse x direction. The y direction is unchanged.
  • If the bullet hits two walls at a corner of the grid, both directions will reverse.
  • If the bullet hits the same spot on a wall twice, it breaks the wall and exits the grid.

The game ends when the bullet has either returned back to its starting position or exited the grid by breaking a wall. Determine the length of the game, in seconds. Answer T test cases to ensure the integrity of your solution.


1 \le T \le 10^5

1 \le N,M \le 10^6

1 \le D \le N

1 \le X, Y \le 10^3

Subtask 1 [30%]

1 \le T \le 10^2

1 \le N,M \le 10^2

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains T, the number of test cases to solve.

The next T lines contain 5 space-separated integers N, M, D, X, and Y.

Output Specification

For each test case, output the number of seconds the game lasts.

Sample Input

3 6 1 1 2

Sample Output


Explanation for Sample

The bullet follows this path around the grid:


There are no comments at the moment.