DP to the rescue!


Some light on the problem:

So ofcourse the value of 'n' will decide the winning and loosing state of the starting player, at every turn we have to remove 2-3 apples, the optimal strategy for both players is that if the player is at a winning state he has to make sure the other player in his turn is always at loosing state, so the question is how do we find a state is winning or loosing

let us define Applesi  as a state with i apples, tintin can remove 2 or 3 apples, Apples i-2 and/or Applesi-3 should be at loosing states or tintin will forfeit, we also know Apples0, Apples1 will be a loosing states since nothing can be removed from the pile by the player and Apples2 and Apples3 will be winning state since player can simply remove 2 or 3 apples to reach Apples0 (the loosing state)

understand that, one winning state leads to atleast 1 loosing state, but one loosing state can lead to only winning states

Dynamic Programming

we can use a very simple bottom-up dynamic programming approach, to come up with a simple program to determine the state of the game

using namespace std;
typedef long long ll;
# define FAST_CODE ios_base::sync_with_stdio(false); cin.tie(NULL);

constexpr ll MOD = 1000000007;

int main()
		freopen("input.txt","r", stdin);
		freopen("output.txt","w", stdout);

	ll n;
	vector<int>Apples(n+1, 0);

	//winning states
	Apples[2] = 1;
	Apples[3] = 1;

	//loosing states
	Apples[0] = 0;
	Apples[1] = 0;

	for(ll i=4; i<=n; ++i)
		if((Apples[i-2] * Apples[i-3]) == 0)
			Apples[i] = 1;

			Apples[i] = 0;

	for(ll u:Apples)
		cout<<u<<" ";

	return 0;

So if the box had 20 apples, then it's a loosing state, Tintin definitely shouldn't go first !

Btw did you notice the pattern ?

0 0 1 1 1 0 0 1 1 1 0 0 1 1 1.....


Be the first one to comment!