원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
가로등
원제: 가로등
문제
수직선 도로 위에 개의 가로등이 켜져 있다. 각 가로등의 위치는 왼쪽부터 차례대로 로 나타낼 수 있다.
위치 의 어두운 정도를, 그 위치로부터 가장 가까운 가로등까지의 거리로 정의하자. 이는 개의 수 중에서 가장 작은 값과 같다. 여기서, 는 절댓값 기호로, 이면 , 이면 이다.
예를 들어, 개의 가로등이 차례대로 , , 에 위치한다면, 부터 까지 각 정수 위치의 어두운 정도는 다음과 같다.
| 위치 | |||||||||||
| 어두운 정도 | |||||||||||
| 가로등이 있는가? | O | O | O |
부터 까지 개의 정수 위치의 어두운 정도를 모두 계산했을 때, 가장 작은 값부터 번째로 작은 값까지 차례대로 출력하는 프로그램을 작성하라.
제약 조건
- 주어지는 모든 수는 정수이다.
부분문제
- (10점)
- (20점) ,
- (15점) . 은 을 나눈다.
- (20점)
- (35점) 추가 제약 조건 없음.
입력 형식
첫 줄에 세 정수 , , 가 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄부터 개의 줄에 걸쳐 답을 출력한다. 이 중 번째 줄에는 번째로 작은 어두운 정도의 값을 출력한다.
예제
예제 1
10 3 4 1 4 8
0 0 0 1
예제 2
4 5 5 0 1 2 3 4
0 0 0 0 0
예제 3
7 1 4 3
0 1 1 2
예제 4
9 4 10 0 3 6 9
0 0 0 0 1 1 1 1 1 1