허수아비
브론즈 I의견: 0
수직선의 위치 \(0\)에서 오른쪽 방향으로 힘 \(P\)를 가진 화살이 발사된다. 각 정수 위치 \(i\) (\(1 ≤ i ≤ N\))에는 방어력 \(A_i\)를 가진 허수아비를 최대 하나 설치할 수 있다. 화살이 허수아비에 부딪치면, 화살의 힘이 방어력보다 작거나 같을 경우 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 화살의 힘은 현재 화살의 힘에서 \(A_i\)만큼 줄어든 채 계속 진행한다.
정수 \(i\)에 대하여 \(f(i)\)의 값을 "화살이 위치 \(i\)에서 멈추거나 위치 \(i\)보다 왼쪽에서 멈추도록 하기 위해 필요한 허수아비의 최소 개수" 라고 정의하자. 화살을 멈추게 할 수 있는 방법이 없을 때의 값은 \(−1\)이다.
예를 들어서 \(N = 5\), \(P = 10\)이고 \(A_1 = 3\), \(A_2 = 6\), \(A_3 = 1\), \(A_4 = 1\), \(A_5 = 10\)이라고 하자. 모든 \(f(i)\)의 값과 설치한 허수아비의 위치는 다음과 같다.
| \(i\) | \(f(i)\)의 값 | 설치한 허수아비의 위치 |
|---|---|---|
| \(i = 1\) | \(-1\) | 불가능 |
| \(i = 2\) | \(-1\) | 불가능 |
| \(i = 3\) | \(3\) | \([1, 2, 3]\) |
| \(i = 4\) | \(3\) | \([1, 2, 3]\) 혹은 \([1, 2, 4]\) 중 하나 선택 가능 |
| \(i = 5\) | \(1\) | \([5]\) |
\(1 ≤ i ≤ N\)인 모든 \(i\)에 대하여 \(f(i)\)의 값을 구하는 프로그램을 작성하라.
- 주어지는 모든 수는 정수이다.
- \(1 ≤ N ≤ 500\, 000\)
- \(1 ≤ P ≤ 10^9\)
- \(1 ≤ i ≤ N\)인 모든 \(i\)에 대하여 \(1 ≤ A_i ≤ 10^9\)
첫 번째 줄에 정수 \(N\)과 화살의 힘 \(P\)가 공백을 사이에 두고 주어진다.
두 번째 줄에 \(N\)개의 정수 \(A_1 , A_2 ,\cdots, A_N\)이 공백을 사이에 두고 주어진다.
첫 번째 줄에 \(f(1), f(2), \cdots , f(N)\)의 값을 공백을 사이에 두고 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 4점 | \(N ≤ 8\) |
2 | 8점 | \(N ≤ 5000\) |
3 | 8점 | \(1 ≤ i ≤ N\)인 모든 \(i\)에 대하여 \(A_i = 1\) |
4 | 20점 | \(1 ≤ i ≤ N\)인 모든 \(i\)에 대하여 \(A_i = 2\) 또는 \(A_i = 3\) |
5 | 40점 | \(1 ≤ i ≤ N\)인 모든 \(i\)에 대하여 \(A_i ≤ 50\) |
6 | 40점 | \(1 ≤ i < N\)인 모든 \(i\)에 대하여 \(A_i \le A_{i+1}\) |
7 | 30점 | 추가 제약 조건 없음. |
5 10
3 6 1 1 10-1 -1 3 3 13 10
20 20 201 1 11 5
3-1riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 1차 대회 > 초등부 3번
평가 및 의견
허수아비
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
허수아비