Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
On its trip, a train has to pass a lot of points (American English: switches) and signals. The train��s track depends on the status of points and signals. The responsible operator on the signal box does not handle them separately, but tells the signal box the start and destination signal of the train��s journey. The box then determines the correct status of points and signals and brings them into the right position.
Figure 9: Schematic view of points and signals on a sample train track.
Figure 9 shows a sample scenario in which railway tracks are shown as solid lines and signals are drawn as triangles (this is also the first scenario of the sample input). Signals have a sense of direction: they are only valid for the direction in which the triangle points (e.g., signal A is valid for trains running from left to right, see also Figure 10). Points are located where railway tracks meet (e.g., at points W1, W2, etc.). Points have a front side (i.e., the side from which a train can take alternative directions) and a back side and can be in two positions, named + and -. If a train comes from the front side, it leaves the point at the + or - leg, dependent on the point��s position (see Figure 11). If the train comes from one of the the back legs, it leaves it at the front leg. Even then the point has to be put into the right state, otherwise it gets damaged!
Figure 10: Signal valid for trains running from left to right
Figure 11: Point with two possible positions
Your task is to implement an automatic signal box, i.e., write a program which finds the correct position of points and signals for a given start and destination. The signal box should follow these rules:
A journey can only start and end at a signal. Both signals have to be in the same direction!
During a journey a train must not change its direction.
The journey consists of a sequence of signal and point settings. A signal is only taken into account for the journey if it has the right direction. A point along the way is always taken into account.
If there is more than one possible track from the start signal
to the destination signal, the correct one is determined by the following scheme:
Consider a set of path selection rules. These are given as a triple (x, y, z) of point identifiers x and y, and a position z. A selection rule has the following meaning:
If there are alternative paths starting at point x and ending
at point y where x is approached from the front and y from the back, then consider
only paths in which x is in position z (z is either + or -).
If no such rule exists for a given point x, the - position must be chosen.
The sample in- and output demonstrate the application of the rules. Furthermore, you can make the following assumptions:
The track plan is acyclic.
Within a path, each element is only used once or not at all.
If for a given point x several rules (x, y, z) exist, they will agree on the position to be chosen.
4 A AC 14 S AB A XXX S A AB W1 W W1 A W2 P3 W W2 W1 P1 P2 S P1 N1 W2 S N1 P1 W11 W W11 F N1 W12 S F AC W11 S AC F XXX S P2 N2 W2 S N2 P2 W12 W W12 W11 N3 N2 S P3 N3 W1 S N3 P3 W12 2 FW W1 W11 + FW W11 W1 - S1 S2 2 S S1 S2 XXX S S2 S1 XXX 0 S1 S4 6 S S1 XXX W1 S S2 W1 XXX S S3 XXX W2 S S4 W2 XXX W W1 S1 S2 W2 W W2 S4 W1 S3 0 S1 S2 8 S S1 XXX W1 S S2 W4 XXX S S3 W1 W2 S S4 W3 W4 W W1 S1 W2 S3 W W2 W3 W1 S3 W W3 W2 W4 S4 W W4 S2 W3 S4 1 FW W1 W2 +
Scenario #1: A N3 AC W1 + W12 - W11 + Scenario #2: NOT POSSIBLE Scenario #3: S1 S4 W1 + W2 - Scenario #4: S1 S3 S2 W1 + W2 + W3 - W4 -