Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ ´
Slovak University of Technology
Pavol Jozef Safarik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2012
Andrew the Ant
ants.c, ants.cpp, Ants.java
Andrew the Ant is fascinated by the behavior of his friends. Thousands of them are marching
their paths on and on. They can build highly organized ant-hills. Sometimes, however, they act
a little bit stupidly.
Recently, Andrew watched his fellow ants marching on top of a long piece of wood. He noticed
their behavioral pattern is very simple: Each ant walks slowly forward with a constant speed of
1 cm per second. Whenever it meets another ant, both of them only touch with their antennae
and immediately turn around and walk the opposite direction. If an ant comes to the end of
the wood, it falls down and does not affect other ants anymore.
E
A
B
D
C
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
The picture above shows an example of moving ants in time 0 s. In one second, the ants E
and A meet at position 2 and change their directions. The ant A then meets B in the next 1.5
seconds. At the same time (2.5 seconds after the start), the ants C and D will meet too. All
four of them change their directions. In the next 0.5 second (time 3 s), the first ant (E) falls
down off the left end, etc.
Your task is to simulate the movement of ants. For simplicity, suppose that the ants have zero
size (although the picture could suggest something else).
Input Specification
The input consists of several scenarios. Each scenario starts with a line containing two integer
numbers L and A, separated by a space. L is the length of the wood in cms (1 ≤ L ≤ 99 999),
and A is the number of ants at the beginning of the simulation (1 ≤ A ≤ L + 1).
Then there are A lines, each containing a positive integer Xi, one space, and an uppercase letter.
The number (0 ≤ Xi ≤ L) specifies the position of the i-th ant and the letter its initial direction:
either "L" for left (towards zero) or "R" for right. No two ants will start at the same position.
Output Specification
For each scenario, you should print a single line containing the text "The last ant will fall
down in T seconds - started at P .", where T is the exact time when the last ant (or two)
reaches the end of the wood, and P is the position where that particular ant has originally
started in time 0. If two last ants fall down at the same time, print "started at P and Q",
indicating both of their positions, P < Q.
Sample Input
90000 1
0R
10 1
0L
14 5
3L
6L
13 L
8R
1R
Output for Sample Input
The last ant will fall down in 90000 seconds - started at 0.
The last ant will fall down in 0 seconds - started at 0.
The last ant will fall down in 13 seconds - started at 6 and 8.
(The last sample input scenario corresponds to the picture.)
