Grundy numbers

Grundy numbers define the best move we can play in any state, let's represent Grundy Number of any state as G(State_i)

• Recursively defined as G(State_i) = Mex{set of grundy numbers of all reachable states}, in our case G(i) = Mex{G(i-1), G(i-2)}
• G(0) = G(1) = 0 is the base case

MEX ?

let us say we have a set of S = {1, 2, 3, 4, 7}

What is Mex(minimum excludant) of S?

It is smallest non negative number not present in S, Mex(S) = 0

Here are other examples:

Mex{0, 1, 4, 6} = 2;   Mex{1, 2, 3, 4} = 0;    Mex{0, 1, 2, 3, 4......w_i} = w_i+1

Any state having grundy number 0 is a loosing state( try to wrap your head around this fact, it will soon get intuitive )

If Tintin starts with any state with a positive Grundy Number and play optimally Tintin wins, else he looses.

Here's an implementation of the above idea

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define FAST_CODE ios_base::sync_with_stdio(false); cin.tie(NULL);

constexpr ll MOD = 1000000007;

//to calculate Mex
ll Mex(unordered_set<ll>&S)
{
	ll Mex = 0;
	
	while (S.find (Mex) != S.end())
		Mex++;
	
	return (Mex);
}

//bottom up approach dp function to calulate grundy numbers
void nimber(ll n, vector<ll>&Grundy)
{

	Grundy[0] = 0; // base case
	Grundy[1] = 0; // base case

	for(ll i=2; i<=n; ++i)
	{
		unordered_set<ll> S;
		for(int j=2; j<=3; j++)
		{
			S.insert(Grundy[i-j]);	
		}

		Grundy[i] = Mex(S);
	}
}

int main()
{
	FAST_CODE
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r", stdin);
		freopen("output.txt","w", stdout);
	#endif

	ll nums;
	cin>>nums; //number of apples in the box

	vector<ll>Grundy(nums+1, -1); //Grundy numbers

	nimber(nums, Grundy);

	for(ll g:Grundy)
	{
		cout<<g<<" "; // printing the grundy number
	}
		
	return 0;
}