# Googol String

Given the initial string and iteration rules. You are asked to given the value of a specific position in where .

The iteration rule is . Here the reverse function reverse the order of string in and switch function change "0" to "1" and "1" to "0".

Although the value of is large, but there is no need to calculate such a big number. It is easy to find the prefix of any won't change from previous string once it is fixed. The largest case you are asked to give th character in the string, so we only need to find an that is longer than the query position. To get the character, we calculate it recursively. We can also notes that the length of is where is the length of . Also we have always holds.

This solution has time complexity, so it is feasible even for large case.

import java.io.*;
import java.util.*;

public class GoogolString {
private static boolean isone(long l, long k) {
if (k == l / 2) return false;
else if (k < l / 2) return isone(l / 2, k);
else return !isone(l / 2, l - k - 1);
}
private static void solve(long K) {
long l = 0;
while (l <= K) l = l * 2 + 1;
System.out.println(isone(l, K) ? "1" : "0");
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int t = 0; t < T; t++) {
System.out.printf("Case #%d: ", t + 1);
solve(in.nextLong() - 1);
}
}
}