CANTON - Count on Cantor
The link for the problem CANTON - Count on Cantor of Spoj is:
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/1The 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; }
No comments:
Post a comment