Insane Drift

시간 제한0.5초메모리 제한1024 MB

요약
같은 방향으로 연속 이동하면 길이가 2배로 늘어나는 규칙에서 목표점 (X, Y)에 도달할 수 있는지 판정하고 이동 순서를 하나 출력한다.
난이도

어려움10점 중 8점

유형
수학, 비트 연산, 그리디, 구현
정답자
아직 제출이 없습니다

문제

무한히 넓은 2차원 좌표평면의 원점 위에 채완이가 자동차를 타고 있다. 채완이는 아래 두 가지 조작 중 하나를 선택해서 자동차를 움직일 수 있다.

  • R: 자동차를 xx 좌표가 증가하는 방향으로 움직인다. 현재 R을 kk번 연속해서 선택했다면 2k−12^{k-1} 만큼 이동한다.
  • U: 자동차를 yy 좌표가 증가하는 방향으로 움직인다. 현재 U를 kk번 연속해서 선택했다면 2k−12^{k-1} 만큼 이동한다.

채완이는 위 조작을 최대 4 0004\ 000번 시행해서 (X,Y)(X, Y) 위치에 도달하고자 한다. 채완이가 해당 좌표에 도달할 수 있는지 판별하고, 도달할 수 있다면 조작 방법을 아무거나 하나 구해보자. 모든 조작을 시행했을 때 정확히 (X,Y)(X, Y) 위치에 자동차가 위치해 있어야만 좌표에 도달한 것으로 간주한다.

입력

첫째 줄에 X,YX, Y가 공백으로 구분되어 주어진다. (0≤X,Y≤1018(0 \le X, Y \le 10^{18}; (X,Y)≠(0,0))(X, Y) \neq (0, 0))

출력

채완이가 (X,Y)(X, Y)에 도달할 수 있다면 길이 11 이상 4 0004\ 000 이하의 R과 U 문자로만 이루어진 문자열을 출력한다.

문자열의 문자 순서대로 자동차를 움직였을 때 자동차의 위치가 정확히 (X,Y)(X, Y)에 도달해야 하며, 가능한 정답이 여러 가지가 있다면 그중 아무거나 출력해도 된다.

도달할 수 없다면 impossible을 출력한다.

힌트

예제2

  1. 예제 1

    입력
    8 3
    
    예상 출력
    RURRURRUR
    
  2. 예제 2

    입력
    0 16
    
    예상 출력
    impossible