Algorithm
Problem link- https://www.spoj.com/problems/HUBULLU/
HUBULLU - Hubulullu
After duelling in quake (a multiplayer game), Airborne and Pagfloyd decide do test themselves out in another game called Hubulullu. The rules of the game are as follows:
N wooden pieces (marked with numbers 1 to N) are placed in a transparent bottle. On his turn the first player takes out some piece (numbered x) and all the pieces numbered by divisors of x that are present in the transparent bottle. The second player picks another number and removes it and its divisors as well. Play continues in an alternating fashion until all pieces have been removed from the bottle. The player who removes the last piece from the bottle wins the game.
Both players play optimally. Given N (the number of wooden pieces in the transparent bottle initially) and the name of the player who starts the game, determine the winner.
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
Each test case consists of a single line containing two integers separated by a single space. The first integer is N (1 <= N <= 2000000000), indicating the number of pieces, and the second integer indicates the player who starts - "0" means Airborne starts the game and "1" means Pagfloyd starts the game (quotes for clarity).
Output
For each test case output one line containing either "Airborne wins." or "Pagfloyd wins."
For each N, it's possible to determine a winner if both players play optimally.
Example
Input: 1 1 0 Output: Airborne wins.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
using namespace std;
int main(){
int t=0;
cin>>t;
while(t--){
long long int n=0;
int p;
cin>>n>>p;
if(p==0)cout<<"Airborne wins."<<endl;
else cout<<"Pagfloyd wins."<<endl;
}
}Input
1 0
Output
#2 Code Example with Java Programming
Code -
Java Programming
#include<bits/stdc++.h>
using namespace std;
//The intuition behind this problem is
//That player can be at losing state or winning state
//at start. If he is at losing state then he can simple
//choose 1 at start as it will not effect the list and can
//Pass his losing state to second player.so he will win
//So no matter what number is whatever player will play first
//will always win.
int main() {
//Number of test cases
int t;
cin>>t;
//Loop over all test cases
while(t--) {
//Take number and who will start first
int n,s;
cin>>n>>s;
//print answer according to who is playing first
if(s == 0) {
cout<<"Airborne wins."<<endl;
} else {
cout<<"Pagfloyd wins."<<endl;
}
}
return 0;
}Input
1 0
Output
Demonstration
SPOJ Solution HUBULLU Hubulullu- Solution in C, C++, Java, Python,HUBULLU,SPOJ Solution