Problem A: The Trip
A number of students are members of a club that travels annually to exotic locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven.
The group agrees in advance to share expenses equally, but it is not practical to have them share every expense as it occurs. So individuals in the group pay for particular things, like meals, hotels, taxi rides, plane tickets, etc. After the trip, each student's expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within a cent) all the students' costs.
Standard input will contain the information for several trips. The information for each trip consists of a line containing a positive integer, n, the number of students on the trip, followed by n lines of input, each containing the amount, in dollars and cents, spent by a student. There are no more than 1000 students and no student spent more than $10,000.00. A single line containing 0 follows the information for the last trip.
For each trip, output a line stating the total amount of money, in dollars and cents, that must be exchanged to equalize the students' costs.
Output for Sample Input
Given N integers representing the expenses in cents of N persons in a trip. Find the least total amount of money to exchange among them so that the final expense of anyone is within a cent of all others. That is, if there are 3 persons, A, B, and C, then the difference between A's and B's expenses is at most one cent, between A's and C's is at most one cent, and between B's and C's is also at most one cent.
Many people use float, double, or long double to read in the amount (given in dollars). This leads to many rounding problems. Instead, we can use integer to store the amount in cents. For example, if the input is 3.14, we can read in 3, the dot, and 14, and the amount then is 3*100 + 14.
int dollar, cent, amount;
cin >> dollar >> dot >> cent;
amount = dollar * 100 + cent;
Of course, we need to take the average. The trip goers are then divided into two groups, those spent more, and those did less. Our job is to get everyone spending as close to this average as possible.
Those who spent less must pay extra cash. This cash is use to offset those who spent more. Let's call this a virtual common fund which a less-spender must deposit in, and a more-spender can withdraw from. This fund could go below zero.
An important realization is that since we are using integer division, the average expense is closer to the less-spenders. The more-spenders, therefore, need withdraw from the common fund only as much as it takes to make his spending to average plus one cent. The less-spenders, however, must pay in full to make his spending to exactly the average. This way, we guarantee that everyone's expense is within one cent of all others'.
If after everything is settled and the fund is non-negative, we say that the less-spenders have repaid the more-spenders so that both are within one cent of the average expense. In addition, if the common fund is negative, the less-spenders need to pay that much more to make the fund balanced (to make it zero).
With that reasoning, the answer is simply the sum that less-spenders must pay to make their expense up to the average, plus any amount of negative fund.
In the end, the algorithm is a two-pass traversal of the expense array. The first pass is to find out the total of all expenses to calculate their average. The second pass performs fund adjustment depending on whether the spender is a less-spender or a more-spender. At the same time, the second pass also accumulates total sum that less-spenders must pay for (called top-up sum). If the fund is non-negative, the solution is this top-up sum; if it is negative, the solution is this top-up sum minus the fund (that is, plus the absolute value of the fund).