레이팅 미적용가뭄으로 농부 존의 목초지에 풀이 다 말라버렸다. 몇 시간의 절망과 고민 끝에, 농부 존은 소중한 소들에게 먹일 옥수수를 구입한다는 기발한 아이디어를 떠올린다.
농부 존의 \(N\)마리(\(1 \leq N \leq 10^5\)) 소들은 한 줄로 서 있으며, 줄에서 \(i\)번째 소의 배고픔 수치는 \(h_i\)(\(0 \leq h_i \leq 10^9\))이다. 소들은 사회적인 동물이라 함께 먹기를 고집하기 때문에, 농부 존이 소들의 배고픔 수치를 줄일 수 있는 유일한 방법은 인접한 두 소 \(i\)와 \(i+1\)을 선택해 각각에게 옥수수 한 자루씩을 먹여 각자의 배고픔 수치를 1씩 줄이는 것이다.
농부 존은 모든 소의 배고픔 수치가 같은 음이 아닌 값이 될 때까지 소들에게 먹이를 주고 싶다. 이를 달성하기 위해 필요한 옥수수 자루의 최소 개수를 구하도록 농부 존을 도와주고, 불가능하다면 \(-1\)을 출력하라.
출제자: Arpan Banerjee
배점
- 입력 2의 모든 테스트 케이스는 \(N \leq 3\)과 \(h_i\le 100\)을 만족한다.
- 입력 3-8의 모든 테스트 케이스는 \(N\le 100\)과 \(h_i\le 100\)을 만족한다.
- 입력 9-14의 모든 테스트 케이스는 \(N\le 100\)을 만족한다.
- 입력 15는 추가 제약이 없다.
또한, 입력 3-5와 9-11에서 \(N\)은 항상 짝수이고, 입력 6-8과 12-14에서 \(N\)은 항상 홀수이다.
출제자: Arpan Banerjee
각 입력은 여러 개의 독립적인 테스트 케이스로 이루어지며, 전체 입력 케이스를 해결하려면 모든 테스트 케이스를 올바르게 해결해야 한다. 첫째 줄에 해결해야 할 테스트 케이스의 수 \(T\)(\(1\le T\le 100\))가 주어진다. 이어서 \(T\)개의 테스트 케이스가 각각 두 줄로 주어진다. 각 쌍의 첫째 줄에 \(N\)이 주어지고, 둘째 줄에 \(h_1,h_2,\ldots,h_N\)이 주어진다. 모든 테스트 케이스에 대한 \(N\)의 합은 최대 \(10^5\)임이 보장된다. \(N\)의 값은 테스트 케이스마다 다를 수 있다.
각 테스트 케이스마다 한 줄씩, 총 \(T\)개의 줄을 출력한다.
이 문제에 등장하는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")을 사용해야 할 수 있음에 유의하라.
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 914
16
-1
-1
-1For the first test case, give two bags of corn to both cows \(2\) and \(3\), then
give five bags of corn to both cows \(1\) and \(2\), resulting in each cow having a
hunger level of \(3\).
For the second test case, give two bags to both cows \(1\) and \(2\), two bags to
both cows \(2\) and \(3\), two bags to both cows \(4\) and \(5\), and two bags to both
cows \(5\) and \(6\), resulting in each cow having a hunger level of \(2\).
For the remaining test cases, it is impossible to make the hunger levels of the
cows equal.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Bronze