This problem has 3 parts, each posed as a separate problem in the contest.
However the only difference between them is the value of MAX_SIZE.

Consider a two-player game in which players alternate turns. A position in the game is given by a collection of heaps of stones.

Each heap contains a positive numbers of stones.
The allowed move each turn is to choose a heap having AT LEAST 2 stones, and to remove an allowed number of stones from it.
The allowed numbers are 1,5,14,15,16.
That is, in a move, a player chooses exactly one heap of stones. Then either subtracts 1 stone,
or subtracts 5 stones, or subtracts 14 stones, or subtracts 15 stones, or subtracts 16 stones from the chosen heap.

Of course, it is not allowed to subtract more stones than a heap contains, but it is allowed to empty a heap completely by subtracting all of its stones.
Note however that even though subtracting 1 is generally allowed, it is never allowed to subtract stones from a heap of only 1 stone.

The rules of the game dictate that when a player CANNOT move, they WIN immediately.

Your task is to be able to efficiently compute whether a position is winning or not, for any possible initial position.
That is, whether the first player has a winning strategy.

For example the 3-heaps position "1 5 4" is winning: the first player can delete all 5 from the heap of 5, and then the only remaining legal moves are 4 -> 3 -> 2 -> 1 in the heap of 4 stones, so the first player will run out of moves.
"1 4 3" is losing on the other hand: there will always be exactly 5 moves of the type "subtract 1 stone" in this particular case until the game ends, no matter what is chosen, and thus the second player will be the one to run out of moves in this case, so they will win.

A lot of test cases will be generated by the following generator, which calls the winning function that you should implement.
This function takes an array describing how many heaps of each possible size there are. It should return true when the position is winning, and false when it is losing.
Allowed heap sizes are from 1 up to MAX_SIZE, which is 68 in this problem. The total number
of heaps can be quite large in some cases as can be checked from inspecting the generator.

The final answer is the md5sum of this generator's output (once the winning function is correctly implemented).

So for example if you save the generator file as solver.cpp, the following command produces the desired md5sum:

g++ --std=gnu++14 -O2 -o solver solver.cpp; ./solver | md5sum








#include <iostream>
#include <cassert>

using namespace std;

const int MAX_SIZE = 68; // THE ONLY DIFFERENCE AMONG THE THREE PARTS OF THIS PROBLEM IS THIS VALUE

// heaps points to an array of size MAX_SIZE+1
// heaps[i] is the number of heaps of size i
// Note that the function must not modify
// the heaps array at all
// heaps[0] == 0 is guaranteed to hold
bool winner(const int *heaps)
{
    // YOUR MAIN TASK IS TO CORRECTLY IMPLEMENT THIS FUNCTION
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    assert(67 <= MAX_SIZE && MAX_SIZE <= 69);
    cerr << "Running generator's quick first phase" << endl;
    static int heaps[70];
    for (int i=0;i<70;i++)
        heaps[i] = 0;
    winner(heaps);
    for (heaps[68] = 0; heaps[68] <= 5 * (MAX_SIZE >= 68); heaps[68]++)
    for (heaps[69] = 0; heaps[69] <= 5 * (MAX_SIZE >= 69); heaps[69]++)
    for (int i=1;i<=67;i++)
    {
        heaps[i]++;
        cout << winner(heaps);
        for (int j=1;j<=i;j++)
        {
            heaps[j]++;
            cout << winner(heaps);
            for (int k=1;k<=j;k++)
            {
                heaps[k]++;
                cout << winner(heaps);
                for (int l=1;l<=k;l++)
                {
                    heaps[l]++;
                    cout << winner(heaps);
                    for (int m=1;m<=l;m++)
                    {
                        heaps[m]++;
                        cout << winner(heaps);
                        heaps[m]--;
                    }
                    heaps[l]--;
                }
                heaps[k]--;
            }
            heaps[j]--;
        }
        heaps[i]--;
    }
    heaps[68] = 0;
    heaps[69] = 0;
    
    const int A = 37;
    const int B = 41;
    const int C = 67;
    const int MOD = 1000000007;
    
    long long X = 1002;
    
    int TOTAL_ITERS = 1;
    if (MAX_SIZE >= 68)
        TOTAL_ITERS *= 6;
    if (MAX_SIZE >= 69)
        TOTAL_ITERS *= 6;
    
    cerr << "Main generation started" << endl;
    
    bool lastStep = false;
    int itersDone = 0;
    for (int heaps68 = 0; heaps68 <= 5 * (MAX_SIZE >= 68); heaps68++)
    for (int heaps69 = 0; heaps69 <= 5 * (MAX_SIZE >= 69); heaps69++)
    {
        lastStep = heaps68 == 5 * (MAX_SIZE >= 68) &&
                   heaps69 == 5 * (MAX_SIZE >= 69);
        for (int iterations = 0; iterations < 200000; iterations++)
        {
            for (int N : {6,7,8,9,10,15,22,30,60,100,1000, 10000, 1000000, 2000000, 5000000})
            {
                if (N > 10000 && iterations % 100000 != 0)
                    continue;
                for (int i=0;i<70;i++)
                    heaps[i] = 0;
                if (MAX_SIZE >= 69 && lastStep)
                {
                    for (int c = 0; c < N; c++)
                    {
                        heaps[1 + (X%69)]++;
                        long long nextX = (A*X+B)%MOD;
                        X = (nextX * X + C)%MOD;
                    }
                } else if (MAX_SIZE >= 68 && lastStep)
                {
                    for (int c = 0; c < N; c++)
                    {
                        heaps[1 + (X%68)]++;
                        long long nextX = (A*X+B)%MOD;
                        X = (nextX * X + C)%MOD;
                    }
                }
                else
                {
                    heaps[68] = heaps68;
                    heaps[69] = heaps69;
                    for (int c = 0; c < N; c++)
                    {
                        heaps[1 + (X%67)]++;
                        long long nextX = (A*X+B)%MOD;
                        X = (nextX * X + C)%MOD;
                    }
                }
                cout << winner(heaps);
            }
            // PROGRESS INDICATOR OF THE LONGEST PART, USE IF YOU WANT
            if (iterations % (2000 * TOTAL_ITERS) == 0)
            {
                cerr << (itersDone * 100 + (iterations / 2000)) / TOTAL_ITERS << "%" << endl;
            }
        }
        itersDone++;
        if (lastStep)
            break;
    }
    cout << "\n";
    return 0;
}