The problem:
For anyone looking at this problem, here’s something that you should know about this problem. Although it’s not explicitly stated that I saw, the sample data implies that if an employee is in the office hometown, that person does not need to commute via a vehicle and can be excluded.
Other than that, it’s relatively simple. Create a list of employees with their hometown and commuter capacity, then just iterate through that list (sorted by commuter capacity) for each hometown. You should be able to either determine that minimum number of cars needed or that it’s impossible relatively quickly.
Here’s the C# code that I used to solve the problem.
| C# | | copy code | | ? |
| 001 | using System; |
| 002 | using System.Collections.Generic; |
| 003 | using System.Linq; |
| 004 | using System.Text; |
| 005 | using System.IO; |
| 006 | using System.Collections; |
| 007 | |
| 008 | namespace get_to_work |
| 009 | { |
| 010 | class Program |
| 011 | { |
| 012 | static void Main(string[] args) |
| 013 | { |
| 014 | string path = args[0]; |
| 015 | |
| 016 | StreamReader reader = new StreamReader(path); |
| 017 | StreamWriter writer = new StreamWriter(path + ".out", true); |
| 018 | |
| 019 | int numTestCases = int.Parse(reader.ReadLine()); |
| 020 | int currNum = 0; |
| 021 | int numTowns = 0; |
| 022 | int officeTown = 0; |
| 023 | int numEmployees = 0; |
| 024 | string commute = null; |
| 025 | string[] officeInfo = null; |
| 026 | bool impossible = false; |
| 027 | List<Employee> employees = null; |
| 028 | |
| 029 | while (!reader.EndOfStream) |
| 030 | { |
| 031 | officeInfo = reader.ReadLine().Split(new char[] { ' ' }); |
| 032 | impossible = false; |
| 033 | currNum++; |
| 034 | writer.Write("Case #" + currNum + ": "); |
| 035 | officeTown = Int32.Parse(officeInfo[1]); |
| 036 | numTowns = Int32.Parse(officeInfo[0]); |
| 037 | numEmployees = Int32.Parse(reader.ReadLine()); |
| 038 | employees = new List<Employee>(); |
| 039 | commute = ""; |
| 040 | |
| 041 | for (int i = 0; i < numEmployees; i++) |
| 042 | { |
| 043 | string[] employee = reader.ReadLine().Split(new char[] { ' ' }); |
| 044 | int town = Int32.Parse(employee[0]); |
| 045 | int capacity = Int32.Parse(employee[1]); |
| 046 | employees.Add(new Employee(town, capacity)); |
| 047 | } |
| 048 | |
| 049 | var towns = employees.Select(r => r.hometown).Distinct(); |
| 050 | for (int i = 1; i <= numTowns; i++) |
| 051 | { |
| 052 | var employees_in_town = employees.Where(e => e.hometown == i); |
| 053 | |
| 054 | if (employees_in_town.Count() == 0 || i == officeTown) |
| 055 | commute = commute + "0 "; |
| 056 | else if (employees_in_town.Sum(e => e.passengers) < employees_in_town.Count()) |
| 057 | { |
| 058 | impossible = true; |
| 059 | break; |
| 060 | } |
| 061 | else |
| 062 | { |
| 063 | commute = commute + computeVehicles(employees_in_town) + " "; |
| 064 | } |
| 065 | } |
| 066 | if (commute.EndsWith(" ")) |
| 067 | { |
| 068 | commute = commute.Substring(0, commute.Length - 1); |
| 069 | } |
| 070 | |
| 071 | if (impossible) |
| 072 | { |
| 073 | writer.WriteLine("IMPOSSIBLE"); |
| 074 | } |
| 075 | else |
| 076 | { |
| 077 | writer.WriteLine(commute); |
| 078 | } |
| 079 | |
| 080 | writer.Flush(); |
| 081 | } |
| 082 | } |
| 083 | |
| 084 | static int computeVehicles(IEnumerable<Employee> employees) |
| 085 | { |
| 086 | int totalVehicles = 0; |
| 087 | int totalCommuters = employees.Count(); |
| 088 | |
| 089 | foreach (Employee employee in employees.OrderByDescending(e => e.passengers)) |
| 090 | { |
| 091 | totalCommuters = totalCommuters - employee.passengers; |
| 092 | totalVehicles++; |
| 093 | if (totalCommuters <= 0) |
| 094 | { |
| 095 | break; |
| 096 | } |
| 097 | } |
| 098 | |
| 099 | return totalVehicles; |
| 100 | } |
| 101 | } |
| 102 | |
| 103 | public struct Employee |
| 104 | { |
| 105 | public int hometown; |
| 106 | public int passengers; |
| 107 | |
| 108 | public Employee(int h, int p) |
| 109 | { |
| 110 | hometown = h; |
| 111 | passengers = p; |
| 112 | } |
| 113 | } |
| 114 | } |
| 115 |
