1973번 - 버스 노선 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 76 | 6 | 2 | 7.143% |
문제
당신이 한 버스 정거장에 아침 9시에 도착했다. 그리고 9시부터 9시 59분까지 그 곳에 있었다. 그 동안 노선이 다른 여러 버스들이 이 정거장에 섰는데, 당신은 그 버스들이 도착하는 시각을 주의 깊게 관찰하였다.
노선이 같은 버스는 9시 정각부터 9분까지 같은 시간 간격으로 규칙성 있게 도착한다. 버스를 관찰한 시간은 0부터 59분까지이다. 각 노선을 달리는 버스는 그 동안 적어도 두 번은 정거장에 서며, 시간은 정수 시간만을 계산한다. (최소 단위는 1분)
노선이 다르더라도 어떤 버스 노선의 시간 스케줄은 최초 도착 시간이나 시간 간격 중 하나 이상이 다른 노선의 스케줄과 일치할 수 있다. 그런 이유로, 같은 시각에 노선이 다른 버스가 두 대 이상 도착하면 그 시각은 온 버스 수만큼 중복 기록한다. 즉, 만약 최초 도착 시간과 오는 간격이 완전히 같은 두 노선이 있더라도 그 노선을 다니는 버스들이 온 시각은 구분되어 따로 입력 파일에 기록된다는 뜻이다.
버스가 도착한 시간 기록을 입력 받아서 이 간격대로 있을 수 있는 서로 다른 버스 노선들을 구해 이들의 시간 스케줄을 출력하는 프로그램을 작성하라. 그리고 찾아낸 버스 노선마다 그 노선의 첫 도착 시간과 다음 간격을 출력하라. 그러한 경우가 많다면, 버스 노선의 수가 가장 적은 경우를 찾아야 한다. (버스의 수는 25를 넘지 않는다)
입력
첫째 줄에 버스가 선 횟수 n(2 ≤ n ≤ 300)이 주어진다. 다음 줄에는 버스가 온 시각 n개가 주어진다. 각각의 시각은 정수라 가정하자. 시각은 분 단위만 기록하며, 0이상 59이하의 값을 갖는다. 입력의 중간에는 공백 대신 엔터가 주어질 수도 있다.
출력
첫째 줄에 버스 노선의 최소 개수 X를 출력한다. 다음 X개의 줄에는 각 노선의 첫 도착 시각과 간격을 출력한다. 최적해가 여러 개인 경우에는 임의의 하나만 출력하면 되며, 출력 순서는 상관이 없다.
예제 입력 1
17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
예제 출력 1
3 0 13 3 12 5 8
힌트
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번)
출처
Olympiad > International Olympiad in Informatics > IOI 1994 > Day 2 5번
- 빠진 조건을 찾은 사람: codingbug
- 잘못된 조건을 찾은 사람: cscandkswon
© 2022 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호