2연산

면접 대비

시간 제한2초메모리 제한512 MB

요약

X = Y = 1에서 시작해 한 변수를 다른 변수에 더하는 연산을 반복할 때, N이 나타나게 하는 가장 짧고 사전순으로 가장 앞선 연산 문자열을 구한다.

문제

두 변수 $X$ 와 $Y$ 에는 처음에 모두 1이 저장되어 있다.

사용할 수 있는 연산은 다음 두 가지다.

$N$ 이 주어질 때, 두 연산을 사용해서 두 변수 중 하나에 $N$ 을 저장하는 방법을 구하는 프로그램을 작성하시오. 가능한 방법이 여러 가지면 연산의 개수가 가장 적은 것을 출력하고, 그런 방법도 여러 가지면 사전 순으로 가장 앞서는 것을 출력한다.

첫째 줄에 $N$ ( $1 \le N \le 1\,000\,000$ )이 주어진다.

첫째 줄에 사용한 연산을 순서대로 이어 붙인 문자열을 출력한다. 연산 X는 X, 연산 Y는 Y로 나타낸다. $N = 1$ 이면 연산을 하나도 쓰지 않으므로 빈 줄을 출력한다.