DWITE Online Computer Programming Contest

Penny Game

October 2011
Problem 2

Extra change can be a big burden to carry around with you. So, you decide to leave your stacks of (identical) pennies you have at home. However, these stacks aren’t of the same size, and look a little messy. You want to move pennies between these stacks so that all the stacks eventually have the same size; it is guaranteed that you are able to do this. You want to do this by making the smallest number of moves possible, where one move consists of taking one penny from a stack and adding it to another stack. For example, if you have three stacks with 4, 5, and 6 pennies, you have to move one penny from the third stack to the first stack so that they all end up with 5 pennies each. Write a program that helps you out with this task.

The input file DATA2.txt will contain 5 sets of input. The first line of each set is a number 1 ≤ N ≤ 50, the number of stacks you have. The next N lines each contain a number 1 ≤ M ≤ 1000, the number of pennies in that stack.

The output file OUT2.txt will contain 5 lines of output, each a single number: the minimum number of moves required to make every stack have an equal number of pennies.

Sample Input (only first case shown):
Sample Output (only first case shown):