#!/usr/bin/python -tt # solution written by Brad Kusnir 12/12/12 """ Bilateral Projects Problem ID: bilateral A friend of yours works at an undisclosed company in the music streaming industry, and needs your help. The company has offices in Stockholm and London, and collaboration between the two offices is extensive. The situation is that each of the many but small projects is handled by a two-person team with a member in each city. While emails, faxes, and phones are wonderful, and work well within each team, the CEO wants a briefing every year on the projects. For this purpose the CEO invites representatives from the projects to Barbados for a week of beach fun presentations of all the projects. However, money is tight and a new policy has been created: the CEO wants at least one person from each project, and additionally, she wants to invite as few people as possible. This is where you come in. In order to help your friend get a ticket to Barbados, you are to write a program that, given all the two-person teams, computes the smallest number of people that must be invited in order to get at least one person from each project, as well as a list of people to invite. If possible (subject to the set of people being smallest possible), the list of invitees should include your friend. Input The first line of input contains an integer 1 <= m <= 10 000, the number of teams. The following m lines each contain two integers, i, j separated by a space, being the employee IDs of the two employees in that team (the first one is from Stockholm and the second one is from London). Stockholm employees have IDs in the range 1000 to 1999 and London employees have IDs in the range 2000 to 2999. An employee can be a member of several teams, but there cannot be several teams consisting of the same pair of employees. Your friend has ID 1009. Output Output first a single line with an integer k indicating the smallest number of employees that must be invited to meet the requirements above. Then output k lines giving the IDs of employees to invite. If possible (subject to k being smallest possible), the list should contain your friend. If there are several solutions subject to these constraints, anyone is acceptable. Sample input 1 2 1009 2011 1017 2011 Sample output 1 1 2011 Sample input 2 4 1009 2000 1009 2001 1002 2002 1003 2002 Sample output 2 2 2002 1009 """ import sys def main(): # read multiple lines of input #input = raw_input('') f = open(r'sample2.txt','rU') # integer k indicating the smallest number of employees that must be invited k = 0 # integer 1 <= m <= 10 000, the number of teams m = 0 # Your friend has ID 1009. friend_id = 1009 # create a list to hold each team curent_team_members = [] team_list = [] team_dict = {} stockholm_team_list = [] stockholm_team_dict = {} london_team_list = [] london_team_dict = {} counter = 0 current_team_number = 0 for line in f: if counter == 0: m = int(line) if ((m >= 1) and (m <= 10000)): print 'm is in range: ' + str(m) else: print '1 <= m <= 10 000' return # input failed validation - exit routine else: print 'append teams to lists' current_team_number = counter current_team_members = line.split() # create a list of unique stockholm employee id's stockholm_id = int(current_team_members[0]) if stockholm_id < 1000 or stockholm_id > 1999: print 'Stockholm employees have IDs in the range 1000 to 1999' return # input failed validation - exit routine if stockholm_id not in stockholm_team_list: print 'Stockholm id not in Stockholm team list - adding ' + str(stockholm_id) stockholm_team_list.append(stockholm_id) # update stockholm employee and associated teams in stockholm dict if stockholm_id not in stockholm_team_dict: # id does not yet exist in hash table, create inital entry stockholm_team_dict[stockholm_id] = str(current_team_number) else: # id already exists in hash table, update existing entry stockholm_team_dict[stockholm_id] = str(stockholm_team_dict[stockholm_id]) + ',' + str(current_team_number) print 'Stockholm Team Dict: ' + str(stockholm_team_dict) # create a list of unique london employee id's london_id = int(current_team_members[1]) if london_id < 2000 or london_id > 2999: print 'London employees have IDs in the range 2000 to 2999' return # input failed validation - exit routine #if london_team_list.index(london_id) > 0: if london_id not in london_team_list: print 'london id not in london team list - adding ' + str(london_id) london_team_list.append(london_id) # update london employee and associated teams in london dict if london_id not in london_team_dict: # id does not yet exist in hash table, create inital entry london_team_dict[london_id] = str(counter) else: # id already exists in hash table, update existing entry london_team_dict[london_id] = str(london_team_dict[london_id]) + ',' + str(current_team_number) print 'London Team Dict: ' + str(london_team_dict) # merge Stockholm and London dicts into master dict (it may not be necessary to split them out) team_dict = dict(stockholm_team_dict.items() + london_team_dict.items()) print 'Team Dict: ' + str(team_dict) # create a list of teams team_list.append(str(stockholm_id) + ', ' + str(london_id) + ', Team #' + str(current_team_number)) print 'team_list = ' + str(team_list) counter = counter + 1 total_teams = counter print 'Total Number of Teams: ' + str(len(team_list)) #print 'stockholm_team_list = ' + str(stockholm_team_list) #print 'london_team_list = ' + str(london_team_list) # need to normalize at team level - no team should be represented twice unnecesarily to get the smallest # of attendees # use dict to create key pair value for each team # Output first a single line with an integer k indicating the smallest number of # employees that must be invited to meet the requirements above. # use a dict? return if __name__ == '__main__': main()