The Trip

Interview

Time limit1sMemory limit128 MB

Summary
Given what each student spent, find the minimum total money that must change hands so every student ends up paying the same amount within one cent.
Level

Medium4 of 10

Topics
Greedy, Math, Implementation, Sorting
Solved
No attempts yet

Problem

A number of students are members of a club that travels each year to interesting destinations. Past trips have gone to Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring the club is planning a trip to Eindhoven.

The members agree in advance to share all expenses equally. However, it is not practical for everyone to pay an equal part of each cost as it occurs, so individual students pay for particular things such as meals, hotels, taxi rides, and plane tickets. After the trip, each student's total spending is tallied and money is exchanged so that every student's net cost becomes the same, to within one cent.

Settling these payments by hand is tedious and error-prone. Given the amount each student spent, compute the minimum total amount of money that must change hands so that all students' costs are equalized to within one cent.

Input

The input contains the data for several trips. Each trip begins with a line holding a single positive integer nn, the number of students on the trip. The next nn lines each contain one amount of money, in dollars and cents, spent by one student. No trip has more than 10001000 students, and no student spent more than $10,000.00. A line containing a single 00 follows the data for the last trip and must not be processed.

Output

For each trip, print a single line with the minimum total amount of money, in dollars and cents, that must be exchanged so that every student's cost is equal to within one cent. Print the amount with a leading dollar sign and exactly two digits after the decimal point.

Examples3

  1. Example 1

    Input
    3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
0
    Expected output
    $10.00
$11.99

  2. Example 2

    Input
    2
0.00
10.00
0
    Expected output
    $5.00

  3. Example 3

    Input
    5
100.00
200.00
300.00
400.00
500.00
0
    Expected output
    $300.00