운동 계획 세우기
시간 제한1초메모리 제한1024 MB
완료 방법의 수가 정확히 N이 되도록 A와 B로 이루어진 운동 순서를 찾고, 가능한 답 중 사전순으로 가장 앞선 것을 출력하며 불가능하면 IMPOSSIBLE을 출력한다.
문제
Juan은 운동을 시작하기로 했고 운동 세션을 준비하려 한다.
그는 어떤 날에는 운동 세션의 모든 운동을 하고 싶지 않을 수도 있다는 것을 알고 있다. 그래서 세션 전체를 건너뛰고 아무 운동도 하지 않는 상황을 피하면서, 동시에 일부 운동을 선택적으로 건너뛸 수 있도록 몇 가지 규칙을 정했다.
규칙은 다음과 같다.
- 운동은 A와 B 두 종류만 있다.
- B 종류의 운동을 마치면 다음 운동으로 넘어간다. 다음 운동이 없으면 운동 세션이 끝난다.
- A 종류의 운동을 마치면 두 가지 선택지가 있다. 다음 운동으로 넘어가거나, 다음 운동을 건너뛰고 그다음 운동으로 넘어갈 수 있다.
- 운동 세션의 마지막 운동은 항상 B 종류여야 한다.
따라서 운동 세션을 완료하는 방법이 여러 가지일 수 있다. 예를 들어 운동 세션의 운동 종류가 BAAB라면 세션을 완료하는 방법은 3가지이다. 모든 운동을 하거나, 3번째 운동을 건너뛰거나, 마지막 운동을 건너뛰는 것이다.
Juan은 운동 세션을 완료하는 서로 다른 방법이 정확히 N가지가 되도록 운동 세션을 준비하려 한다. 도와줄 수 있는가?
입력
운동 세션을 완료하는 방법의 수를 나타내는 양의 정수 N이 하나 주어진다. (2 ≤ N ≤ 1015)
출력
운동 세션의 운동 종류를 나타내는, 문자 ‘A’와 ‘B’로만 이루어진 문자열을 한 줄에 출력한다. 유효한 답이 여러 개라면 사전순으로 가장 앞서는 답을 출력한다. 유효한 운동 세션이 없으면 “IMPOSSIBLE”이라는 문자열을 한 줄에 출력한다. (따옴표는 출력하지 않는다.)