#!/usr/bin/env python # Countdown # Phil Bordelon import os import sys DEBUG = os.getenv("DEBUG", False) # The handy Collection class, empty but useful. class Collection(object): pass def readCountdown(): # The first element in a given dataset is the number of lines # in the countdown definition. After that, it's a series of # strings that define the countdown. command_count = int(sys.stdin.readline()) # Initialize the countdown 'object'. This is really just two # different things we track: the start time of the countdown, # and the various conditions and the time costs associated with # them. countdown = Collection() countdown.start_time = None countdown.condition_dict = {} # We're going to temporarily store conditions in the condition # list, until we populate the dictionary. We do this because # there are potentially conditions that don't actually effect # the countdown: those that occur "before" the countdown starts. # (Devious? Yes. I didn't even think of this when I came up with # the problem; it just came to me when I sat down to write this # solution. And it was too good of a "gotcha" to pass up. I'd # apologise, but I used to be a contestant too, and these sorts of # head-slapping moments are worth any bad mojo you may send my way.) possible_condition_list = [] for command_loop in range(command_count): line = sys.stdin.readline().strip() # Break the line down into elements. 'time' is always the first # one. line_elements = line.split() if len(line_elements) < 2: sys.exit("ERROR: Invalid command line '%s'!" % line) time = int(line_elements[0]) if time <= 0 or time > 1440: sys.exit("ERROR: Invalid time %d!" % time) # The next word is either 'START' or 'HOLD' (with lots of stuff # after it). start_or_hold = line_elements[1] if start_or_hold == "START": # This is the start time. Important! Store it. if countdown.start_time: sys.exit("ERROR: Two start times (%d and %s)!" % (countdown.start_time, time)) countdown.start_time = time else: # All other 'time' values are actually completely worthless in terms # of computation ... except that we need to ignore directives that # happen at starting numbers "earlier" than the starting value. So # stuff it in the list of /possible/ directives, and then later save # it if we need it. # All holds are of the format: # # time HOLD length [IF [NOT] condition] # # We can pull 'length' out now. length = int(line_elements[2]) # See if this is a boring hold, or an 'if' hold, based on the number # of elements in the string. if len(line_elements) == 3: # Boring mandatory hold, like "30 HOLD 50". possible_condition_list.append((time, length, None, None)) elif len(line_elements) == 5: # Hold IF condition, like "40 HOLD 10 IF philfixedit". if line_elements[3] != "IF": sys.exit("ERROR: No 'IF' in command '%s'!" % line) condition = line_elements[4] # We store possible conditions in a tuple of the format: # # (time, length, condition, if_or_if_not) # # We could just use the Collection object again, but, uh, it # seems that I didn't do that when I wrote this. possible_condition_list.append((time, length, condition, True)) elif len(line_elements) == 6: # Hold IF NOT condition, like "40 HOLD 10 IF NOT underattack". if line_elements[3] != "IF" or line_elements[4] != "NOT": sys.exit("ERROR: No 'IF NOT' in command '%s'!" % line) condition = line_elements[5] possible_condition_list.append((time, length, condition, False)) else: sys.exit("ERROR: Invalid command line '%s'!" % line) # Now that we've pulled in all of the conditions, we only want the ones # where the time is less than the countdown start time. condition_list = [x for x in possible_condition_list if x[0] < countdown.start_time] # Now we convert the list of countdowns into a dictionary keyed off of the # condition. There will be a certain amount of extra time that will be # charged if conditions are true, and a certain amount of extra time that # will be charged if conditions are false. Since conditions don't change # during a given countdown, we can simply track the total of all of the # 'if true' lines, and all the 'if false' lines. We can also track the # mandatory holds by summing them up. condition_dict = countdown.condition_dict # Initialize the dictionary with the MANDATORY hold object; the first # element in the list is the 'if true' value, and the second is the # 'if false' value. MANDATORY conditions could be considered to always # be true /or/ false, so that we don't have to special-case our math later. condition_dict["MANDATORY"] = [0, 0] for condition in condition_list: # Break the tuple back out to its constitutent bits. 'time' is useless # now, as we've already removed all of the events that occur before the # countdown starts, but it's clearer to see it than to use slices. time, length, condition, true_or_false = condition # Check condition to see if it's 'None', in which case it's mandatory. if not condition: # Since this is a mandatory hold, it happens whether or not we want # it to; simulate that by adding to both the true and false bits. condition_dict["MANDATORY"][0] += length condition_dict["MANDATORY"][1] += length else: # Create a new entry in the dictionary if one doesn't already # exist; if it does, this is just another hold dependent on a # condition that's already come up, and we'll just be adding to # the true or false costs for that condition. if condition not in condition_dict: condition_dict[condition] = [0, 0] # Add to the proper value. if true_or_false: condition_dict[condition][0] += length else: condition_dict[condition][1] += length # Thanks to the magic of Python, condition_dict == countdown.condition_dict, # so we're done. Return the countdown object. return countdown def calculateCountdown(countdown): # Calculate the maximum and minimum countdown times. This is easy; for the # minimum, we pick the smallest of the two times for each condition, and for # the maximum we pick the largest. minimum_time = countdown.start_time maximum_time = countdown.start_time for condition in countdown.condition_dict: true_num, false_num = countdown.condition_dict[condition] minimum_time += min(true_num, false_num) maximum_time += max(true_num, false_num) # Print! print "%d TO %d" % (minimum_time, maximum_time) if "__main__" == __name__: dataset_count = int(sys.stdin.readline()) for dataset_loop in range(dataset_count): # Read the countdown in ... countdown = readCountdown() if DEBUG: for condition in countdown.condition_dict: condition_list = countdown.condition_dict[condition] print "%s: %d, %d" % (condition, condition_list[0], condition_list[1]) # ... and calculate the minimum and maximum values. Easy. calculateCountdown(countdown)