시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 256 MB | 108 | 47 | 28 | 40.580% |
철수는 혼자서 자연수 게임을 하고 있다. 자연수 게임을 하려면 파란 종이 한 장과 빨간 종이 한 장이 필요하다. 가장 처음에 두 종이에는 모두 1이 적혀있다.
게임은 두 종이 적힌 수의 합을 구하고, 그 값을 하나의 종이에 바꿔 적는 방식으로 진행된다. 이 과정 한 번을 "덧셈"이라고 부른다. "덧셈"을 반복해서 두 종이 중 하나에 철수가 원하는 수 x가 적히면 게임이 종료된다.
1보다 큰 정수 x에 대해서 게임을 할 때 계속 같은 색의 종이만 고른다면, 항상 x-1번의 덧셈 후에 게임이 끝난다. 철수는 x를 만드는 덧셈의 최소 횟수가 궁금해졌다. x가 주어졌을 때, 게임이 종료되는 덧셈의 최소 횟수를 구해보자.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 x가 한 줄에 하나씩 주어진다.
각각의 테스트 케이스마다 x를 만들기 위한 방법 중 덧셈 횟수가 최소인 것을 한 줄에 하나씩 출력한다.
x를 만드는 최소 덧셈 횟수가 M번인 경우에는 길이가 M인 문자열을 출력해야 하고, 파란 종이를 고른 것은 B, 빨간 종이를 고른 것은 R이다. 최소 덧셈 횟수를 만드는 방법이 여러가지인 경우에는 아무거나 출력한다.
4 2 3 4 5
B RB RRR RBR
x = 5인 경우 아래와 같이 다양한 방법으로 5를 만들 수 있다. B는 파란 종이, R은 빨간 종이를 의미하고, 알파벳의 뒤에 적힌 수는 해당 종이에 적힌 수이다.