Moo Route
골드 II의견: 0
Farmer Nhoj dropped Bessie in the middle of nowhere! At time \(t=0\), Bessie is
located at \(x=0\) on an infinite number line. She frantically searches for an
exit by moving left or right by \(1\) unit each second. However, there actually is
no exit and after \(T\) seconds, Bessie is back at \(x=0\), tired and resigned.
Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses
\(x=.5, 1.5, 2.5, \ldots, (N-1).5\), given by an array \(A_0,A_1,\dots,A_{N-1}\)
(\(1\leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\), \(\sum A_i\le 10^6\)). Bessie never
reaches \(x>N\) nor
\(x<0\).
In particular, Bessie's route can be represented by a string of
\(T = \sum_{i=0}^{N-1} A_i\) \(L\)s and \(R\)s where the \(i\)th character represents
the direction Bessie moves in during the \(i\)th second. The number of direction
changes is defined as the number of occurrences of \(LR\)s plus the number of
occurrences of \(RL\)s.
Please help Farmer Nhoj find any route Bessie could have taken that is
consistent with \(A\) and minimizes the number of direction changes. It is
guaranteed that there is at least one valid route.
Problem credits: Brandon Wang and Claire Zhang
SCORING
- Inputs 3-5: \(N\le 2\)
- Inputs 3-10: \(T = A_0 + A_1 + \cdots + A_{N-1} \leq 5000\)
- Inputs 11-20: No additional constraints.
Problem credits: Brandon Wang and Claire Zhang
The first line contains \(N\). The second line contains \(A_0,A_1,\dots,A_{N-1}\).
Output a string \(S\) of length \(T = \sum_{i=0}^{N-1} A_i\) where \(S_i\) is \(L\) or
\(R\), indicating the direction Bessie travels in during second \(i\). If there are
multiple routes minimizing the number of direction changes, output any.
2
2 4RRLRLLThere is only 1 valid route, corresponding to the route
\(0\to 1 \to 2 \to 1\to 2 \to 1\to 0\). Since this is the only possible route, it
also has the minimum number of direction changes.
3
2 4 4RRRLLRRLLLThere are 3 possible routes:
RRLRRLRLLL
RRRLRLLRLL
RRRLLRRLLL
The first two routes have 5 direction changes, while the last one has only 3.
Thus the last route is the only correct output.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Silver
평가 및 의견
Moo Route
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Moo Route