University of Toronto ACM-ICPC Tryouts 2012

F: Light Cyclin’

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 x-coordinate of each light cycle is always between 1 and 10¹², while its y-coordinate is between 1 and 10⁶ (inclusive). Light cycles always stay on the grid lines, and move at a speed of 1 square per second.

A match lasts S (1 ≤ S ≤ 10¹⁰⁰) seconds. You start at coordinates (X_A, Y_A) and follow a set of N_A (1 ≤ N_A ≤ 10⁵) instructions, with your i-th instruction consisting of moving L_Ai squares in the direction given by the character D_Ai (with "U", "D", "L", and "R" representing up, down, left, and right, respectively). Similarly, your opponent starts at coordinates (X_B, Y_B) and follows a set of N_B (1 ≤ N_B ≤ 10⁵) instructions, with their ith instruction described by L_Bi and D_Bi. Of course, neither player's instructions will ever take them beyond the boundaries of the walls, and it will take each player exactly S seconds to execute their instructions. Additionally, for each player, no instruction will have an equal or opposite direction to that of their previous instruction. Finally, if a grid point is ever visited more than once throughout the course of the match, it is guaranteed that one of the path segments intersecting there is passing directly through vertically, while the other is passing directly through horizontally (as such, this cannot happen at either player's starting or ending points).

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 T (1 ≤ T ≤ 20) scenarios as described above, you're simply interested in the number of collisions that will occur throughout each match.

Input

Line 1: 1 integer, T
For each scenario:
Line 1: 1 integer, S
Next line: 3 integers, X_A, Y_A, and N_A
Next N_A lines: 1 character, D_Ai, and 1 integer, L_Ai, for i = 1..N_A
Next line: 3 integers, X_B, Y_B, and N_B
Next N_B lines: 1 character, D_Bi, and 1 integer, L_Bi, for i = 1..N_B

Output

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):

All Submissions
Best Solutions

Point Value: 20
Time Limit: 10.00s
Memory Limit: 64M
Added: Oct 02, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)