Sample Input/Output
Input Possible output
12 3 3 5 4 2 1 1 2 2 1 2 0
Hint: If we get all chocolates in one bag, then it is easy to distribute nearly equally. One way of ensuring that a sequence of steps ends up with a given distribution is to define an order relation on the distributions, such that the required distribution is the minimum element. At every step ensure that you move to a distribution that is ‘smaller’ in the ordering. Since there are only finitely many distributions, you will eventually reach the minimum. Can you think of such a relation for this problem?
Submission: Name the file as RollNo 2.cpp and submit on moodle.
Homework: A more general problem is given arbitrary initial and final distributions of chocolates, find a sequence of steps that leads from the initial to the final. Is this always possible? What can you say about the number of moves required?
1
