Thursday 6 August 2015

HUBULLU

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;
}

5 comments:

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

    ReplyDelete
    Replies
    1. You 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.

      Else 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.

      Delete
  2. 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

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

    ReplyDelete