IOI '94 - Haninge, Sweden

The Buses

A man arrives at a bus stop at 12:00. He remains there during 12:00-12:59. The bus stop is used by a number of bus routes. The man notes the times of arriving buses. The times when buses arrive are given.

  • Buses on the same route arrive at regular intervals from 12:00 to 12:59 throughout the entire hour. This means, for example, that if buses from a given route arrive at 12:16 and 12:27, a bus from that route must have also arrived at 12:05. Also, more buses from that route will arrived at 12:38 and 12:49.
  • Times are given in whole minutes from 0 to 59.
  • At least two buses arrive from each bus route during the hour.
  • 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 interval. Even if two bus routes have the same starting time and interval, they are distinct 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 Format

The first line of input contains a number n telling how many arriving buses have been noted. The second line contains a space-separated list of arrival times in ascending order.

Output Format

The first line should contain an integer - the number of bus routes. This should be minimal. The following n lines should each contain a description of one bus route - two space-separated integers, the first time of arrival of a bus from the route during the hour, and the interval between successive buses from that route. The order of the bus routes does not matter. If there are several solutions, only one is required.

Sample Input

17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

Sample Output

3
0 13
3 12
5 8

All Submissions
Best Solutions


Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 8M
Added: Aug 20, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...