Created
July 29, 2018 16:29
-
-
Save py-in-the-sky/b2f3278e09a6651ef5b2cea0f7b8e949 to your computer and use it in GitHub Desktop.
Solution to "Googol String" Code Jam problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
https://code.google.com/codejam/contest/4284486/dashboard | |
Key insight: any digit in S_googol is ultimately a reversal/switch | |
of a zero that was inserted between two strings. If we can somehow | |
count the number of switches, then we'll know whether the digit is | |
a 1 or 0. | |
Knowing the position of these middle zeros and reverse-engineering | |
the reversals from a given index to an index of one of the middle | |
zeros will allow us to count the number of switches. | |
""" | |
from bisect import bisect_left | |
def get_middle_zero_indices(): | |
k_limit = 10**18 | |
def _generate_middle_zero_indices(): | |
i = 0 | |
while i < k_limit: | |
yield i | |
i = 2*i + 1 | |
return tuple(_generate_middle_zero_indices()) | |
def get_digit(k, middle_zero_indices): | |
switches = 0 | |
while True: | |
i = bisect_left(middle_zero_indices, k) | |
if i < len(middle_zero_indices) and middle_zero_indices[i] == k: | |
return switches % 2 | |
else: | |
mzi = middle_zero_indices[i-1] | |
k = mzi - (k - mzi) # reversal around a middle zero | |
switches += 1 | |
def main(): | |
middle_zero_indices = get_middle_zero_indices() | |
T = int(raw_input()) | |
for t in xrange(1, T+1): | |
k = int(raw_input()) - 1 # convert from 1-based to 0-based index | |
print 'Case #{}: {}'.format(t, get_digit(k, middle_zero_indices)) | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment