원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
건초 더미
원제: 건초 더미
문제
수직선의 위치 에서 오른쪽 방향으로 정수 크기의 힘을 가진 화살이 발사된다. 각 정수 위치 에는 방어력 를 가진 건초 더미를 최대 하나 설치할 수 있다.
화살이 건초 더미에 부딪쳤을 때 화살의 힘이 방어력보다 작거나 같으면, 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 힘이 방어력 만큼 감소한 뒤 건초 더미를 관통해 계속 날아간다.
두 정수 , 에 대하여 의 값을 "힘이 인 화살이 위치 에서 멈추거나 위치 보다 왼쪽에서 멈추도록 하기 위해 설치해야 하는 건초 더미의 최소 개수" 라고 정의하자. 만약 어떠한 설치 방법으로도 화살을 멈추게 할 수 있는 방법이 없다면, 로 정의한다.
개의 정수 쌍 ()에 대해 각각 의 값을 구하는 프로그램을 작성하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 인 모든 에 대하여
- 인 모든 에 대하여
- 인 모든 에 대하여
부분문제
- (6점)
- (16점)
- (18점) 인 모든 에 대하여
- (32점) 인 모든 에 대하여
- (28점) , 인 모든 에 대하여 ,
- (16점) 인 모든 에 대하여
- (12점) 인 모든 에 대하여
- (22점) 추가 제약 사항 없음.
입력 형식
첫 번째 줄에는 건초 더미의 설치할 수 있는 위치의 개수 과 발사되는 화살의 횟수 가 공백을 사이에 두고 주어진다.
두 번째 줄에는 위치 ()에 놓을 수 있는 건초 더미의 방어력 이 공백을 사이에 두고 주어진다.
세 번째 줄부터 개의 줄에 걸쳐 개의 정수 쌍이 주어진다. 이 중 () 번째 줄에는 와 가 공백을 사이에 두고 주어진다.
출력 형식
개의 줄을 출력한다. 이 중 ()번째 줄에는 의 값을 출력한다.
예제
예제 1
5 6 2 5 6 1 12 1 1 5 14 2 8 3 7 4 14 5 1
1 2 -1 2 4 1
예제 2
5 5 3 6 1 1 10 1 10 2 10 3 10 4 10 5 10
-1 -1 3 3 1