Google Code Jam 2013 - Qualification Round - Problem C

problem_c.py

from bisect import bisect_left, bisect_right


def solve(numbers, a, b):
    answer = bisect_right(numbers, b) - bisect_left(numbers, a)
    return answer if answer > 0 else 0

def main():
    numbers = [1, 4, 9]
    previous = ('012', [''])
    for k in range(2, 51):
        current = []
        for palindrome in previous[1]:
            current.append('0' + palindrome + '0')
        for border in '12':
            for palindrome in previous[1]:
                n = border + palindrome + border
                n2 = int(n) ** 2
                s = str(n2)
                if s == s[::-1]:
                    numbers.append(n2)
                    current.append(n)
        previous = (current, previous[0])
    T = int(raw_input())
    for t in xrange(T):
        A, B = [int(k) for k in raw_input().split()]
        print 'Case #%d: %s' % (t + 1, solve(numbers, A, B))

if __name__ == '__main__':
    main()