Internet Problem Solving Contest

IPSC 2005

Solution to Problem P – Polly Wanna Cracker

Let P be the number of parrots and N be the number of crackers. Then Mirko makes c=N/P (entire) rounds before he runs out of crackers. The remaining r=N mod P crackers go to parrots 1..r. This means that the first r parrots get c+1 crackers each, the remaining P-r parrots get c crackers each. This leads to a straightforward program that solves the easy input. For the hard input you should have implemented big integer arithmetic – or use a tool that has built-in large integers. (The tool of our choice is usually bc, but there are many suitable scripting languages out there, not to mention the BigInteger class in Java.) The number of parrots is small enough (it can be stored in a 32-bit int), so if you did it on your own, you only had to implement division by a small integer.