Howdy! This time, problems started getting more and more complex, and that’s good, because I like the challenge! The next problem is Get to Work:
You work for a company that has E employees working in town T. There are N towns in the area where the employees live. You want to ensure that everyone will be able to make it to work. Some of the employees are drivers and can drive P passengers. A capacity of
P == 1indicates that the driver can only transport themselves to work. You want to ensure that everyone will be able to make it to work and you would like to minimize the number of cars on the road.
You want to calculate the number of cars on the road, with these requirements:
- Every employee can get to town T.
- The only way an employee may travel between towns is in a car belonging to an employee.
- Employees can only take rides from other employees that live in the same town.
- The minimum number of cars is used.
Find whether it is possible for everyone to make it to work, and if it is, how many cars will end up driving to the office.
Whoa, that’s way more complex than the other problems, but still, not that hard! What we need to do is: check who are drivers and passengers for each town (since they can only help same town buddies), if the total capacity of cars from a town is inferior to the number of passengers, the problem cannot be solved and so, reported as “IMPOSSIBLE”. If we can carry everyone, start filling the cars from the “minivan” (can carry more passengers) to the “mini cooper”. 😀 That way we can make sure there are fewer cars on the road.
Some rough, but commented, and validated (!) python code follows:
for case in range(1,int(raw_input())+1): # For all test cases town_len, office = map(int, raw_input().split(" ")) # Get amount of towns and office carriers = [ for x in xrange(town_len)] # Create new lists for every town capacities = town_len *  # Initialize "capacity of transportation" payload = town_len *  # Initialize "cargo" for each town for i in range(int(raw_input())): # Get and go through employee list town, capacity = map(int, raw_input().split(" ")) # Get the current employee info if town == office: # If employee is from office town continue # No need to commute, ignore town -= 1 # Adjust "town" to zero-based index payload[town] += 1 # Employee needs to commute, count if capacity != 0: # If employee has a car capacities[town] += capacity # Add to our capacities for the town carriers[town].append(capacity) # Append its car capacity resultStr = "" # Create our result string for i in range(town_len): # For all towns if capacities[i] < payload[i]: # If we can't carry everyone resultStr = "IMPOSSIBLE " # declare it impossible, give up break; cars = 0 # We can carry, start with 0 cars carriers[i].sort() # Sort and reverse the car list carriers[i].reverse() for car in carriers[i]: # So we can start from the bigger ones if (payload[i] <= 0): # If we're carrying everybody already break # we're done for this town payload[i] -= car # Else, fill a car, report as being used cars += 1 resultStr += str(cars)+" " # Add this town filled vehicles print "Case #%d: %s" % (case, resultStr[:-1]) # Report results, remove last space
As the last problem, the same can be told about this code. There are many ways to improve its performance, but this way it can already solve the large inputs in an instant. Bitbangers apart, it solves the problem and everybody gets happy. Also, I think it is quite clear to understand, even more with the comments. 🙂 Bye!