루미 알고리즘

#1134실버거리두기거리두기

KOI 2026 2차코딩초등부 1번출제 장근영이 문제가 어렵다면 — 배우는 순서 보기

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

거리두기

원제: 거리두기

문제

NN명의 학생이 수직선 위에 서려고 한다. 수직선에서는 수가 클수록 더 오른쪽에 있는 위치를 나타낸다.

학생들은 11번부터 NN번까지 번호 순서대로 왼쪽부터 오른쪽으로 서며, 학생들이 서는 위치는 모두 정수이다.

ii (1≤i≤N)(1 \le i \le N)번 학생이 서는 위치를 BiB_i라고 하자. 학생들이 서는 위치는 다음 조건을 만족해야 한다.

  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대해, ii번 학생은 위치 AiA_i보다 오른쪽에 설 수 없다. 즉, Bi≤AiB_i \le A_i여야 한다.
  • 번호가 연속한 두 학생은 KK 이상의 거리를 두어야 한다. 즉, 정수 ii (1≤i≤N−1)(1 \le i \le N - 1)에 대해 Bi+1−Bi≥KB_{i+1} - B_i \ge K여야 한다.

K=0K = 0인 경우에는 여러 학생이 같은 위치에 서도 된다.

학생들은 11번 학생의 위치 B1B_1을 가능한 한 크게 만들고 싶다.

조건을 만족하면서 학생들이 수직선 위에 서는 방법 [B1,B2,⋯ ,BN][B_1, B_2, \cdots, B_N] 중 B1B_1의 값이 가장 큰 방법을 구하라. 그러한 방법이 여러 개라면 그중 아무거나 구하라.

조건을 만족하면서 학생들이 수직선 위에 서는 방법이 적어도 하나는 존재함을 증명할 수 있다.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤1001 \le N \le 100
  • 0≤K≤100 \le K \le 10
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 1≤Ai≤1001 \le A_i \le 100

부분문제

  1. (25점) 정수 ii (1≤i≤N−1)(1 \le i \le N - 1)에 대해 Ai+1−Ai≥KA_{i+1} - A_i \ge K이다.
  2. (35점) K=0K = 0
  3. (30점) 조건을 만족하도록 학생들이 서는 방법 중 0≤B1≤1000 \le B_1 \le 100인 것이 존재한다.
  4. (10점) 추가 제약 조건 없음.

입력 형식

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

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

출력 형식

첫 줄에 NN개의 정수 B1,B2,⋯ ,BNB_1, B_2, \cdots, B_N을 공백으로 구분하여 출력한다. 이때, 학생들이 수직선 위에 서는 방법 [B1,B2,⋯ ,BN][B_1, B_2, \cdots, B_N]은 지문에서 주어진 모든 조건을 만족해야 하며, B1B_1의 값이 최대화되어야 한다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.

예제

예제 1

입력
5 2
1 4 10 9 13
출력
1 4 6 9 12

예제 2

입력
4 0
5 2 7 3
출력
2 2 3 3

예제 3

입력
4 3
2 1 5 9
출력
-2 1 5 8

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.