Revenge of the ants 1
Time limit5sMemory limit256 MB
Ants march both ways around a circular rail and reverse on head-on meeting; find the first time every ant is back at its start with its initial direction.
- Level
Medium7 of 10
- Topics
- Math, Number theory, Simulation
- Solved
- No attempts yet
Problem
A circular rail has circumference . Gyeonggeun split the rail into equal parts and numbered the points to clockwise. He then picked some of those points and placed ants that run clockwise and ants that run counterclockwise. No point holds two or more ants.
Every ant on the rail moves a distance of 1 per second. The rail is narrow enough that only one ant fits across it, so when two ants moving in opposite directions meet at a position, both reverse direction at that instant. An ant is a point with no size, so two ants meet only at the moment their positions are exactly equal.
Gyeonggeun tells all the ants apart. Find the smallest number of seconds after which every ant is back at its starting point and moving in its starting direction.
Input
The first line contains the circumference of the rail, the number of ants moving clockwise, and the number of ants moving counterclockwise, separated by spaces.
The second line contains the points that hold the clockwise ants, separated by spaces.
The third line contains the points that hold the counterclockwise ants, separated by spaces.
, , , and . Every point number is between and , and the given points are all different. The points are not necessarily listed in increasing order.
Output
Print the smallest time in seconds after which every ant is back at its starting point and moving in its starting direction. The answer is always an integer.
Hint
In the first example the two ants collide at 0.5 seconds and at 1.5 seconds, and at 2 seconds the state matches the start.