레이팅 미적용농부 존의 소 \(N\)마리 \((1 \leq N \leq 2 \cdot 10^5)\)가 원형으로 서 있다. \(1,2,\dots,N-1\)의 각 \(i\)에 대해 소 \(i\)의 오른쪽에는 소 \(i+1\)이 있고, 소 \(N\)의 오른쪽에는 소 \(1\)이 있다. \(i\)번째 소는 정수 용량 \(a_i\) \((1 \leq a_i \leq 10^9)\)리터의 양동이를 가지고 있다. 처음에 모든 양동이는 가득 차 있다.
매 분마다 소들은 \(\text{'L'}\)과 \(\text{'R'}\) 문자로만 이루어진 문자열 \(s_1s_2\dots s_N\)에 따라 우유를 교환한다. \(i\)번째 소는 우유가 \(1\)리터 이상 있으면, \(s_i=\text{'L'}\)이면 왼쪽 소에게, \(s_i=\text{'R'}\)이면 오른쪽 소에게 우유 \(1\)리터를 건넨다. 모든 교환은 동시에 일어난다 (즉, 양동이가 가득 찬 소가 우유 1리터를 주면서 동시에 1리터를 받으면 그 소의 우유는 그대로 유지된다). 어떤 소의 총 우유가 \(a_i\)를 초과하게 되면 초과분은 사라진다.
농부 존이 알고 싶은 것은 다음과 같다. \(M\)분 \((1 \leq M \leq 10^9\))이 지난 후, 모든 소에게 남아 있는 우유의 총량은 얼마인가?
출제: Chongtian Ma, Alex Liang
배점
- 입력 4-8: \(N,M \le 1000\)
- 입력 9-16: 추가 제약 없음.
출제: Chongtian Ma, Alex Liang
첫째 줄에 \(N\)과 \(M\)이 주어진다.
둘째 줄에 각 소가 우유를 건네는 방향을 나타내는, \(\text{'L'}\) 또는 \(\text{'R'}\) 문자로만 이루어진 문자열 \(s_1s_2\dots s_N\)이 주어진다.
셋째 줄에 각 양동이의 용량인 정수 \(a_1, a_2, \dots, a_N\)이 주어진다.
\(M\)분 후 모든 소에게 남아 있는 우유의 합을 정수로 출력한다.
이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의하라.
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