Post Office 1
Time limit1sMemory limit1024 MB
Place P post offices among V villages on a circular road of circumference L to minimize the total distance from every village to its nearest office, and output both the cost and chosen positions.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Binary search, Divide and conquer, Sorting
- Solved
- No attempts yet
Problem
A large ring road runs in a circle, and V villages sit along it. The circumference of the ring road is an integer L. In this problem the ring road is a circle carrying the integers from 0 to L-1, and the position of each village is given by an integer coordinate on the road. Several villages may share the same position. The distance between two villages at coordinates x and y is min(|x - y|, L - |x - y|).
We want to build post offices in P of these villages. Not every village needs one. We choose some of the villages and build a post office at each chosen position. We want to minimize the sum, over all villages, of the distance from the village to its nearest post office.
Given the positions of the villages and the number of post offices to build, write a program that computes the minimum possible value of the sum of distances from each village to its nearest post office, and outputs positions at which to build the post offices so that this value is achieved.
Input
The first line gives three integers V, P, and L. (1 ≤ P ≤ V ≤ 20, 1 ≤ L ≤ 10^12)
The next line gives V integer coordinates representing the positions of the villages. The coordinates are sorted in nondecreasing order. Each coordinate lies between 0 and L-1 inclusive.
Output
On the first line, output the integer S, the minimum value of the sum of the distances from each village to its nearest post office.
On the next line, output P integers in nondecreasing order, the positions of the villages where post offices are to be built.