CSC 427: Data Structures and Algorithm Analysis
Fall 2006

HW4: Problem Solving & Sets/Maps

The following problem is written in the style of programming contests. The elegance of your solution is not a major issue here. Instead, you should focus on correctness: your program must handle all possible inputs correctly and produce output of the exact form specified.

This problem involves determining, for a group of gift-giving friends, how much more each person gives than they receive (and vice versa for those that view gift-giving with cynicism). Each person sets aside some money for gift-giving and divides this money evenly among all those to whom gifts are given. However, in any group of friends, some people are more giving than others (or at least may have more acquaintances) and some people have more money than others.

Given a group of friends, the money each person in the group spends on gifts, and a (sub)list of friends to whom each person gives gifts; you are to write a program that determines how much more (or less) each person in the group gives than they receive.

The Input

The input is a sequence of gift-giving groups, stored in a file named input.txt. Each group consists of several lines, with items separated by whitespace:

All gifts are non-negative integers. Each person gives the same integer amount of money to each friend to whom any money is given, and gives as much as possible. Any remaining money is kept by the gift giver and ignored when determining his or her net gain/loss.

The input consists of one or more groups, separated by a line containing a single asterisk.

The Output

For each group of gift-givers, the name of each person in the group should be printed on a line followed by the net gain (or loss) received (or spent) by the person. Names in a group should be printed in alphabetical order.

The output for each group should be separated from other groups by a line containing a single asterisk.

Sample Input

dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
vick 100 0
liz 30 1 steve
steve 55 2 liz dave
dave 0 2 steve liz

Sample Output

amr -150
dave 302
laura 66
owen -359
vick 141
dave 27
liz -3
steve -24