Solution for Problem: C - Fair and Square - Google Code Jam Qualification Round 2013

FairAndSquare.py

import sys

values = [1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001, 1234321, 4008004, 100020001, 102030201,
          104060401, 121242121, 123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201, 12102420121,
          12345654321, 40000800004, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201,
          1024348434201, 1210024200121, 1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004,
          4004009004004, 100000020000001, 100220141022001, 102012040210201, 102234363432201, 121000242000121,
          121242363242121, 123212464212321, 123456787654321, 400000080000004, 10000000200000001, 10002000300020001,
          10004000600040001, 10020210401202001, 10022212521222001, 10024214841242001, 10201020402010201,
          10203040504030201, 10205060806050201, 10221432623412201, 10223454745432201, 12100002420000121,
          12102202520220121, 12104402820440121, 12122232623222121, 12124434743442121, 12321024642012321,
          12323244744232321, 12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004,
          1000000002000000001, 1000220014100220001, 1002003004003002001, 1002223236323222001, 1020100204020010201,
          1020322416142230201, 1022123226223212201, 1022345658565432201, 1210000024200000121, 1210242036302420121,
          1212203226223022121, 1212445458545442121, 1232100246420012321, 1232344458544432321, 1234323468643234321]
sys.stdin = open("i.in", "r")
#sys.stdout = open("o.ot", "w")

MAXN = pow(10, 100)

#LIB

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        midval = a[mid]
        if midval < x:
            lo = mid + 1
        elif midval > x:
            hi = mid
        else:
            return mid
    return mid

#END LIB

T = int(input())

for _ in range(1, T + 1, 1):
    N, M = map(int, input().split(' '))

    low = binary_search(values, N, 0, len(values))
    high = binary_search(values, M, 0, len(values))

    if values[low] < N:
        low += 1
    if values[high] > M:
        high -= 1

    #print("%d %d\n%d %d" % (low, values[low], high, values[high]))

    ans = 0

    if low != high:
        ans = high - low + 1
    else:
        if values[low] >= N and values[high] <= M:
            ans = 1

    print("Case #%d: %d" % (_, ans))