题目背景

0x29 搜索 总结与练习

题目描述

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.
• 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 interval. 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.

输入格式

Your program is to read from standard input. The input contains a number n (n <= 300) telling how many arriving buses have been noted, followed by the arrival times in ascending order.

输出格式

Your program is to write to standard output. The output contains one integer, which is the fewest number of bus routes.

题目大意

【题目描述】

一个人在 12:00 到达一个公交车站。他在 12:00 到 12:59 期间一直待在那里。这个公交车站被多条公交线路使用。这个人记录了公交车到达的时间。给出了公交车到达的时间。

• 同一条路线的公交车在整个小时内从 12:00 到 12:59 以固定的时间间隔到达。
• 时间以整分钟给出，从 0 到 59。
• 每条公交线路至少停靠 2 次。
• 测试示例中的公交线路数量将 $\leq 17$。
• 不同路线的公交车可能同时到达。
• 几条公交线路的首次到达时间和/或时间间隔可能相同。如果两条公交线路的起始时间和间隔相同，则它们是不同的，并且都需要呈现。

找出满足输入数据的必须停靠在公交车站的公交线路数量最少的时间表。对于每条公交线路，输出起始时间和间隔。

【输入格式】

你的程序需要从标准输入中读取。输入包含一个数字 $n$（$n \leq 300$），表示已经记录的到达公交车的数量，后跟按升序排列的到达时间。

【输出格式】

你的程序需要写入标准输出。输出包含一个整数，即最少的公交线路数量。

翻译来自于：ChatGPT

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

3