Joe is a skilled programmer. The management of the highway police division wants to
control the traffic on the highway, and hired him to solve the following problem. There are some
fixed control points on the highway. The highway police division wants to place specialized
devices to record information from all the control points. Such a device is very expensive and
unfortunately can cover an interval of only one meter (including the left endpoint and excluding
the right endpoint). The management wants to place the minimum number of devices to cover all
the control points. Joe must find an efficient solution.
The program input is from a text file. Each data set in the file stands for a particular
configuration of control points. A data set starts with the number n (n <= 100000) – the number of
control points, followed by the real values in ascending order describing the coordinates of the
control points (the highway is considered a real line). The coordinates are expressed in meters.
White spaces can occur freely in the input. The input data terminate with an end of file.
For each set of data the program has to print the minimum number of devices needed to
cover all the control points to the standard output.
An input/output sample is in the table bellow. There are two data sets. In the first case,
there are 2 points: 3.56 and 4. Only one device is needed.
2 3.56 4 3 1 2 2.9
1 2
Migrated from old NTUJ.
SEERC 2010
| No. | Testdata Range | Score |
|---|