Google Code Jam 2012 Round 1A Problem B. 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")