루미 알고리즘

#1110골드허수아비허수아비

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

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

허수아비

원제: 허수아비

문제

수직선의 위치 00에서 오른쪽 방향으로 힘 PP를 가진 화살이 발사된다. 각 정수 위치 ii (1≤i≤N)(1 \le i \le N)에는 방어력 AiA_i를 가진 허수아비를 최대 하나 설치할 수 있다. 화살이 허수아비에 부딪치면, 화살의 힘이 방어력보다 작거나 같을 경우 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 화살의 힘은 현재 화살의 힘에서 AiA_i만큼 줄어든 채 계속 진행한다.

정수 ii에 대하여 f(i)f(i)의 값을 "화살이 위치 ii에서 멈추거나 위치 ii보다 왼쪽에서 멈추도록 하기 위해 필요한 허수아비의 최소 개수" 라고 정의하자. 화살을 멈추게 할 수 있는 방법이 없을 때의 값은 −1-1이다.

예를 들어서 N=5N = 5, P=10P = 10이고 A1=3A_1 = 3, A2=6A_2 = 6, A3=1A_3 = 1, A4=1A_4 = 1, A5=10A_5 = 10이라고 하자. 모든 f(i)f(i)의 값과 설치한 허수아비의 위치는 다음과 같다.

iif(i)f(i)의 값설치한 허수아비의 위치
i=1i = 1−1-1불가능
i=2i = 2−1-1불가능
i=3i = 333[1,2,3][1, 2, 3]
i=4i = 433[1,2,3][1, 2, 3] 혹은 [1,2,4][1, 2, 4] 중 하나 선택 가능
i=5i = 511[5][5]

1≤i≤N1 \le i \le N인 모든 ii에 대하여 f(i)f(i)의 값을 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤500 0001 \le N \le 500\,000
  • 1≤P≤1091 \le P \le 10^9
  • 1≤i≤N1 \le i \le N인 모든 ii에 대하여 1≤Ai≤1091 \le A_i \le 10^9

부분문제

  1. (4점) N≤8N \le 8
  2. (8점) N≤5 000N \le 5\,000
  3. (8점) 1≤i≤N1 \le i \le N인 모든 ii에 대하여 Ai=1A_i = 1
  4. (20점) 1≤i≤N1 \le i \le N인 모든 ii에 대하여 Ai=2A_i = 2 또는 Ai=3A_i = 3
  5. (40점) 1≤i≤N1 \le i \le N인 모든 ii에 대하여 Ai≤50A_i \le 50
  6. (40점) 1≤i<N1 \le i < N인 모든 ii에 대하여 Ai≤Ai+1A_i \le A_{i+1}
  7. (30점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 정수 NN과 화살의 힘 PP가 공백을 사이에 두고 주어진다.

두 번째 줄에 NN개의 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백을 사이에 두고 주어진다.

출력 형식

첫 번째 줄에 f(1),f(2),⋯ ,f(N)f(1), f(2), \cdots, f(N)의 값을 공백을 사이에 두고 출력한다.

예제

예제 1

입력
5 10
3 6 1 1 10
출력
-1 -1 3 3 1

예제 2

입력
3 10
20 20 20
출력
1 1 1

예제 3

입력
1 5
3
출력
-1

자료

출처 표기

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