게임

시간 제한1.5초메모리 제한256 MB

요약

두 장의 종이에 모두 1이 적혀 있을 때, 합을 한 장에 덮어쓰는 연산을 최소 횟수로 반복해 한 종이에 x를 만드는 색 순서를 구합니다.

문제

철수는 혼자서 자연수 게임을 하고 있다. 게임을 하려면 파란 종이 한 장과 빨간 종이 한 장이 필요하다. 처음에 두 종이에는 모두 1이 적혀 있다.

게임은 두 종이에 적힌 수의 합을 구하고, 그 값을 두 종이 중 하나에 다시 적는 방식으로 진행된다. 이 과정 한 번을 "덧셈"이라고 부른다. 덧셈을 반복하다가 두 종이 중 하나에 철수가 원하는 수 x가 적히면 게임이 끝난다.

1보다 큰 정수 x에 대해 같은 색의 종이만 계속 고르면, 항상 x-1번의 덧셈 후에 게임이 끝난다. 철수는 x를 만드는 덧셈의 최소 횟수가 궁금해졌다. x가 주어졌을 때, 게임이 끝나는 덧셈의 최소 횟수를 구하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 x가 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 x를 만드는 방법 중 덧셈 횟수가 최소인 것을 한 줄에 하나씩 출력한다.

x를 만드는 최소 덧셈 횟수가 M번이면 길이가 M인 문자열을 출력한다. 파란 종이를 고른 경우는 B, 빨간 종이를 고른 경우는 R로 적는다. 최소 횟수를 만드는 방법이 여러 가지라면 아무거나 출력한다.

x = 5인 경우 여러 방법으로 5를 만들 수 있다. B는 파란 종이, R은 빨간 종이를 뜻하고, 문자 뒤의 수는 그 종이에 적힌 수이다.

(B1, R1) → B를 선택 → (B2, R1) → R을 선택 → (B2, R3) → B를 선택 → (B5, R3) → 종료 (덧셈 3번)
(B1, R1) → B를 선택 → (B2, R1) → B를 선택 → (B3, R1) → B를 선택 → (B4, R1) → B를 선택 → (B5, R1) → 종료 (덧셈 4번)