버스 노선
시간 제한2초메모리 제한128 MB
60분 동안 기록된 도착 시각 다중집합을 정확히 설명하는, 각각 두 번 이상 등장하는 등차수열 형태의 버스 노선을 최소 개수로 복원합니다.
문제
아침 9시에 한 버스 정류장에 도착해 9시 59분까지 머물렀다. 그동안 여러 노선의 버스가 이 정류장에 도착했고, 당신은 각 버스가 도착한 분을 기록했다.
같은 노선의 버스는 관찰 구간 안에서 첫 도착 시각을 기준으로 일정한 분 간격마다 도착한다. 관찰한 시각은 9시 정각을 0분, 9시 59분을 59분으로 나타낸 정수이다. 각 노선은 이 한 시간 동안 적어도 두 번 정류장에 도착한다.
서로 다른 노선이라도 첫 도착 시각이나 도착 간격이 같을 수 있다. 같은 시각에 여러 노선의 버스가 도착하면 그 시각은 도착한 버스 수만큼 중복해서 기록된다. 첫 도착 시각과 간격이 완전히 같은 두 노선이 있어도 두 노선의 도착 기록은 서로 따로 세어야 한다.
기록된 도착 시각의 멀티셋이 주어질 때, 이 기록을 만들 수 있는 버스 노선들의 시간표를 찾아 출력하라. 가능한 경우가 여러 가지라면 버스 노선 수가 가장 적은 경우를 찾아야 한다. 최적해에 필요한 버스 노선 수는 25를 넘지 않는다.
입력
첫째 줄에 버스가 정류장에 도착한 횟수 n이 주어진다. (2 <= n <= 300)
다음에는 버스가 도착한 시각 n개가 주어진다. 각 시각은 0 이상 59 이하의 정수이며, 9시 정각부터 지난 분을 뜻한다. 시각들은 공백 또는 줄바꿈으로 구분된다.
출력
첫째 줄에 필요한 버스 노선의 최소 개수 X를 출력한다.
다음 X개의 줄에는 각 노선의 첫 도착 시각과 도착 간격을 공백으로 구분해 출력한다. 최적해가 여러 개라면 그중 아무거나 출력해도 되며, 노선의 출력 순서는 상관없다.
힌트
아래는 세 노선의 시간표를 도착 시각으로 나타낸 예시이다.
0 13 ← 0 . . 13 . . 26 . . . 39 . . 52 . (5회)
3 12 ← . 3 . . 15 . . 27 . . 39 . 51 . . (5회)
5 8 ← . . 5 13 . 21 . . 29 37 . 45 . . 53 (7회)