## IPSC 1999

## Solution to Problem B – Candy

This was the easiest problem of the contest. We provide correct output
files and a program solving the problem.

The algorithm is very simple. First, read input into an array and count
the total number of candies in all packets. If the total number of candies
is not divisible by number of packets, it is not possible for all
packets to be of the same size. Otherwise compute the number of candies
**C** that should be in one packet. The smallest number of moves can
be achieved in such way that you always remove one candy from any packet that
contains more than **C** candies and put it into a packet that
contains less than **C**candies. Thus, the total number of moves can
be computed as a sum of all candies that has to be removed from all the
packets containing more than **C** candies. Note, that in the
difficult data set the sum of all candies exceeded 32767 and thus you should
use **4-byte integers.**

Answers for the B1 data set could be computed easily by hand. This
input contained only two very small and trivial blocks of data (with 5 and
3 packets) and one block with 101 packets. Sizes of packets in this block
made an arithmetic progression 3,4,5,...,103. Well-known formula says that
1+2+3+...+n=(n+1)n/2. The total number of candies could be computed as
1+2+...+103-1-2=103*104/2-3=103*52-3=5353. Next we get 5353/101=53, thus
each packet should contain 53 candies. We should remove 1 candy from a
packet that contains 54 candies, 2 candies from a packet that contains 55
candies, ..., 50 candies from a packet that contains 103 candies. Thus the
number of candies moved is 1+2+...+50=50*51/2=25*51=1275.

Since there are three team members and only one computer, it is probably
clever to compute at least some of the inputs by hand. On the other side
this problem was so easy that it might take less time to write a program than
to do computation mentioned above by hand.