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