A1
Time limit1sMemory limit128 MB
Given damaged points on a highway divided into length-M segments, find the offset K in [1,M] for segment starts that minimizes the number of segments containing damage, and list all optimal K values.
- Level
Medium6 of 10
- Topics
- Binary search, Greedy, Implementation
- Solved
- No attempts yet
Problem
A country maintains a main highway called A1. Several damaged points on the highway are known, and repair teams will be assigned to fixed-length segments of the highway. Because there may be more damaged points than available teams, the first segment should be chosen so that as few segments as possible contain damage.
There are N known damaged points. Each point is given as an integer distance, in meters, from the beginning of the highway. Every segment has length M meters. There are no damaged points in the first M meters of the highway.
The first segment must start at one of the integer positions from 1 through M. If the first segment starts at position K, then the L-th segment starts at position K + (L - 1) * M. A team assigned to a segment repairs all damaged points from the first meter of that segment through its last meter.
Determine the minimum number of repair teams needed to repair all damaged points on highway A1, and output every possible starting position K for the first segment that achieves this minimum.
Input
The first line contains two integers M and N separated by a space: 1 <= M, N <= 100000. Here, M is the segment length and N is the number of damaged points.
The second line contains N integers separated by spaces. These are the positions of all damaged points. Each position is greater than M and at most 2000000000. The positions are given in strictly increasing order.
Output
Print the minimum number of repair teams on the first line.
On the second line, print all possible starting positions of the first segment that achieve that minimum. Separate the numbers with spaces and print them in strictly increasing order.