루미 알고리즘

#1099골드가로등가로등

KOI 2024 2차코딩초등부 2번, 중등부 1번, 고등부 1번출제 오주원이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

가로등

원제: 가로등

문제

수직선 도로 위에 NN 개의 가로등이 켜져 있다. 각 가로등의 위치는 왼쪽부터 차례대로 A1<⋯<ANA_1 < \cdots < A_N로 나타낼 수 있다.

위치 xx의 어두운 정도를, 그 위치로부터 가장 가까운 가로등까지의 거리로 정의하자. 이는 NN 개의 수 ∣A1−x∣,⋯ ,∣AN−x∣|A_1 - x|, \cdots, |A_N - x| 중에서 가장 작은 값과 같다. 여기서, ∣⋅∣|\cdot|는 절댓값 기호로, y≥0y \ge 0이면 ∣y∣:=y|y| := y, y<0y < 0이면 ∣y∣:=−y|y| := -y이다.

예를 들어, N=3N = 3 개의 가로등이 차례대로 A1=1A_1 = 1, A2=4A_2 = 4, A3=8A_3 = 8에 위치한다면, 00부터 1010까지 각 정수 위치의 어두운 정도는 다음과 같다.

위치001122334455667788991010
어두운 정도1100111100112211001122
가로등이 있는가?OOO

x=0x = 0부터 x=Lx = L까지 L+1L + 1 개의 정수 위치의 어두운 정도를 모두 계산했을 때, 가장 작은 값부터 KK 번째로 작은 값까지 차례대로 출력하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤L≤1 000 000 000 000 000 0001 \le L \le 1\,000\,000\,000\,000\,000\,000
  • 1≤N≤300 0001 \le N \le 300\,000
  • 1≤K≤500 0001 \le K \le 500\,000
  • K≤L+1K \le L + 1
  • 0≤A1<A2<⋯<AN≤L0 \le A_1 < A_2 < \cdots < A_N \le L

부분문제

  1. (10점) N=1N = 1
  2. (20점) N≤2 500N \le 2\,500, L≤2 500L \le 2\,500
  3. (15점) 2≤N2 \le N. N−1N - 1은 LL을 나눈다. Ai=LN−1×(i−1)A_i = \frac{L}{N-1} \times (i - 1)
  4. (20점) L≤5 000 000L \le 5\,000\,000
  5. (35점) 추가 제약 조건 없음.

입력 형식

첫 줄에 세 정수 LL, NN, KK가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 NN 개의 정수 A1,⋯ ,ANA_1, \cdots, A_N이 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄부터 KK 개의 줄에 걸쳐 답을 출력한다. 이 중 ii 번째 줄에는 ii 번째로 작은 어두운 정도의 값을 출력한다.

예제

예제 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

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.