| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 320 | 155 | 137 | 53.101% |
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.
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 4
RRLRLL
There 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 4
RRRLLRRLLL
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.