## IPSC 2009

## Solution to Problem B – Bouncing balls

Simulation of bouncing balls might be slightly problematic, in both implementation and computational aspects.
Fortunately, there are several interesting restrictions given in the input specification, especially the fact that all
balls have the same speed and they move only diagonally.

In fact, thanks to this setting we can simply ignore collisions of the balls with each other. Visually, we would
get exactly the same view if we allowed the balls to pass through each other.

Hence we only have to handle the collisions between each ball and the walls. To do this, it is enough to note
that the x coordinate of each ball is periodic with a period 2X, and the y coordinate is periodic with a period
2Y .

Thus we can simply process the balls one by one, for each of them we compute its final position in O(1), and
then we just sort and output these.