Saving the Universe Again

01_Google_Code_Jam_2018.py

def min_hacks(d, p):
    p_list = list(p)
    can_swap = True
    curr_damage, num_of_hacks = (0,)*2

    while can_swap:
        curr_damage, shoot_damage = 0, 1
        for c in p_list:
            if c == 'S':
                curr_damage += shoot_damage
            elif c == 'C':
                shoot_damage *= 2
        if curr_damage > d:
            can_swap = False
            for i in reversed(range(len(p_list) - 1)):
                if p_list[i:i + 2] == ['C', 'S']:
                    p_list[i], p_list[i+1] = p_list[i+1], p_list[i]
                    num_of_hacks += 1
                    can_swap = True
                    break
        else:
            break
    return -1 if curr_damage > d else num_of_hacks


num_of_cases = int(input())
for i in range(1, num_of_cases + 1):
    d, p = input().split()
    solution = min_hacks(int(d), p)
    solution = "IMPOSSIBLE" if solution < 0 else str(solution)
    print("Case #{0}: {1}".format(i, solution))