## 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 *Apples _{i}* as a state with i apples, tintin can remove 2 or 3 apples,

*Apples*and/or

_{i-2}*Apples*should be at loosing states or tintin will forfeit, we also know

_{i-3}*Apples*,

_{0}*Apples*will be a loosing states since nothing can be removed from the pile by the player and

_{1}*Apples*and

_{2}*Apples*will be winning state since player can simply remove 2 or 3 apples to reach

_{3}*Apples*(the loosing state)

_{0}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

```
#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;
int main()
{
FAST_CODE
#ifndef ONLINE_JUDGE
freopen("input.txt","r", stdin);
freopen("output.txt","w", stdout);
#endif
ll n;
cin>>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;
}
else
{
Apples[i] = 0;
}
}
for(ll u:Apples)
{
cout<<u<<" ";
}
cout<<"\n";
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.....