Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: IOI'94 - Day 2 - Problem 2: The Buses
发信站: 哈工大紫丁香 (2002年03月29日13:26:30 星期五), 站内信件

IOI'94 - Day 2 - Problem 2: The Buses
A man arrives at a bus stop at 12:00. He remains there during 12:00-12:59. T
he bus stop is used by a number of bus routes. The man notes the times of ar
riving buses. The times when buses arrive are given.
Buses on the same route arrive at regular intervals from 12:00 to 12:59 thro
ughout the entire hour.
Times are given in whole minutes from 0 to 59.
Each bus route stops at least 2 times.
The number of bus routes in the test examples will be <=17.
Buses from different routes may arrive at the same time.
Several bus routes can have the same time of first arrival and/or time inter
val. If two bus routes have the same starting time and interval, they are di
stinct and are both to be presented.
Find the schedule with the fewest number of bus routes that must stop at the
 bus stop to satisfy the input data. For each bus route, output the starting
 time and the interval.
Input Data
The input file, INPUT.TXT, contains a number n (n<=300) telling how many arr
iving buses have been noted, followed by the arrival times in ascending orde
r. Our example:
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
Output Data
Write a table to the OUTPUT.TXT file with one line for each bus route. Each 
line in the file gives the time of arrival for the first bus and the time in
terval in minutes. The order of the bus routes does not matter. If there are
 several solutions, only one is required. Our example gives:
0 13
3 12
5 8

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]