Placeholder

#5471

Moo Route 1초 32MB

문제

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


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.