Google Code Jam - Qualification Round 2013 - C. Fair and Square - large 1 input

C-large-1.py

#!/usr/bin/python3
import re
from math import ceil, sqrt
MAY_BE_PALINDROMIC_ROOT = re.compile(r'(?:[123]|[12][012]*[12])$')
palindromes = []

def is_palindrome(S):
	#return S == S[::-1]
	l = len(S)

	if l == 1:
		return True

	p = int(l / 2)
	return S[:p] == S[-p::-1]

def may_be_palindromic_root(S):
	return MAY_BE_PALINDROMIC_ROOT.match(S) and is_palindrome(S)

def generate_palindromes(top):
	for i in range(1, top):
		if may_be_palindromic_root(str(i)):
			if is_palindrome(str(i ** 2)):
				palindromes.append(i)

def test_input():
	for x in range(1, int(input()) + 1):
		y = 0
		A, B = input().split(' ')
		A = ceil(sqrt(int(A)))
		B = int(sqrt(int(B)))

		for i in palindromes:
			if i > B:
				break
			if A <= i:
				y += 1

		print('Case #%d: %d' % (x, y))

def main():
	generate_palindromes(10 ** 7)
	test_input()

if __name__ == '__main__':
	main()