DWITE Online Computer Programming Contest, April 2010, Problem 3
Having just found a bug in billing software, you've realized that some customers have been charged an excess amount. While some may not notice or care regarding small increases in charges, the extra money is just not worth the sacrifice in reputation of the company. The decided solution is to subtract the excess amount from the existing outstanding bills.
The input will contain 5 sets of input. Each set starts with an integer on the first line; followed by lines of "current bills" in the form of payerID value; followed by integer ; followed by lines of amendments, also in the form of payerID value, where the amendment value is a positive integer that needs to be subtracted out of current bills. Bill values are also positive integers.
A particular payerID might have multiple current bills. A particular payerID might also have multiple amendments to be processed. If the amendment value is greater than the first bill in the list, take the full amount out of it (setting the bill value to 0) and continue with the following bills in order. All bill values are positive. A payerID will always have been billed enough for at least the full amendment amount, but possibly across multiple bills.
The output will contain 5 sets of output — adjusted new bills, in the same order as the input sets.
Note: the order of bills and amendments is not guaranteed. Some payerIDs might not have any amendments.
3 set1_one 10 set1_one 10 set1_two 10 2 set1_one 15 set1_two 5 2 set2_one 10 set2_one 10 1 set2_one 20 1 set3_one 20 2 set3_one 5 set3_one 10
set1_one 0 set1_one 5 set1_two 5 set2_one 0 set2_one 0 set3_one 5