Internet Problem Solving Contest

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 Ccandies. 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.