구골 문자열 (Small)

중간 0과 뒤집고 바꾼 꼬리를 덧붙여 재귀 0/1 문자열을 만든 뒤 각 테스트 케이스의 K번째 문자를 구합니다.

쉬움3재귀시뮬레이션면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제 설명

예제4

문제

"0/1 문자열"은 모든 문자가 0 또는 1인 문자열이다. 0/1 문자열에는 다음 두 연산을 적용할 수 있다.

switch: 모든 0을 1로, 모든 1을 0으로 바꾼다. 예를 들어 "100"은 "011"이 된다.
reverse: 문자열을 뒤집는다. 예를 들어 "100"은 "001"이 된다.

다음과 같이 정의된 0/1 문자열의 무한 수열을 생각하자.

$S_0$ = ""
$S_1$ = "0"
$S_2$ = "001"
$S_3$ = "0010011"
$S_4$ = "001001100011011"
...
$S_N$ = $S_{N-1}$ + "0" + switch(reverse( $S_{N-1}$ ))

googol은 $10^{100}$ 이다. $S_{googol}$ 의 $K$ 번째 문자를 구하라. 문자의 위치는 1번부터 센다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 다음 $T$ 개의 줄에는 각각 정수 $K$ 가 하나씩 주어진다.

출력

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 $S_{googol}$ 의 $K$ 번째 문자이다.

제한

$1 \le T \le 100$
$1 \le K \le 10^5$

Loading...