Milk Exchange
골드 V의견: 0
Farmer John's \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) cows are lined up in a circle
such that for each \(i\) in \(1,2,\dots,N-1\), the cow to the right of cow \(i\) is
cow \(i+1\), and the cow to the right of cow \(N\) is cow \(1\). 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, the cows exchange milk according to a string \(s_1s_2\dots s_N\)
consisting solely of the characters \(\text{‘L’}\) and \(\text{‘R’}\). if
the \(i\)th cow has at least \(1\) liter of milk, she will pass \(1\) liter of milk to
the cow to her left if \(s_i=\text{‘L’}\), or to the right if
\(s_i=\text{‘R’}\). All exchanges happen simultaneously (i.e., if a cow has a
full bucket but gives away a liter of milk but also receives a liter, her milk
is preserved). If a cow's total milk ever ends up exceeding \(a_i\), then the
excess milk will be lost.
FJ wants to know: after \(M\) minutes \((1 \leq M \leq 10^9\)), what is the total
amount of milk left among all cows?
Problem credits: Chongtian Ma, Alex Liang
SCORING
- Inputs 4-8: \(N,M \le 1000\)
- Inputs 9-16: No additional constraints.
Problem credits: Chongtian Ma, Alex Liang
The first line contains \(N\) and \(M\).
The second line contains a string \(s_1s_2\dots s_N\) consisting solely of the
characters \(\text{‘L’}\) or \(\text{‘R’}\), denoting the direction each cow
will pass their milk in.
The third line contains integers \(a_1, a_2, \dots, a_N\), the capacities of each
bucket.
Output an integer, the sum of milk among all cows after \(M\) minutes.
Note that the large size of integers involved in this problem may require the
use of 64-bit integer data types (e.g., a "long long" in C/C++).
3 1
RRL
1 1 12Cows \(2\) and \(3\) pass each other one liter of milk, so their milk is preserved.
When cow \(1\) passes their milk to cow \(2\), cow \(2\)'s bucket overflows, and one
liter of milk is lost after one minute.
5 20
LLLLL
3 3 2 3 314Each cow is passing a liter of milk to the cow on the left and gaining a liter
of milk from the cow on the right, so all of the milk is preserved regardless of
how much time passes.
9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 438Initially, there are a total of 51 liters of milk. After 5 minutes, cows \(3\), \(6\), and \(7\) will lose 5, 3, and 5 liters of milk respectively. Therefore, a total of 38 liters of milk remain.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Bronze
평가 및 의견
Milk Exchange
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Milk Exchange