Monday, August 8, 2011

Problem 10137: The Trip

Original problem statement

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.

The Input

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.

The Output

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.

Sample Input
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
0

Output for Sample Input
$10.00
$11.99

Restated problem

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.

Reading input

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;
char dot;
cin >> dollar >> dot >> cent;
amount = dollar * 100 + cent;

Solution

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).

4 comments:

  1. i didn't understand the problem........ can you explain the second sample output

    ReplyDelete
  2. Mavrik, the second sample can be explained like this. Four persons in a trip. They pay 15.00, 15.01, 3.00, and 3.01. The problem is to calculate the TOTAL SUM of money that must change hands to equalize (within 1 cents) the costs.

    The average is 9.00. So the less-payers (3.00 and 3.01) must pay to the more-payers (15.00 and 15.01). The sum is therefore (9.00 - 3.00) + (9.00 - 3.01), which is 11.99.

    I hope that clarifies the problem.

    ReplyDelete
  3. theres problem with input method recommended
    for the cent
    the value 10 and 01 ,are the same

    ReplyDelete
  4. Really? Do you have a test case? I'd appreciate it if you could share your test case with me.

    ReplyDelete