{"problem":{"name":"[USACO23JAN] Moo Route S","description":{"content":"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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9015"},"statements":[{"statement_type":"Markdown","content":"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.\n\nFarmer Nhoj tries to track Bessie but only knows how many times Bessie crosses $x=0.5,1.5,2.5, \\cdots ,(N−1).5$, given by an array $A_0,A_1, \\cdots ,A_{N−1} (1 \\le N \\le 10^5, 1 \\le A_i \\le 10^6, \\sum A_i \\le 10^6)$. Bessie never reaches $x>N$ nor $x<0$.\n\nIn particular, Bessie's route can be represented by a string of $T= \\sum\\limits_{i=0}^{N-1}A_i$\n$L$s and $R$s where the $i$-th character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of $LR$s plus the number of occurrences of $RL$s.\n\nPlease help Farmer Nhoj find any route Bessie could have taken that is consistent with A\nand minimizes the number of direction changes. It is guaranteed that there is at least one valid route. \n\n## Input\n\nThe first line contains $N$. The second line contains $A_0,A_1,\\cdots ,A_{N−1}$. \n\n## Output\n\nOutput a string $S$ of length $T=\\sum\\limits_{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. \n\n[samples]\n\n## Note\n\n### Explanation for Sample 1\n\nThere is only $1$ valid route, corresponding to the route $0 \\rightarrow 1 \\rightarrow 2 \\rightarrow 1 \\rightarrow 2 \\rightarrow 1 \\rightarrow 0$. Since this is the only possible route, it also has the minimum number of direction changes. \n\n### Explanation for Sample 2\n\nThere are $3$ possible routes:\n\nRRLRRLRLLL  \nRRRLRLLRLL  \nRRRLLRRLLL  \n\nThe first two routes have $5$ direction changes, while the last one has only $3$. Thus the last route is the only correct output.\n\n### Scoring\n\n - Inputs $3-5$: $N \\le 2$\n - Inputs $3-10$: $T=A_0+A_1+ \\cdots +A_{N−1} \\le 5000$\n - Inputs $11-20$: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9015","tags":["贪心","USACO","2023","Special Judge","构造"],"sample_group":[["2\n2 4","RRLRLL"],["3\n2 4 4","RRRLLRRLLL"]],"created_at":"2026-03-03 11:09:25"}}