55 - ZOJ Monthly, September 2006 - 1003
Mr. Smith is writing a program of a movie player. His player supports subtitles and he wants to create a new format of subtitle files. The new format looks like this:
00:00:00.00 This is the first text line. 00:00:01.25 The time-tag of this line can be omitted. 00:00:03.00 A text line will not be empty. 00:00:10.00 END
Each text line has a time-tag above it. A time-tag has a form of "HH:MM:SS.CC" (HH for hours, MM for minutes, SS for seconds and CC for centiseconds). The whole file will be ended with a line of "END" (it is just for denoting the end of file, and won't be displayed).
However, Mr. Smith finds that some of the time-tags can be omitted. We choose any two of the time-tags, and then, if all the time-tags between them can be calculated in the range of error with the two time-tags, all the time-tags between them can be omitted. For instance, the second time-tag in the example above can be omitted with an error range of -5 centiseconds to +5 centiseconds. You can see that the lengths of the first text line and the second one are 28 and 41, and the first time-tag and the third one are 0 centisecond and 300 centisecond, so the second time-tag should be 0 + (300 - 0) * 28 / (28 + 41) = 121.739 averagely, rounding to the nearest integer 122. Because the second time-tag is 125 centisecond actually and 122 - 5 = 117 <= 125 <= 127 = 122 + 5, it can be omitted. And of course the first and the last time-tags cannot be omitted.
Write a program to count how many time-tags can be omitted at most.
There are several test cases. In each test case, the first line contains one integer E (0 <= E <= 100) which is the error range in centiseconds, and then the subtitle file follows. In each two of the following lines, the first line is the time-tag and the second one is the subtitle text. A text line of "END" denotes the end of the subtitle file. The number of the time-tags in a subtitle file won't exceed 1000. The length of a text line is at most 100 and at least 1. You can assume that the time-tags are in nondecreasing order. E = -1 denotes the end of input.
For each test case, output one line with the maximum number of time-tags that can be omitted in the error range of -E centiseconds to +E centiseconds.
5 00:00:00.00 The first line 00:00:01.25 The second line 00:00:02.75 The third line 00:00:04.00 The fourth line 00:00:05.00 END -1
The second and the third time-tags can be omitted by being calculated with the first and the fourth time-tags.
Author: JIAN, Hengyi