문제
무한히 넓은 2차원 좌표평면의 원점 위에 채완이가 자동차를 타고 있다. 채완이는 아래 두 가지 조작 중 하나를 선택해서 자동차를 움직일 수 있다.
R: 자동차를 $x$ 좌표가 증가하는 방향으로 움직인다. 현재R을 $k$번 연속해서 선택했다면 $2^{k-1}$ 만큼 이동한다.U: 자동차를 $y$ 좌표가 증가하는 방향으로 움직인다. 현재U를 $k$번 연속해서 선택했다면 $2^{k-1}$ 만큼 이동한다.
채완이는 위 조작을 최대 $4\ 000$번 시행해서 $(X, Y)$ 위치에 도달하고자 한다. 채완이가 해당 좌표에 도달할 수 있는지 판별하고, 도달할 수 있다면 조작 방법을 아무거나 하나 구해보자. 모든 조작을 시행했을 때 정확히 $(X, Y)$ 위치에 자동차가 위치해 있어야만 좌표에 도달한 것으로 간주한다.
입력
첫째 줄에 $X, Y$가 공백으로 구분되어 주어진다. $(0 \le X, Y \le 10^{18}$; $(X, Y) \neq (0, 0))$
출력
채완이가 $(X, Y)$에 도달할 수 있다면 길이 $1$ 이상 $4\ 000$ 이하의 R과 U 문자로만 이루어진 문자열을 출력한다.
문자열의 문자 순서대로 자동차를 움직였을 때 자동차의 위치가 정확히 $(X, Y)$에 도달해야 하며, 가능한 정답이 여러 가지가 있다면 그중 아무거나 출력해도 된다.
도달할 수 없다면 impossible을 출력한다.
예제 입력 1
8 3
예제 출력 1
RURRURRUR
자동차의 이동은 다음과 같이 이루어진다. 제시된 출력 이외에 RRRUUR도 가능한 정답 중 하나이다.
$(0, 0)$ $\xrightarrow{R}$$(1, 0)$ $\xrightarrow{U}$$(1, 1)$ $\xrightarrow{R}$$(2, 1)$ $\xrightarrow{R}$$(4, 1)$ $\xrightarrow{U}$$(4, 2)$ $\xrightarrow{R}$$(5, 2)$ $\xrightarrow{R}$$(7, 2)$ $\xrightarrow{U}$$(7, 3)$ $\xrightarrow{R}$$(8, 3)$
$(0, 0)$ $\xrightarrow{R}$$(1, 0)$ $\xrightarrow{R}$$(3, 0)$ $\xrightarrow{R}$$(7, 0)$ $\xrightarrow{U}$$(7, 1)$ $\xrightarrow{U}$$(7, 3)$ $\xrightarrow{R}$$(8, 3)$
예제 입력 2
0 16
예제 출력 2
impossible
노트
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2024. 10. C번
- 문제를 만든 사람: bnb2011
- 문제를 검수한 사람: chogahui05, snrnsidy, utilforever