Google Code Jam 2015 Round 1C

A-small.py

def check(R,C,W,B):
    c = sum(b.count(1) for b in B)
    for y in range(R):
        for x in range(C-W+1):
            if B[y][x:x+W].count(1)==c and B[y][x:x+W].count(-1)==0:
                return True
    return False

def BT(R,C,W,B):
    Bt = tuple(tuple(b) for b in B)
    if Bt in memo:
        return memo[Bt]

    ans = 9999
    for y in range(R):
        for x in range(C):
            if B[y][x]==0:
                ans2 = 0

                B[y][x] = 1
                if check(R,C,W,B):
                    if sum(b.count(1) for b in B)==W:
                        ans2 = max(ans2, 1)
                    else:
                        ans2 = max(ans2, BT(R,C,W,B)+1)
                B[y][x] = 0
                
                B[y][x] = -1
                if check(R,C,W,B):
                    ans2 = max(ans2, BT(R,C,W,B)+1)
                B[y][x] = 0

                ans = min(ans, ans2)

    memo[Bt] = ans
    return ans

def solve(R,C,W):
    global memo
    B = [[0]*C for _ in range(R)]
    memo = {}
    return BT(R,C,W,B)

for t in range(input()):
    R,C,W = map(int, raw_input().split())
    print "Case #%s: %s"%(t+1, solve(R,C,W))

A.py

def check(C,W,B):
    c = B.count(1)
    for x in range(C-W+1):
        if B[x:x+W].count(1)==c and B[x:x+W].count(-1)==0:
            return True
    return False

def BT(C,W,B):
    Bt = tuple(B)
    if Bt in memo:
        return memo[Bt]

    ans = 9999
    T = [0]*C
    for x in range(C-W+1):
        if B[x:x+W].count(1)==B.count(1) and B[x:x+W].count(-1)==0:
            for i in range(x,x+W):
                T[i] += 1
    mt = -1
    x = -1
    for i in range(C):
        if B[i]==0 and T[i]>mt:
            mt = T[i]
            x = i

    ans = 0

    B[x] = -1
    if check(C,W,B):
        ans = max(ans, BT(C,W,B)+1)
    B[x] = 0

    if ans==0:
        B[x] = 1
        if B.count(1)==W:
            ans = max(ans, 1)
        else:
            ans = max(ans, BT(C,W,B)+1)
        B[x] = 0

    memo[Bt] = ans
    return ans

def solve(R,C,W):
    global memo
    B = [0]*C
    memo = {}
    ans = BT(C,W,B)
    return ans + (R-1)*((C+2*W-2)/(2*W-1))

for t in range(input()):
    R,C,W = map(int, raw_input().split())
    print "Case #%s: %s"%(t+1, solve(R,C,W))

B.py

def solve(K, L, S):
    for l in L:
        if K.count(l)==0:
            return 0.

    for i in range(1,len(L)+1):
        if L[i:]==L[:-i]:
            d = i
            break
    m = 1 + (S-len(L))/d

    p = 1.
    for l in L:
        p *= float(K.count(l))/len(K)

    return m - p*(S-len(L)+1)

for t in range(input()):
    _,_,S = map(int, raw_input().split())
    K = raw_input()
    L = raw_input()
    print "Case #%s: %.10f"%(t+1, solve(K,L,S))

C.py

def solve(C, D, V):
    d = 0
    v = 0
    N = []
    while v<V:
        if d<len(D) and D[d]<=v+1:
            d += 1
        else:
            N += [v+1]
        v = (sum(D[:d])+sum(N))*C
    return len(N)

for t in range(input()):
    C,_,V = map(int, raw_input().split())
    D = map(int, raw_input().split())
    print "Case #%s: %s"%(t+1, solve(C,D,V))