Image

Imageunbe

gjc qualification

Kвалификация google code jam 2010. Задачи простые и результат соответствующий - прошли почти все, кто участвовал. Мои решения ниже.

Задача А: Услoвие, 
import sys

T=int(sys.stdin.readline())
for case in range(T):
        (N,K) = map(int, sys.stdin.readline().split())
        need = 2**N - 1
#       print K, need
        on = (K & need) == need
        print "Case #%d: %s" % (case+1, "ON" if on else "OFF")


Задача B: Услoвие, 
import sys

def gcd(a,b):
        while b!=0:
                (a,b) = (b, a % b)
        return a
        

C=int(sys.stdin.readline())
for case in range(C):
        t = map(int, sys.stdin.readline().split())[1:]
        N = len(t)
        dt = [abs(t[i] - t[i-1]) for i in range(N)]
#       print dt
        T = reduce(gcd, dt)
#       print T
        cy = [(T - x % T) % T for x in t]
        y = min(cy)
        print "Case #%d: %s" % (case+1, y)


Задача C: Услoвие, 
import sys

def ride(g, gi):
        on = 0
        qlen = len(g)
        while on + g[gi] <= k and qlen > 0:     
                on += g[gi]
                gi = (gi + 1) % len(g)
                qlen -= 1
        return gi, on

T=int(sys.stdin.readline())
for case in range(T):
        (R,k,N) = map(int, sys.stdin.readline().split())
        g = map(int, sys.stdin.readline().split())
        seen = [None] * N
        rn = 0
        gi = 0
        sum = 0
        while rn < R:
                if seen[gi] is None:
                        seen[gi] = (rn, sum)
                        gi, on = ride(g, gi)
                        rn += 1
                        sum += on
                else:
                        orn, osum = seen[gi]
#                       print "loop at %d: %d, %d -> %d, %d" % (gi, orn, osum, rn, sum)
                        looplen = rn-orn
                        loopsum = sum-osum
                        loops = (R-rn) / looplen
                        rn += loops*looplen
                        sum += loops*loopsum
                        seen = [None] * N
        print "Case #%d: %d" % (case+1, sum)

LJ Video