Control Points#1397
Joe is a skilled programmer. The management of the highway police division wants to control the traffic on the highway, and has 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 represents a particular configuration of control points. A data set starts with the number (n \leq 100000) — the number of control points, followed by real numbers 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 must print the minimum number of devices needed to cover all the control points to the standard output.
An input/output sample is provided in the table below. There are two data sets. In the first case, there are points: and . Only one device is needed.
Example 1