 # WA in Matches

After taking n%m, n will be smaller than m…, But the method is wrong either ways .
We need the First rule of game theory.
If there are two players playing a turn based game, uninfluenced by nature(no randomness), There is one player who can force a tie or a win. Since there are no ties, one player is sure to win always.
If we use this we can deduce that if 2m\leq n or vice versa, player 1 is sure to win.
Let’s say the state (n,m) is a losing state if the player who has their turn on this state will lose, and vice versa. Now, if n>2m we can force the other player to have the state (n\%m,m) if it is a losing state by going to (n\%m + m,m), where there only choice would be (n\%m,m), Or if it is a winning state, we can go there directly ourselves. Now if n<2m, our only option would be (n-m,m), and the answer will be the opposite of this answer. Also, if we get n=m, we know player 1 will win. If one of them is a 0, then we know player 2 has won already. Using these relations, we can use recursion to get to our answer.

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
ll solve(ll n,ll m){
if(m>n){
ll c=n;
n=m;
m=c;
}
if(m==0){
return 0;
}
if(n>=m*2){
return 1;
}
if(n==m){
return 1;
}
else{
return (solve(n-m,m)+1)%2;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--){
ll n,m;
cin>>n>>m;
if(solve(n,m)==1){
cout<<"Ari";
}
else{
cout<<"Rich";
}
cout<<'\n';
}
}

1 Like

Your explanation corrected my understanding of the problem. Thank you.