Meh, missed edge case of an RFP having NO requirements at all. Other than that pretty easy problem. Could have done it without using a heap and keeping track of some variables but I used one anyways.<\/p>\n
\r\nimport java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\nimport java.io.PrintWriter;\r\nimport java.util.ArrayList;\r\nimport java.util.Comparator;\r\nimport java.util.PriorityQueue;\r\nimport java.util.StringTokenizer;\r\n\r\n\/**\r\n * \r\n * @author Sanchit M. Bhatnagar\r\n * @see http:\/\/uhunt.felix-halim.net\/id\/74004\r\n * \r\n *\/\r\npublic class P10141 {\r\n\r\n public static void main(String[] args) throws NumberFormatException, IOException {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n PrintWriter out = new PrintWriter(System.out);\r\n StringTokenizer st = null;\r\n\r\n boolean first = true;\r\n int test = 1;\r\n String line = null;\r\n while ((line = br.readLine()) != null) {\r\n st = new StringTokenizer(line);\r\n int N = Integer.parseInt(st.nextToken());\r\n int P = Integer.parseInt(st.nextToken());\r\n if (N == 0 && P == 0)\r\n break;\r\n if (!first)\r\n out.println();\r\n ArrayList<String> requirements = new ArrayList<String>();\r\n for (int i = 0; i < N; i++) {\r\n requirements.add(br.readLine());\r\n }\r\n\r\n PriorityQueue<Offer> heap = new PriorityQueue<Offer>(P, new Comparator<Offer>() {\r\n @Override\r\n public int compare(Offer arg0, Offer arg1) {\r\n if (arg0.compliance == arg1.compliance) {\r\n if (arg0.price == arg1.price) {\r\n return Integer.compare(arg0.idx, arg1.idx);\r\n } else {\r\n return Double.compare(arg0.price, arg1.price);\r\n }\r\n } else {\r\n return Double.compare(arg1.compliance, arg0.compliance);\r\n }\r\n }\r\n });\r\n\r\n for (int i = 0; i < P; i++) {\r\n String name = br.readLine();\r\n st = new StringTokenizer(br.readLine());\r\n double price = Double.parseDouble(st.nextToken());\r\n int offer = Integer.parseInt(st.nextToken());\r\n int count = 0;\r\n for (int j = 0; j < offer; j++) {\r\n br.readLine();\r\n count++;\r\n }\r\n heap.add(new Offer(name, price, count, i));\r\n }\r\n out.println("RFP #" + test);\r\n out.println(heap.poll().name);\r\n test++;\r\n first = false;\r\n }\r\n\r\n out.close();\r\n br.close();\r\n }\r\n\r\n private static class Offer {\r\n int idx;\r\n String name;\r\n double price;\r\n double compliance;\r\n\r\n public Offer(String name, double price, double compliance, int idx) {\r\n this.name = name;\r\n this.price = price;\r\n this.compliance = compliance;\r\n this.idx = idx;\r\n }\r\n }\r\n\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Meh, missed edge case of an RFP having NO requirements at all. Other than that pretty easy problem. Could have done it without using a heap and keeping track of some variables but I used one anyways. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer; \/** * … Continue reading UVA 10141 – Request for Proposal<\/span>