원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
허수아비
원제: 허수아비
문제
수직선의 위치 에서 오른쪽 방향으로 힘 를 가진 화살이 발사된다. 각 정수 위치 에는 방어력 를 가진 허수아비를 최대 하나 설치할 수 있다. 화살이 허수아비에 부딪치면, 화살의 힘이 방어력보다 작거나 같을 경우 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 화살의 힘은 현재 화살의 힘에서 만큼 줄어든 채 계속 진행한다.
정수 에 대하여 의 값을 "화살이 위치 에서 멈추거나 위치 보다 왼쪽에서 멈추도록 하기 위해 필요한 허수아비의 최소 개수" 라고 정의하자. 화살을 멈추게 할 수 있는 방법이 없을 때의 값은 이다.
예를 들어서 , 이고 , , , , 이라고 하자. 모든 의 값과 설치한 허수아비의 위치는 다음과 같다.
| 의 값 | 설치한 허수아비의 위치 | |
|---|---|---|
| 불가능 | ||
| 불가능 | ||
| 혹은 중 하나 선택 가능 | ||
인 모든 에 대하여 의 값을 구하는 프로그램을 작성하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 인 모든 에 대하여
부분문제
- (4점)
- (8점)
- (8점) 인 모든 에 대하여
- (20점) 인 모든 에 대하여 또는
- (40점) 인 모든 에 대하여
- (40점) 인 모든 에 대하여
- (30점) 추가 제약 조건 없음.
입력 형식
첫 번째 줄에 정수 과 화살의 힘 가 공백을 사이에 두고 주어진다.
두 번째 줄에 개의 정수 이 공백을 사이에 두고 주어진다.
출력 형식
첫 번째 줄에 의 값을 공백을 사이에 두고 출력한다.
예제
예제 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