1. # Mystery Square
  2. import codejam as gcj
  4. def bn(n):
  5. return bin(n)[2:] # Python annoyingly prepends '0b'
  7. def int_sqrt(n): # Find int(n**0.5) - works for very large numbers
  8. x, y = n, (n + 1) // 2
  9. while y < x:
  10. x, y = y, (y + n // y) // 2
  11. return x
  13. def replace_gaps(X, gaps, digits): # (?00??1?, 1011) -> (1)00(0)(1)1(1)
  14. digits = bn(digits).zfill(len(gaps))
  15. for i, j in enumerate(gaps):
  16. X[j] = digits[i]
  18. def find_square(S):
  19. if len(S) > 1:
  20. top, bottom = S[:len(S) // 2], S[len(S) // 2:]
  21. return try_find_odd(top[:], bottom[:]) or 4 * find_square(top + bottom[:-2])
  22. return 1
  24. def try_find_odd(top, bottom):
  25. if bottom[-1] == '1' or bottom[-1] == '?':
  26. bottom[-1] = '1'
  27. if bottom.count('?') >= top.count('?'):
  28. gaps = [i for i, c in enumerate(top) if c == '?']
  29. for digits in range(2**len(gaps)):
  30. replace_gaps(top, gaps, digits)
  31. r = int_sqrt(int(''.join(top) + '1' * len(bottom), 2))
  32. if all(a in (b, '?') for a, b in zip(top + bottom, bn(r**2))):
  33. return r**2
  34. else:
  35. gaps = [i for i, c in enumerate(bottom) if c == '?']
  36. for digits in range(2**len(gaps)):
  37. replace_gaps(bottom, gaps, digits)
  38. b = int(''.join(bottom), 2)
  39. for second_digit in 0, 1:
  40. r = 2 * second_digit + 1
  41. for k in range(3, len(bottom) + 1):
  42. if r**2 % 2**(k + 1) != b % 2**(k + 1):
  43. r += 2**(k - 1)
  44. r |= 2**(k - 1)
  45. if all(a in (b, '?') for a, b in zip(top + bottom, bn(r**2))):
  46. return r**2
  48. T = gcj.read_input('i')
  49. for _case in range(1, T + 1):
  50. S = gcj.read_input('s{}')
  51. print('Case #%d:' % _case, bn(find_square(S)))