여행 비용을 공평하게 나누어라! (프로그래밍 도전과제)

2008년 11월 23일 at 11:13 am

여행 

 

한 클럽의 학생들이 있는데 이들은 매년 다른 곳으로 여행을 간다. 과거 그들의 목적지는 인디애나폴리스, 피닉스, 내쉬빌, 필라델피아, 산호세, 애틀랜타 등이었다. 이번 봄에 그들은 아인트호벤으로의 여행을 계획하고 있다.

 

그들은 여행 경비를 동등하게 지불하고자 하지만, 모든 비용을 발생할 때마다 분배하는 것은 현실적으로 불가능하다. 따라서 각자는 식비, 숙박비, 택시비, 비행기표 등을 지불한다. 여행이 끝난 후에 각 학생들의 각 지출이 계산되고, 돈은 교환될 것이며 따라서 결국 비용은 센트 단위까지 같을 것이다. 과거에는 이러한 돈 계산이 지루하고 시간을 지나치게 소모하는 일이었다. 당신이 할 일은 지출내역으로부터 교환되어야 할 돈의 최소량을 동등하게(센트 단위까지) 모든 학생들에게 분배하는 것이다.

 

Input

Standard input will contain the information for several trips. Each trip consists of a line containing a positive integer n denoting the number of students on the trip. This is followed by n lines of input, each containing the amount spent by a student in dollars and cents. 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.

 

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

 

Sample Output

 

$10.00

$11.99

 

 

 

http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110103&format=html