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;

  }

}

**Kitty and Katty

Kitty and Katty

Kitty and Katty have N$N$ plastic blocks. They label the blocks with sequential numbers from 1$1$to N$N$ and begin playing a game in turns, with Kitty always taking the first turn. The game's rules are as follows:

• For each turn, the player removes 2$2$ blocks, A$A$ and B$B$, from the set. They calculate A−B$A-B$, write the result on a new block, and insert the new block into the set.
• The game ends when only 1$1$ block is left. The winner is determined by the value written on the final block, X$X$:
  • If X%3=1$X\mathrm{\%}3=1$, then Kitty wins.
  • If X%3=2$X\mathrm{\%}3=2$, then Katty wins.
  • If X%3=0$X\mathrm{\%}3=0$, then the player who moved last wins.

Recall that %$\mathrm{\%}$ is the Modulo Operation.

Given the value of N$N$, can you find and print the name of the winner? Assume that both play optimally.

Note: The selection order for A$A$ and B$B$ matters, as sometimes A−B≠B−A$A-B\ne B-A$. The diagram below shows an initial set of blocks where N=5$N=5$. If A=2$A=2$ and B=3$B=3$, then the newly inserted block is labeled −1$-1$; alternatively, if A=3$A=3$ and B=2$B=2$, the newly inserted block is labeled 1$1$.

Input Format

The first line contains a single positive integer, T$T$ (the number of test cases or games). 
The T$T$ subsequent lines each contain an integer, N$N$ (the number of blocks for that test case).

Constraints

• 1≤T≤100$1\le T\le 100$
• 1≤N≤105$1\le N\le {10}^5$

Output Format

For each test case, print the name of the winner (i.e.: either Kitty or Katty) on a new line.

Sample Input

2
2
3

Sample Output

Kitty
Katty

Explanation

Test Case 0: 
N=2$N=2$ so there are two blocks labeled 1$1$ and 2$2$. Kitty chooses A=2$A=2$ and B=1$B=1$, then inserts a new block with the label 1$1$ (the result of 2−1$2-1$). The game ends, as there is now only 1$1$ block in the set. The label on the last block, X$X$, is 1$1$, so we calculate result=1 % 3=1$result=1\mathrm{\%}3=1$. Becauseresult=1$result=1$, Kitty wins and we print Kitty on a new line.

Test Case 1: 
N=3$N=3$, so there are three blocks labeled 1$1$, 2$2$, and 3$3$. No matter how Kitty makes the first move, Katty will win. If Kitty chooses A=3$A=3$ and B=2$B=2$ on the first move and inserts a block labeled 1$1$ (the result of 3−2$3-2$), the set of blocks becomes {1,1}$\{1,1\}$. Katty then must choose A=1$A=1$ and B=1$B=1$ and insert a new block labeled 0$0$ (the result of 1−1$1-1$). The game ends, as there is now only 1$1$ block in the set. The label on the last block, X$X$, is 0$0$, so we calculate result=0 % 3=0$result=0\mathrm{\%}3=0$. Because result=0$result=0$ and Katty made the last move, Katty wins and we print Katty on a new line.

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

Special Case

Let us first deal with the special case. When `N=1$N=1$`, there is only one element in the array, and nobody can make a move. Kitty wins since the remainder is `1$1$`.

Solution

For any arbitary `N>1$N>1$`, imagine the game is being played. Eventually, the game will come to a situation when there are exactly two elements in the array, `A$A$` and `B$B$`. Since the game is decided by the final value modulo `3$3$`, we can say that `a=A%3$a=A\mathrm{\%}3$` and `b=B%3$b=B\mathrm{\%}3$` and play with these two numbers instead. It will not affect the game state.

Now, if `a=b$a=b$`, then this player can simply replace `a,b$a,b$` with `a−b=0$a-b=0$`. The final value will be `0$0$`, and this player will win.

If they are not equal, then this player will still win. This player wins because she can choose the value of her move where either `1$1$` or `2$2$` is left as the final value.

Suppose `a=1$a=1$` and `b=2$b=2$`. If this player wants to have the final value as `1$1$`, then she will just choose `2$2$` and `1$1$` and replace them with `2−1=1$2-1=1$`. If she wants `2$2$`, then she will chose `1$1$` and `2$2$` and replace them with `1−2=−1$1-2=-1$`.

So, the player who makes the last move always wins. If `N$N$` is even, then Kitty wins, otherwise Katty wins.

-------------------------------------------------code--------------------------------------------

#include<bits/stdc++.h>

using namespace std;

int main(){

    int T;

    cin >> T;

    for(int a0 = 0; a0 < T; a0++){

        int n;

        cin >> n;

        if(n==1) cout<<"Kitty"<<endl;

        else if(n%2==0) cout<<"Kitty"<<endl;

        else cout<<"Katty"<<endl;

    }

    return 0;

}