Google Code Jam 2008 Qualification Round A
(後で書く)
UPPER_BOUND = 10000 num_test = int(fi.readline()) print num_test for test_id in range(num_test): num_engine = int(fi.readline()) engines = [fi.readline() for i in range(num_engine)] num_query = int(fi.readline()) # start DP scores = [0] * num_engine for i in range(num_query): q = fi.readline() if q in engines: # switch target = engines.index(q) target_score = scores[target] for i in range(num_engine): if i == target: scores[i] = UPPER_BOUND else: scores[i] = min(scores[i], target_score + 1) else: # no need to switch engine pass result = min(scores) p("Case #%d: %s" % (test_id + 1, result))