Informatica Online Judge

  Memory [0390 / 0186]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 30   Total Tried : 347


The Champion of this Problem (C++) : gs15120 - 14ms / 2035byte
My Best Submission (C++) : N/A

[]

Background

당신은 정수 두 개(X, Y)만을 저장할 수 있는 간단한 컴퓨터를 가지고 있다. 이 컴퓨터에는 버튼이 두 개 있고, 각각의 버튼을 누르면 간단한 연산을 한다.

X버튼 : X ← X + Y
Y버튼 : Y ← X + Y

즉, 각각의 버튼은 두 수를 더한 값을 X에 넣을지 Y에 넣을지를 의미한다. 버튼은 누르지 않을 수도 있고, 여러 번 누를 수도 있다. 컴퓨터가 부팅되면 X, Y에 각각 1이 초기값으로 주어진다. 예를 들어 컴퓨터를 부팅하고 “XXYYX” 버튼을 차례대로 누른 경우 아래와 같이 진행된다.

X Y 버튼 연산
1 1 [X] X ← X + Y
2 1 [X] X ← X + Y
3 1 [Y] Y ← X + Y
3 4 [Y] Y ← X + Y
3 7 [X] X ← X + Y
10 7

목표로 하는 숫자 N이 입력으로 주어진다. 초기 상태로 (1, 1)이 주어질 때, 일정한 연산을 취해서 X 값이 N이 되도록 만들고 싶다. 이 때 Y 값은 어떻게 되어도 상관이 없다. 만약 답이 여러 개 있는 경우 길이가 짧은 문자열을 구하시오. 길이가 같은 문자열이 여러 개 있으면 사전 순으로 제일 빠른 답을 출력한다. 시간제한은 2초이며, 부분점수는 없다.

Input

첫 번째 줄에는 우리가 만들어야 하는 목표 숫자 N이 주어진다. 숫자의 범위는 1 이상 1,000,000 이하이다.

Output

입력으로 들어온 숫자를 만들기 위해 필요한 연산 횟수를 첫 줄에 출력한다. 두 번째 줄에는 어떤 연산을 할 지에 대해서 차례대로 출력한다.

IO Example

예시1)
입력
10

출력
5
XXYYX

예시2)
입력
20

출력
7
XYYYYXX

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]