Graveyard
Time limit1sMemory limit128 MB
Given n equally spaced statues on a circle of length 10000 and m statues to add, find the minimum total sliding distance to reach n+m equally spaced positions with optimal rotation and assignment.
Problem
Programming contests became so popular in the year 2397 that the governor of New Earck — the largest human-inhabited planet of the galaxy — opened a special Alley of Contestant Memories (ACM) at the local graveyard. The ACM encircles a round park and holds holographic statues of famous contestants, placed equidistantly along the park perimeter. The alley must be renewed from time to time when a new group of memorials arrives.
When new memorials are added, the exact place for each newcomer may be chosen arbitrarily along the ACM, but the equidistant arrangement must be preserved by moving some of the old statues along the alley.
Statues move only along the park perimeter. Find a renewal plan that minimizes the total travel distance of all existing statues. Installing a new hologram adds no distance penalty, so choose the places for the newcomers wisely.
Input
The first line contains two integers and : is the number of holographic statues initially placed along the ACM, and is the number of statues to be added (, ). The length of the alley along the park perimeter is exactly 10,000 feet.
Output
Print, on a single line, the minimal total travel distance of all statues in feet, rounded to exactly 4 digits after the decimal point. Always print 4 fractional digits.
Notes
The statues stand equidistantly along the circular alley. After the renewal the statues must again be equidistant, and this new arrangement may start at any point of the circle; each existing statue slides along the perimeter to reach its new position.