#PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester:Tester’s name
Editorialist:Editorialist’s name
DIFFICULTY : EASY
#PREREQUISITES : NIL
#PROBLEM :
Two players are playing a game. The game is played on a sequence of positive integer pairs.
The players make their moves alternatively.
During his move the player can choose a pair and decreases the larger integer in the pair by a positive multiple of the smallest integer in the pair in such a way that both integers in the pair remain positive after decreasing.
If two numbers in any pair become equal then that pair is removed from the sequence.
The player who can not make any move loses (or in another words the player who encounters an empty sequence loses).
Given the sequence of positive integer pairs determine whether the first player can win or not (assuming that both players are playing optimally).
#SOLUTION :
#include
using namespace std;
typedef long long LL;
int T,N;
LL X,Y;
int main(){
cin>>T;
while(T–){
cin>>N;
LL xr = 0;
while(N–){
cin>>X>>Y;
LL t1 = (XX-YY)/(X*Y);
if(t1<0) t1 = -t1;
xr ^=t1;
}
if(xr) cout<<“YES\n”;
else cout<<“NO\n”;
}
return 0;
}
EXPLANATION :
Example case 1. If the pair is (2,3)The first player don’t have any choice other than subtracting 2 from 3.
So during the turn of the second player integer pair will be (2,1). The second player will win by subtracting 1 from 2.
Example case 2. If the pair is (4,5).If the first player choose to move (4,5) to (4,1) the second player will make it to (1,1).So,second player wins.