Mojo, Jojo and Game

Mojo, Jojo and Game
After solving some programming problems, Mojo and Jojo want to take some time off and play some game. They ask Rhezo what to play. Rhezo tells them about a game with the following rules:
There are $N$ stacks of coins, each containing $X$ coins. Both players take turns, with Mojo moving first. The only allowed moves are the following:

1. Remove any stack of coin.
2. Remove any $2$ stacks.
3. Remove $X/2$ coins from each stack if $X$ is even, or remove $(X+1)/2$ coins from each pile, if $X$ is odd.

The game finishes when there are no more coins left in any stack. The last person to make the move wins. Both, Mojo and Jojo play optimally and want to win. Can you tell who will win this game?
Input:
First line of the input contains an integer $T$, denoting the number of test cases you have to handle.
Each test case consists of two integers, $N$ and $X$, separated by a single space.
Output:
For each test case, if Mojo wins, print "Mojo", else print "Jojo" (quotes only for clarity).
Constraints:

• $1\le T\le {10}^3$
• $1\le N\le {10}^3$
• $1\le X\le {10}^9$

SAMPLE INPUT

1
4 5

SAMPLE OUTPUT

Jojo

Explanation

One possible flow of the game is as follows:

$\bullet$ There are $4$ stacks with $5$ coins each, Mojo removes $2$ stacks.

$\bullet$ There are $2$ stacks left now with $5$ coins each, Jojo removes $2$ stacks, and wins.

We can show that for any possible flow of the game, Jojo will always win.

--------------------------------------------------editorial-----------------------------------------------------------------------------

 this problem is all about  state optimization ...

Let us have a function $isWinning(N,X)$ that tells us if the current state is winning or not if there are $N$ stacks left and each stack has $X$ coins.

One important observation is that there are only a very small number of distinct values that all stacks can take for a particular starting $X$. This small number is upper bounded by $log2\left(X\right)$. Let us keep all these distinct values in an array $A$.

let value  of X is 16 than instead of 16 use it as 4 ans each time instead of dividing x by 2 decreasing value of x  by 1 

Let us redefine the state $(N,X)$ as $(N,P)$, where $P$ denotes the the index of different values that we can obtain from $X$in array $A$.

Then we can easily write a DP solution. A state is winning, if we can go to at least one state that is losing. A state is losing, if we can only go to winning states from it.

The base conditions are as follows: if $N$ is $0$ or $P$ is not a valid index, then it is a losing state.

Refer to the author's solution for a proper implementation of the $isWinning$ function.

======================================code============================================

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

#define ff first

#define ss second

#define mp make_pair

#define pb push_back

#define mod 1000000007

bool dp[100][1010];

bool used[100][1010];

bool solve(int height,int n)

{

// cout<<height<<" "<<n<<endl;

 if(height==0) return false;

 else if(n==0) return false;

 else if(used[height][n]) return dp[height][n];

 else

 {

  used[height][n]=true;

  bool ans=false;

   ans= ans| (!solve(height-1,n));

    ans= ans| (!solve(height,n-1));

     if(n>=2)

     ans= ans| (!solve(height,n-2));

     dp[height][n]=ans;

     return ans;

 }

}

int main()

{

 int t;

  cin>>t;

  while(t--)

  {

      memset(dp,false,sizeof dp);

   memset(used,false,sizeof used);

    int n,x;

     cin>>n>>x;

     int height=0;

     while(x!=0)

       {

       if(x&1) x=x-(x+1)/2;

else x/=2;

height++;

 }

// cout<<"height is "<<height<<endl;

 

bool ans=solve(height,n);

if(ans) cout<<"Mojo"<<endl;

else cout<<"Jojo"<<endl;

  }

}