Milk Exchange
골드 II의견: 0
Farmer John's \(N\) \((1 \leq N \leq 5 \cdot 10^5)\) cows are lined up in a circle.
The \(i\)th cow has a bucket with integer capacity \(a_i\) \((1 \leq a_i \leq 10^9)\)
liters. All buckets are initially full.
Every minute, cow \(i\) will pass all the milk in their bucket to cow \(i+1\) for
\(1\le i
simultaneously (i.e., if a cow has a full bucket but gives away \(x\) liters of
milk and also receives \(x\) liters, her milk is preserved). If a cow's total milk
ever ends up exceeding \(a_i\), then the excess milk will be lost.
After each of \(1, 2, \dots, N\) minutes, how much total milk is left among all
cows?
Problem credits: Chongtian Ma, Alex Liang, Patrick Deng
SCORING
- Inputs 4-5: \(N \le 2000\)
- Inputs 6-8: \(a_i \le 2\)
- Inputs 9-13: All \(a_i\) are generated uniformly at random in the range \([1,10^9]\).
- Inputs 14-23: No additional constraints.
Problem credits: Chongtian Ma, Alex Liang, Patrick Deng
The first line contains \(N\).
The next line contains integers \(a_1,a_2,...,a_N\).
Output \(N\) lines, where the \(i\)-th line is the total milk left among all cows
after \(i\) minutes.
6
2 2 2 1 2 18
7
6
6
6
6Initially, the amount of milk in each bucket is \([2, 2, 2, 1, 2, 1]\).
- After \(1\) minute, the amount of milk in each bucket is \([1, 2, 2, 1, 1, 1]\) so the total amount of milk is \(8\).
- After \(2\) minutes, the amount of milk in each bucket is \([1, 1, 2, 1, 1, 1]\) so the total amount of milk is \(7\).
- After \(3\) minutes, the amount of milk in each bucket is \([1, 1, 1, 1, 1, 1]\) so the total amount of milk is \(6\).
- After \(4\) minutes, the amount of milk in each bucket is \([1, 1, 1, 1, 1, 1]\) so the total amount of milk is \(6\).
- After \(5\) minutes, the amount of milk in each bucket is \([1, 1, 1, 1, 1, 1]\) so the total amount of milk is \(6\).
- After \(6\) minutes, the amount of milk in each bucket is \([1, 1, 1, 1, 1, 1]\) so the total amount of milk is \(6\).
8
3 8 6 4 8 3 8 125
20
17
14
12
10
8
8After \(1\) minute, the amount of milk in each bucket is
\([1, 3, 6, 4, 4, 3, 3, 1]\) so the total amount of milk is \(25\).
10
9 9 10 10 6 8 2 1000000000 1000000000 10000000002000000053
1000000054
56
49
42
35
28
24
20
20riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Gold
평가 및 의견
Milk Exchange
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Milk Exchange