UVa 10137

From Algorithmist
Jump to navigation Jump to search

10137 - The Trip[edit]

Summary[edit]

A clever arithmetic based problem related to a common task. Given a list of expenditures, find the minimum amount of money that must change hands to equalize the expenditures (within one cent).

Explanation[edit]

Calculate the average expenditure and round it to two decimal places. (You'll need to write your own rounding function).

Now the expenditure can be equalized in two ways, and you'll need to account for both of them and select the appropriate answer. You'll need to keep track of the difference from subtracting the average from the currentStudentPayment (when currentStudentPayment > average) as well as the difference from subtracting the currentStudentPayment from the average (when currentStudentPayment < average). These will either be equal to each other or they will differ by $0.01.

It can be explained in the following pseduocode.

If (currentStudentPayment > averagePayment)
   positiveDifference += currentStudentPayment - averagePayment;
Else
   negativeDifference += averagePayment - currentStudentPayment;

if(negativeDifference < positiveDifference)
   return negativeDifference
else
   return positiveDifference

Implementation[edit]

Make sure to use doubles throughout. Do not round off the total.

Alternately, use only 32-bit integer variables in your solution. (Each sum we need to store is between 0 and 1,000,000,000 cents and it is possible to avoid floating-point math.)

Input[edit]

3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
5
56.22
44.00
39.99
1.02
1000.00
0

Output[edit]

$10.00
$11.99
$771.75

Solutions[edit]

C: http://snippets.dzone.com/posts/show/5207