CANTON - Count on Cantor Editorial or Solution Spoj - UCS

CANTON - Count on Cantor

The link for the problem  CANTON - Count on Cantor of Spoj is:

http://www.spoj.com/problems/CANTON/

Logic :

The series goes as 

1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1

The series will go as following steps:
1) First, add numerator and denominator of series in order we get a series like:

2 3 3 4 4 4 5  5 5 5 6 6  6 6 6.

From this, we can deduce that nth value sum appears (n-1) times in series.

Suppose we want 7th term so we can proceed as

1+2+3=6 , let 6 would be stored in r,which is less than 7th term so our 6th term will contain (3+1) i.e., 4 so now we must calculate from 7 to 9th term with value equal to (4+1 =5)i.e., value =5 here

so if value =5 is odd then we must start with numerator =1 and denominator = value - 1

so for every step increment numarator by 1 and decrement denominator by 1 until we reach our nth term.
So finally print it.
Incase our value is even then take numerator = value -1 and denominator = value +2

And follow the same step as before up to nth term.

The following is C++ Solution for the problem CANTON - Count on Cantor of Spoj

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int t;
    long long int n,ans,i,j;
    cin>>t;
    for(int ii=0;ii<t;ii++)
    {
        cin>>n;
        long long  r=0;
        i=1;
        while(r<n)
        {
         r+=i;
         i++;
        }
        i--;
        r-=i;
        i++;
        long long num,den;
        if(i%2==1)
        {
            num=1;
            den=i-1;
            for(j=r+1;j<n;j++)
         {
            num++;
             den--;
         }
         }
         else
        {
            num=i-1;
         den=1;
           for(j=r+1;j<n;j++)
         {
             num--;
             den++;
         }
       }
        cout<<"TERM "<<n<<" IS ";
       cout<<num<<"/"<<den<<endl;
}
return 0;
} 

Note: Be careful while printing output as given in problem otherwise it will give wrong answer.

Happy Coding ....
Feel Free to make comments for queries