Link to the question : HUBULLU

###

###

###
__HINT :__

Observe carefully. Try some simple cases by taking n a small number and then you will get the answer.

###
__SOURCE CODE :__

```
/* Hubulullu */
```

/* sushant gupta */

#include<iostream>

using namespace std;

int main()

{

int t,s;

long long int n;

cin>>t;

while(t--)

{

cin>>n>>s;

if(s==0)

cout<<"Airborne wins."<<endl;

else

cout<<"Pagfloyd wins."<<endl;

}

return 0;

}

Can you teach me i am not able to solve this .?

ReplyDeleteYou can try solving by hit and trial method. For example take the value of n=2, then the first player selects 2 and 1(divisor) and wins. Similarly if n=5, player-1 picks up 5 and 1. Then player-2 can either pick 3 or (4,2). In either case you will see that player-2 loses. Hence with this you can conclude that player_1 will always win.

DeleteElse you can solve it using game theory. It has got two states: winning and losing. For n=1, it can be clearly seen that player_1 is the winner. For n>1, let us assume player_1 to be the loser. Hence after player_1 plays his move, it will lead to a winning state. Take for eg. for n>1 , player_1 picks up 1, then player_2 picks up x. Since, we have assumed that player_2 is the winner, we can say that the move made by player_2 leads to losing state. But if player_1 picks up x in the first move, player_2 will be in the losing state.This is a contradiction. Hence the first player always wins.

This solution is wrong , since for 2 it will return -1, but in input test cases 2 is not present thats why it is getting accepted

ReplyDeleteNo where in the program -1 is returned.

DeleteSo basically no matter what is the value of n...the first player will always win?

ReplyDelete