| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 398 | 170 | 148 | 54.815% |
수직선의 위치 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)$의 값을 구하는 프로그램을 작성하라.
첫 번째 줄에 정수 $N$과 화살의 힘 $P$가 공백을 사이에 두고 주어진다.
두 번째 줄에 $N$개의 정수 $A_1 , A_2 ,\cdots, A_N$이 공백을 사이에 두고 주어진다.
첫 번째 줄에 $f(1), f(2), \cdots , f(N)$의 값을 공백을 사이에 두고 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $N ≤ 8$ |
| 2 | 8 | $N ≤ 5,円 000$ |
| 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 1
3 10 20 20 20
1 1 1
1 5 3
-1
Olympiad > 한국정보올림피아드 > KOI 2025 1차대회 > 초등부 3번