import java.util.Scanner; import java.io.File; import java.io.PrintStream; import java.util.TreeMap; /** * Program for solving the greedy gift-givers problem. * @author Dave Reed * @version 11/20/08 */ public class GreedyGiftGiver { public static void main(String[] args) throws java.io.FileNotFoundException { Scanner infile = new Scanner(new File("input.txt")); PrintStream outfile = new PrintStream("output.txt"); while (infile.hasNextLine()) { processGroup(infile, outfile); } } public static void processGroup(Scanner infile, PrintStream outfile) { TreeMap netGains = new TreeMap(); while (infile.hasNextLine()) { String line = infile.nextLine(); if (line.equals("*")) { break; } Scanner inline = new Scanner(line); String giver = inline.next(); int amount = inline.nextInt(); int numGivees = inline.nextInt(); int giftAmount = 0; if (numGivees > 0) { giftAmount = amount / numGivees; } if (!netGains.containsKey(giver)) { netGains.put(giver, 0); } netGains.put(giver, netGains.get(giver)-(numGivees*giftAmount)); for (int i = 0; i < numGivees; i++) { String nextGivee = inline.next(); if (!netGains.containsKey(nextGivee)) { netGains.put(nextGivee, 0); } netGains.put(nextGivee, netGains.get(nextGivee)+giftAmount); } } for (String str : netGains.keySet()) { outfile.println(str + " " + netGains.get(str)); } if (infile.hasNextLine()) { outfile.println("*"); } } }