We can describe the current state in the classroom with a bitmask, where the value of each bit tells whether a child received an even or odd number of melons during the previous class.

There are ~2^N~ of these states, or about ~10^6~ for ~N = 20~. With a number of classes larger than this, a state is guaranteed to repeat and, once it does, it will keep looping through the same cycle. We can calculate the number of throws in one iteration of the cycle in ~\mathcal O(N \cdot 2^N)~ and, with careful implementation, skip most of the iterations through the cycle.