블록 쌓기
플래티넘 II의견: 0
블록을 쌓는 놀이를 하고 있다. 블록을 위로 쌓을 수 있는 칸들이 총 \(N\)개 있으며, \(1\)번 칸부터 \(N\)번 칸까지 순서대로 붙어 있다.
현재 \(i\)번 칸에는 \(A_i\)개의 블록이 쌓여 있다. 현재 블록들이 쌓인 모양이 난잡하다고 생각해, 다음과 같은 조건들을 만족하도록 블록들을 옮기려고 한다.
- 각 칸에 쌓인 블록의 개수는 \(L\) 이상 \(R\) 이하이다.
- 각 칸에 쌓인 블록의 개수는 단조증가한다: \(1 ≤ i ≤ N - 1\)에 대해 \(i\)번 칸에 쌓인 블록의 개수는 \(i + 1\)번 칸에 쌓인 블록의 개수 이하이다.
여러분은 어떠한 칸의 블록을 인접한 칸으로 옮기는 것을 반복해 목표를 달성하려고 한다. 목표를 달성하는 것이 가능한지 판별하고, 가능한 경우 블록을 옮기는 횟수의 최솟값을 구해야 한다.
- 주어지는 수는 모두 정수이다.
- \(1 \le N \le 100\)
- \(0 \le L \le R \le 10^9\)
- \(R - L \le 100\)
- \(0 \le A_i \le 10^9\) (\(1 \le i \le N\))
첫 번째 줄에 \(N\), \(L\), \(R\)이 공백으로 구분되어 주어진다.
두 번째 줄에 \(A_1\), \(\dots\), \(A_N\)이 공백으로 구분되어 주어진다.
목표를 달성하는 것이 불가능하다면 \(-1\)을 출력한다. 목표를 달성하는 것이 가능하다면 블록을 옮기는 횟수의 최솟값을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 7점 | \(N \le 50\), \(R - L \le 1\). |
2 | 6점 | \(N \le 4\), \(R - L \le 50\). |
3 | 11점 | \(N \le 10\), \(A_1 + \cdots + A_N \le 10\). |
4 | 11점 | \(N \le 50\), \(A_1 + \cdots + A_N \le 50\). |
5 | 30점 | \(N \le 50\), \(R \le 50\). |
6 | 10점 | \(N \le 50\), \(R - L \le 50\). |
7 | 25점 | 추가 제약 조건 없음. |
5 3 5
2 0 9 1 4
7
10 3 8
2 7 9 10 2 2 2 8 3 8
25
10 6 7
10 7 5 4 4 3 9 4 9 7
20
3 2 3
1 1 1
-1
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2023 > 1차 대회 > 고등부 3번
평가 및 의견
블록 쌓기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
블록 쌓기