RiseOJ – 무 경로

설명

농부 뇌즈가 베시를 아무것도 없는 허허벌판에 떨어뜨렸다! 시각 $$t=0$$ 에 베시는 무한한 수직선 위의 $$x=0$$ 에 있다. 그녀는 매초 왼쪽 또는 오른쪽으로 $$1$$ 단위씩 움직이며 필사적으로 출구를 찾는다. 그러나 사실 출구는 없으며, $$T$$ 초 후 베시는 지치고 체념한 채 $$x=0$$ 으로 돌아온다.

농부 뇌즈는 베시를 추적하려 하지만, 베시가 $x=.5, 1.5, 2.5, \ldots, (N-1).5$ 를 각각 몇 번 지나갔는지만 알고 있으며, 이는 배열 $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$ )로 주어진다. 베시는 결코 $$x>N$$ 이나 $$x<0$$ 에 도달하지 않는다.

구체적으로, 베시의 경로는 $T = \sum_{i=0}^{N-1} A_i$ 개의 $$L$$ 과 $$R$$ 로 이루어진 문자열로 나타낼 수 있으며, $$i$$ 번째 문자는 $$i$$ 번째 초 동안 베시가 움직이는 방향을 나타낸다. 방향 전환 횟수는 $$LR$$ 의 출현 횟수와 $$RL$$ 의 출현 횟수의 합으로 정의된다.

$$A$$ 와 일치하면서 방향 전환 횟수를 최소화하는, 베시가 지났을 수 있는 경로를 아무거나 하나 찾도록 농부 뇌즈를 도와주자. 유효한 경로가 적어도 하나 존재함이 보장된다.

Problem credits: Brandon Wang and Claire Zhang

제약

채점 방식

입력 3-5: $N\le 2$
입력 3-10: $T = A_0 + A_1 + \cdots + A_{N-1} \leq 5000$
입력 11-20: 추가 제약이 없다.

Problem credits: Brandon Wang and Claire Zhang

입력 형식

첫째 줄에 $$N$$ 이 주어진다. 둘째 줄에 $A_0,A_1,\dots,A_{N-1}$ 이 주어진다.

출력 형식

길이 $T = \sum_{i=0}^{N-1} A_i$ 의 문자열 $$S$$ 를 출력한다. $$S_i$$ 는 $$L$$ 또는 $$R$$ 이며, $$i$$ 번째 초 동안 베시가 이동하는 방향을 나타낸다. 방향 전환 횟수를 최소화하는 경로가 여러 개라면 아무거나 출력한다.

예제 1

입력

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.

예제 2

입력

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.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > January > Silver

올림피아드 > USACO > 2022-2023 > January > Silver

태그

JudgeUSACO

무 경로

평가 및 의견

풀이 제출