My solution UVA 264 - Count on Cantor O(1) solution

264 - Count on Cantor

Time complexity: O(1)

The change of A[i] =
            1
        12321
    123454321
1234567654321

The label of A[i] =row r
row 1: 1,
row 2: 2,3,4,5,6,
row 3: 7,8,9,10,11,12,13,14,15,
row 4: 16,17,18,19,20,21,22,23,24,25,26,27,28,
row 5: 29,30,31,...45

The size of row r = 4r-3

The last item of row r:
row 1: 1
row 2: 6
row 3: 15
row 4: 28
row 5: 45
=sum(4r-3)=2r^2-r

The first item of row r:
row 1: 1
row 2: 2
row 3: 7
row 4: 16
row 5: 29
= 1+ last item of row (r-1) =2(r-1)^2-(r-1) +1 = s = 2r^2-5r+4

Given current position = N,
N>=2r^2-5r+4
2r^2-5r-(N-4)<=0

r<=(5+sqrt(25+8(N-4)))/4
r=(int)(5+sqrt(25+8(N-4)))/4

offset in row r : o = N-s
max value of row r : z=2*r-1;
We use offset and search/compute the value of A(N) in row r : A=z-abs(o-z+1); 

We can find out B in the similar way.

---------------------------- CODE ---------------------------
#include <iostream>
#include <cmath>


using namespace std;


int main(int argc, char *argv[])
{
    int N;
    int A,B;
    int r,t,s,o,z;
    while(cin>>N)
    {
        t=N-4;t=t<<3;        
        r=(int)(5.0+sqrt(25+t))>>2;
        s=(r*(r-2)<<1)-r+4;

        z=(r<<1)-1;
        o=N-s;
        A=z-abs(o-z+1);


        
        t=N-2;t=t<<3;
        r=(int)(3.0+sqrt(9+t))>>2;
        s=((r*(r-1))<<1)-r+2;
        z=r<<1;
        o=N-s;
        B=z-abs(o-z+1);
/*        
        cout<<"N="<<N<<" ";
        cout<<endl;
        cout<<"ra="<<ra<<" ";
        cout<<"sa="<<sa<<" ";
        cout<<"za="<<za<<" ";
        cout<<"oa="<<oa<<" ";
        cout<<endl;
        cout<<"rb="<<rb<<" ";
        cout<<"sb="<<sb<<" ";
        cout<<"zb="<<zb<<" ";
        cout<<"ob="<<ob<<" ";
        cout<<endl;
*/
        cout<<"TERM "<<N<<" IS "<<A<<"/"<<B<<endl;
    };


    return 0;
}