UVa 10714

From Algorithmist
Jump to navigation Jump to search

10714 - Ants[edit]


An army of ants walk on a horizontal pole of length cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediately falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.


This is one of those great problems, which are very easy, once you get an insightful idea.

All you need to notice is that the ants are indistinguishable. When two ants collide, we may simply ignore the fact that they change the directions in which they're walking!



10 3
2 6 7
214 7
11 12 7 13 176 23 191


4 8
38 207