5회 문제풀이 08 / ABC 216 C - Many Balls

ABC 216 C - Many Balls

【문제 개요】

비어있는 상자가 있습니다. 타카하시군은 아래의 작업을 원하는 만큼 수행할 수 있습니다.

• 작업 A : 상자 안에 볼을 1개 추가한다
• 작업 B : 상자 안의 볼의 수를 2배로 한다. 합계 120회 이내에 상자 안의 볼의 수를 정확히 N개로 하는 방법을 구하시오.
  또한, 주어진 제약으로 반드시 조건을 만족하는 방법은 존재합니다.
  작업 이외의 방법으로 볼의 수를 변환하는 것은 불가능합니다.

힌트 : 이진법(binary) 활용
그리디(Greedy) 접근
역순으로 생각하기

【전제】

• 1 ≤ N ≤ 10¹⁸
• 입력되는 모든 수는 정수이다.

【입력 형태】

N

【출력 형태】

A, B로만 이루어진 문자열 S를 출력하라.
S의 i문자째가 A라면 타카하시군은 i번째에 사용하는 작업은 A작업임을 의미하고 B라면 B작업임을 의미한다.
S의 길이는 120 이하이여야 한다.

【예시】

입력 예 1

5

출력 예 1

AABA

볼의 수는 0 (A)⇒ 1 (A)⇒ 2 (B)⇒ 4 (A)⇒ 5로 변화합니다.
AAAAA등도 정답으로 인정됩니다.

입력 예 2

14

출력 예 2

BBABBAAAB

볼의 수는 0 (B)⇒ 0 (B)⇒ 0 (A)⇒ 1 (B)⇒ 2 (B)⇒ 4 (A)⇒ 5 (A)⇒ 6 (A)⇒ 7 (B)⇒ 14로 변화합니다.
S의 길이를 최소화 할 필요는 없습니다.

출처 : https://atcoder.jp/contests/abc216/tasks/abc216_c