University of Toronto ACM-ICPC Tryouts 2012
Having been sucked into your father's secret computer through a projector in the back of his arcade (or something), you find yourself in the wonderful world of Tron! Here, you play games all day, and if you ever lose, you die.
One such game involves you and an opponent driving around a flat grid on
light cycles, which leave behind a permanent trail of...light...wherever
they go. This grid can be modeled with the Cartesian plane, and is
enclosed by a rectangle of impenetrable walls which ensure that the
A match lasts U
, D
, L
, and R
representing up, down, left, and right,
respectively). Similarly, your opponent starts at coordinates
Whenever both light cycles reach the same grid point at the same time,
or a light cycle hits an existing trail of light (in other words, a grid
point which either light cycle had previously passed through), a
collision occurs. Because you're just playing a practice match for now,
neither player dies when this occurs, and, in fact, the collision is not
counted in favour of either you or your opponent. Instead, for
Input Specification
Line 1: 1 integer,
For each scenario:
Line 1: 1 integer,
Next line: 3 integers,
Next
Next line: 3 integers,
Next
Output Specification
For each scenario:
1 integer: The total number of collisions that will occur.
Sample Input
1
12
2 5 5
R 4
U 1
L 1
D 4
L 2
3 3 4
U 3
L 2
D 2
R 5
Sample Output
4
Explanation of Sample
The following diagram illustrates the paths of the light cycles (yours drawn in solid lines, and your opponent's drawn in dotted ones), as well as all of the collision points (indicated with large dots):
Comments