In this problem the contestant is asked to solve a variant of the Nim game (whose description can be found online). Rather than piles and objects, the game here is played with classes and students. Moreover, the players are ”polite” – they never take more students than in the previous turn, and never take more than K students in a turn. The solutions to the various subtasks follow.

3.1 Subtask 1

When K = 1, each player takes one student each turn. The classes are irrelevant, all that matters is the total number of students. If it is even, the second player wins, otherwise the first player wins. It is worth noting that the sum overflows the int data type.

3.2 Subtask 2

In this subtask, a brute-force solution is awarded points. Create a function wins(v) that returns 1 if and only if a player wins if starting from a sequence of classes of sizes 4described in vector v. Make the function memoize its results. When calculating a result, simply try all possible moves, and use wins recursively – if there exists a move that leads to a losing state, then the initial state is winning; otherwise, it is not. It can be proved that, if the answers are memoized, at most ~2^N~ of them must be calculated.

3.3 Subtask 3

A better brute-force solution is needed here. Create an array ~d[i_1][i_2][i_3][i_4][i_5]~. This will be 1 if and only if, starting from a state with ~i_j~ classes of size ~j~ (for ~j = 1, 2, 3, 4, 5~), the player who moves first wins. Initialise this array so that each index is between ~0~ and ~10~ (it thus has ~10^5~ total entries). Calculate this array recursively similarly to the previous subtask, by simulating all possible moves, and checking if a losing state can be reached. When answering a query, look up the solution in the array.

3.4 Subtask 4

Here, N = 1. Suppose that K = 1. Then the solution is determined by the parity of the number of students (like in subtask 1). Otherwise, suppose there are an odd number of students. Then, if the first player takes one student, the second is forced to take one also, and so on – and the first player wins. So we know how to solve the problem if K = 1 or N is odd. Now, what if K > 1 and N is even?

Suppose this is the case, and note that the player who selects an odd number will certainly lose (since the opponent is given a state where there are an odd number of students, and thus can select one student, and win). So we can consider that both players only make even moves, and ”give up” instead of playing an odd move. But, then we can just divide K and the size of the lone class by 2, and reach an equivalent game state!

This observation completes the solution. Simply continue to divide the class size and K by two until either the class size becomes odd, or K becomes 1, at which point the problem can be easily solved.

3.5 Subtask 5 + 6 + 7

As before, if K is one then the game is solved, and if the total number of students is odd, the game is also solved. So suppose K is not one and there are an even number of students. The key observation is that we can divide all class sizes by two (ignoring the remainder) without changing the winner of the game (since the only case in which that remainder will be relevant is if an odd move is made, in which case the game is decided). So adapt the solution from the previous subtask, dividing K and all class sizes by two, until either their sum is odd, or K is one.