Google Code Jam 2018 QR Problem A

a.py

import sys, copy;
def modify(a, i, z, d):
    x = a[i]
    y = x['v']
    m = z['m']
    damage = z['d']
    print "y=", y
    while (y > 0):
                        x['v'] -= 1
                        a[i-1]['v'] += 1
                        m += 1
                        damage -= x['p'] / 2
                        if damage <= d:
                            z['m'] = m;
                            z['d'] = damage;
                            return m
                        print x['v'], x, a[i-1]['v'], m, a
                        y = x['v']
                        print "y=", y
                        print y > 0
                        print "m=",m
                        
    z['m'] = m;
    z['d'] = damage;
    return m;
def solve(d,p):
    ss = 0
    cc = 0
    for c in p:
        if c == 'S':
            ss+=1
        elif c == 'C':
            cc+=1
    if ss == 0:
        return 0;
    if d < ss:
        return "IMPOSSIBLE"
    power = 1
    damage = 0
    a = []
    v = 0
    for c in p:
        if c == 'S':
            damage += power
            v += 1
        elif c == 'C':
            a.append({'v':v,'p':power})
            power *= 2;
            v = 0
    a.append({'v':v,'p':power})
    if damage <= d:
        return 0;
    for c in p[::-1]:
        if c == 'S':
            ss+=1
    """a =  [0] * cc;
    for i in range(cc):
        a.push(0)"""
    #print a
    m = 0;
    #print "Damage:", damage
    #print "D:", d
    for i in reversed(range(len(a))):
        x = a[i]
        #print i, x, a
        if x['v'] == 0:
            continue
        if x['p'] > 1:
            """z = {'m':m, 'd':damage}
            print "zm=",z['m']
            print "zd=",z['d']
            modify(a, i, z, d);
            print "zm=",z['m']
            print "zd=",z['d']
            m = z['m']
            damage = z['d']
            if damage <= d:
                return m"""
            y = x['v']
            #print "y=", y
            while (y > 0):
                x['v'] -= 1
                a[i-1]['v'] += 1
                m += 1
                damage -= x['p']/2
                if damage <= d:
                    #print "y=", y
                    #print y > 0
                    #print "m=", m
                    return m
                #print x['v'], x, a[i-1]['v'], m, a
                y = x['v']
                #print "y=", y
                #print y > 0
    #print a
    return m
#print 1 > 0
#inputFile =  sys.argv[1] if (len(sys.argv) > 1) else "input.txt";
#outputFile = sys.argv[2] if (len(sys.argv) > 2) else (inputFile + "out.txt") if (len(sys.argv) > 1) else "output.txt";
#print(inputFile, outputFile)
#file = open(outputFile, "w")

#with open(inputFile, 'r') as f:
t = int(raw_input())
#print(t)
for i in range(1, t + 1):
    d,p = raw_input().split()
    d = int(d)
    print "Case #" + str(i) + ": " + str(solve(d,p))
    #file.write(str(solve(d,p)) + "\n")
#file.close()