CareerCup

Let us define a function is_first_player_winner() which returns 1 if the first player can control the game and force a win. This function returns 0 if the first player cannot do so, and consequently the second player wins.

Now, we can think of a recursive solution. If we want to find out if the first player can force a win for a given value if "N", we can consider all possible combinations of the first two moves.

We can divide N by the product of the first two moves and then apply the same function recursively to check if player 1 can force a win (Optimal substructure).

Based on the answer of these sub-problems, we can check if player 1 can force a win or not.

// Recursive Solution

int is_first_player_winner (int n)
{
  /* Returns 1 if Player_1 can control and win the game
   Returns 0 if the Player_1 cannot control and win the game */

  if ( n <= 1 ) 
  {
    // should not reach here
    // exit
  }
  if (n > 2 && n <= 9)
    return 1;         // first player wins
  if (n > 9 && n <= 18) 
    return 0;         // first player cannot win
  
  /* Consider the first two moves in the game
   They can be one of the following: (2,2), (2,9), (9,2), (9,9) */
                                                                              // case 2,2              
  int win_2_2 = is_first_player_winner (ceil((float)n/4));

  // case 2,9 or 9,2 
  int win_2_9 = is_first_player_winner (ceil((float)n/18));

  // case 9,9
  int win_9_9 = is_first_player_winner (ceil((float)n/81));

  if ((win_2_2 && win_2_9) || (win_9_9 && win_2_9))
    return 1;
  else 
    return 0;
}

This comment has been deleted.

Is any player fixed for playing the first chance ?
suppose we could assume that P-1 always gets the first chance.

Is this question is about getting closer to N than the other player to win the game ?
please correct me if i am getting wrong interpretation of the question

#include<iostream>
using namespace std;
int playgame(int n,int turn,int x);
int main()
{
    int x=playgame(0,0,1); // first argument is n, second is player's turn(0 for first 1 for second) , third is starting no to each player(1)
    cout<<x;
    
    return 0;
    }
int playgame(int n,int turn,int x)
{
     if(x*2>=n &&  x*9>=n)
     return turn;
     
     
     int l=playgame(n,(turn+1)%2,x*2);
     int r=playgame(n,(turn+1)%2,x*9);
     return (l || r);
     
     }

if the n <= 9, the first player wins
if the 9 < n <= 18, the second player wins
if the 18 < n <= 36, the first player wins
if the 36 < n <= 72, the second player wins

conclusion :
find the least number a, when n <= 9 * 2^a, if a is even, the first player wins, if a is odd, the second player wins

input number is N, if there are n steps to finish this game,
the step n must multiply 9 to finish the game.
the step n-1 must multiply 2 to avoid to reach N/9 (when N/9 > 9, if N/9<9, game over).
the step n-2 must multiply 9 to reach the N/9/2 (when N/9/2 > 9, if N/9/2<9, game over).
...
finally, the remain number <=9, get the winner.

here is the code (not test)

boolean game(int N, int value, boolean flag)
{
if(N <= 9)
{
if(flag) return true;
return false;
}
else
{
int remain = (N%value == 0 ? N/value : N/value+1;
return game(remain, value == 9 ? 2 : 9, !flag);
}
}

// true : first win, false : second win
boolean game(int N)
{
return game(N, 9, true);
}

Solution: If player 1 can make one successful combination of moves which is not broken by either choice by player 2 then he wins else player 2 wins. Dynamic programming might be useful although I am not sure how as in dynamic programming we are usually incrementing towards solution here it is other way around.

#include<iostream>
#include<conio.h>
using namespace std;
bool playgameplayer2(float n);
bool playgameplayer1(float n)
{
if(n<=9) {
return true;
}


bool l=playgameplayer2(n/2);
bool r=playgameplayer2(n/9);
return (l || r);

}
bool playgameplayer2(float n)
{
if(n<=9) {
return false;
}

bool l=playgameplayer1(n/2);
bool r=playgameplayer1(n/9);
return (l && r);

}
int main()
{
float n;
cin>>n;
bool x=playgameplayer1(n); // first argument is n, second is player's turn(0 for first 1 for second) , third is starting no to each player(1)
cout<<x;
getch();
return 0;
}

#include<iostream>
#include<conio.h>
using namespace std;
bool playgameplayer2(float n);
bool playgameplayer1(float n)
{
     if(n<=9) {
             return true;
     }
     
     
     bool l=playgameplayer2(n/2);
     bool r=playgameplayer2(n/9);
     return (l || r);
     
}
bool playgameplayer2(float n)
{
     if(n<=9) {
             return false;
     }
     
     bool l=playgameplayer1(n/2);
     bool r=playgameplayer1(n/9);
     return (l && r);
     
}
int main()
{
    float n;
    cin>>n;
    bool x=playgameplayer1(n); // first argument is n, second is player's turn(0 for first 1 for second) , third is starting no to each player(1)
    cout<<x;
    getch();
    return 0;
}

I've put some of my earlier comments into a complete solution:

Let F(i, j) be true if the winner of the game is the player whose turn it is next when we start at 2^i*9^j, false otherwise.

Then, since we start at 2^0*9^0 = 1 and with the first player's turn being next, we can write:

boolean FirstPlayerIsWinner = F(0,0)

Now, F(i, j) is automatically true if 2^i * 9^j * 9 >= N. That is, if there is some number the player can multiply by and immediately win.

If that's not the case, F(i, j) is true if and only if either of F(i+1, j) and F(i, j+1) is false. Why? The number is currently 2^i*9^j. F(i,j) represents whether the current player will win starting from this number. If the current player multiplies by 2, it will be the other player's turn and the number will be 2^(i+1)*9^j. So F(i+1, j) will represent whether the opposing player (whose turn it now is) will win. The same logic applies for 9: F(i, j+1) will represent whether the opposing player will win.

So if F(i+1, j) and F(i, j+1) are both true, the current player loses: no matter what, the opposing player will win. However, if at least one is false, the current player would pick that move, causing the opposing player to lose and giving the current player the victory. Therefore, in this case, we can write: F(i, j) = not (F(i+1, j) and F(i, j+1))

So the overall formula now is:

boolean FirstPlayerIsWinner = F(0,0)

F(i, j) =
If 2^i * 9^j * 9 >= N then true
Else not (F(i+1, j) and F(i, j+1))

So that sets up basic recursion. We will need dynamic programming to help us evaluate this efficiently. This is just a matter of setting up simple memorization. With the constraints given, we can see that i< 32 and j < about 10, so a dynamic programming solution will be plenty fast.

This entire solution assumes that we don't have to deal with overflows, etc.

Ok, so I'm assuming that the number has to be perfectly divisible by 2 or 9 or a combination of these for someone to win (so prime numbers are out for e.g.), in which case I think it's just a case of how many multiples of these are factors of the number in question, and if P1 goes first, then he can only win if there's an odd number of multiples:

public class Game2_9 {

    public static void main(String[] args) {
        System.out.println(new Game2_9().winner(24234234));
        System.out.println(new Game2_9().winner(2*2*2*2*9*9*9*2));
        System.out.println(new Game2_9().winner(2*2*2*2*9*9*9*2*9*2*2));
        System.out.println(new Game2_9().winner(1));
    }

    public int winner(int N) {
        int goes = calcGoes(N);
        // for goes == 0, need to consider whether first player
        // has to pick between 2 or 9, or whether can decide not to pick because it's 1
        // i've assumed they have to pick, so nobody wins
        if (goes == -1 || goes ==0) {
            return 0;
        }
        if (goes%2==0) {
            return 2;
        }
        return 1;
    }


    private int calcGoes(int n) {
        if (n == 1) {
            return 0;
        }
        if (n%9==0) {
            int goes = calcGoes(n/9);
            return goes==-1?-1:goes+1;
        }
        if (n%2==0) {
            int goes = calcGoes(n/2);
            return goes==-1?-1:goes+1;
        }
        return -1;
    }
}

// turn = 0 player 1 wins
//turn = 1 player 2 wins
int Win(int N, int turn, int dice)
{
if(N == 0)
return turn
if(N < 0 )
return -1
else
{
Win(N - dice*2, !turn, dice+1);
Win(N - dice*9, !turn, dice+1);
}
}

Do let me know If I am making any mistake here

classic game-theory question, recursion would give the most concise solution..

def win( i, N ) :
    if( i*9 >= N ) : return True
    return not (win( i*2, N ) and win( i*9, N ))

this number N can only be represented as 2^k1*9^k2

if ((k1+k2)%2 == 1)
1 win
else
2 win

probably.... 0 for player 0, 1 for player 1, -1 for impossible cases like 13,17,19,..34,38..

int winner(int no)
{
        if (no<=0) return -1;
        if (no<=9) return 0;
        int i;
        for(i=2;i<=9;i++)
        {
                int j=winner(no/i);
                if(!(no%i) && j!=-1){if(j==0) return 1;else return 0; }
        }
        return -1;
}