Cook off Jan 2014 - Subtraction Game

general
, , ,
1

the question for the solution below is -

Now…

The following code is working fine for the test cases but giving wrong answer on submission.
What is the mistake that i am doing?
Is my method wrong for the question?

#include<iostream>
#include<stdio.h>
using namespace std;
int func(long long int a,long long int b)
{
    int freq=0;
    if(a<b)
        swap(a,b);
    if(a%b==0)
        freq++;
    else
    {
        freq++;
        freq+=func(b,a%b);
    }
    return freq;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long int a,b;
        int arr[n];
        int sum=0;
        for(int i=0;i<n;i++)
        {
            cin>>a;
            cin>>b;
            arr[i]=func(a,b);
            sum+=arr[i];
        }
        if(sum%2!=0)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
}
2

Your approach is incorrect. Here is a test case that will fail your code.

1
1
4 10

Your code gives an answer of NO but the answer is YES for this case.
The first player will move from (4, 10) to (4,6). The second player can only move to (4,2) from this position. Now the first player will move to (2,2) and hence winning the game.

Go through the editorial of this problem available at http://discuss.codechef.com/questions/37284/gameaam-editorial