A number of students are members of a club that travels annually to exotic locations. Since their very successful trip to Eindhoven, their destinations have included Orlando, Vancou- ver, Honolulu, and Beverly Hills. This spring they are planning a trip to Prague. The group agrees in advance to share ex- penses equally, but it is not practical to have them share every expense as it occurs. So indi- viduals in the group pay for particular things, like meals, hotels, taxi rides, plane tickets, etc. After the trip, each student’s expenses are tal- lied 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. Since the Eindhoven trip the club has used a scheme that, for a given list of ex- penses, ensures that the minimum amount of money changes hands in order to equalize (within a cent) all the students’ costs. The students have not found the scheme to be completely satisfactory. Instead of minimizing the amount of money that changes hands, the students now wish to minimize the total number of payments that must be made between individuals. After all it is easier to pay $10.00 to one person than to pay $3.33 to each of three people. 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 10 students and no student spent more than $10,000.00. A single line containing ‘0’ follows the information for the last trip. Output For each trip, output a line stating the total number of payments that must be made between individuals to equalize the students’ costs within one cent. Sample Input 3 10.00 20.00 30.00 4 15.00 15.01 3.00
2/2 3.01 4 15.00 15.00 15.00 10.00 2 0.95 0.93 0 Sample Output 1 2 3 1