Google Code Jam 2012 Round 1A Problem B. Kingdom Rush

Kingdom Rush

手数も星も、最初から星2個を狙った方が得。星を1個だけ取るレベルをいかに減らすかという問題。各回では、星を2個取れるレベルがあるならば、そのレベルに挑戦する。星を1個しか取れないレベルしかないならば、星を2個取るのに必要な星が多いレベルから挑戦する。星を2個取るのに必要な星が少ないレベルは、後で星2個を一気に取れるかもしれないから。

#coding: utf-8
for test in range(input()):
    N = input()
    L = [map(int,raw_input().split())for i in xrange(N)]
    C = [0]*N   # 各レベルで獲得した星数
    star = 0
    turn = 0
    while True:
        t = -1
        # 星を2個取れるレベルがあるなら、そのレベルに挑戦
        for i in xrange(N):
            if C[i]<=1 and star>=L[i][1]:
                t = i
        # 星を2個取れるレベルが無ければ、星を2個取るのに必要な星が多いレベルに挑戦
        if t==-1:
            for i in xrange(N):
                if C[i]==0 and star>=L[i][0] and (t==-1 or L[i][1]>L[t][1]):
                    t = i
        # 星を取れるレベルが無ければ、終わり
        if t==-1:
            break
        
        l = 2 if star>=L[t][1] else 1
        star += l-C[t]
        C[t] = l
        turn += 1
    print "Case #%s: %s"%(test+1,turn if min(C)==2 else "Too Bad")