문제
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, …,(N−1).5
, given by an array A0,A1,…,AN−1 (1≤N≤105, 1≤Ai≤106, ∑Ai≤106). Bessie never reaches x>N nor x<0.
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.
입력
The first line contains N. The second line contains A0,A1,…,AN-1.
출력
예제1
2
2 4
RRLRLL
예제2
3
2 4 4
RRRLLRRLLL
ex1)
There is only 1 valid route, corresponding to the route 0→1→2→1→2→1→0. Since this is the only possible route, it also has the minimum number of direction changes.
ex2)
There 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.
출처
USACO 2023 January Silver
로그인해야 코드를 작성할 수 있어요.