SPOJ Problem CANTON-Count on Cantor [Algorithm] [Java Implementation]

SPOJ Problem CANTON-Count on Cantor [Algorithm]                                     [ Java Implementation]

Problem link:-

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

Problem Statement:-

One of the famous proofs of modern mathematics is Georg Cantor's demonstration that the set of rational numbers is enumerable. The proof works by using an explicit enumeration of rational numbers as shown in the diagram below.

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

In the above diagram, the first term is 1/1, the second term is 1/2, the third term is 2/1, the fourth term is 3/1, the fifth term is 2/2, and so on.

Input

The input starts with a line containing a single integer t <= 20, the number of test cases. t test cases follow.

Then, it contains a single number per line.

Output

You are to write a program that will read a list of numbers in the range from 1 to 10^7 and will print for each number the corresponding term in Cantor's enumeration as given below.

Example

Input:

3

3

14

7

Output:

TERM 3 IS 2/1

TERM 14 IS 2/4

TERM 7 IS 1/4

Concept:-

1. First we find diagnal number.

2. Then we find the position of required number in that diagnal related to last element position in a diagnal.

Positions as:-

1 2 6  7  15 16...

3 5  8  14

4  9  13

10 12

11

Diagnal 1 contain positions:-1

Diagnal 2 contain positions:-2,3

Diagnal 3 contain positions:-4,5,6

Diagnal 4 contain positions :-7,8,9,10

Diagnal 5 contain positions:-11,12,13,14,15

As above details we can easily seen the pattern of Triangular Number and hence we can find the diagnal number from the formula:-

diag=sqrt(8*n+1)/2

Now we should taken care of number generated by formula to round off  as:-

Example

2.5 needs to be 2

2.2 needs to be 2

2.6 needs to be 3

We can easily formalised formula and get it by:-

(int)Math.ceil((Math.sqrt(8*n+1)-1)/2.0);

2. Now we know the diagnal no. and hence we can find the last position in diagnal(ie.in diagnal 3 is 6) by:-

endPoint =  ((diag *diag)+diag)/2;

Now we know last element position(i.e endPoint) and we can get the position in a diagnal of required number by calculating difference of required number and endPoint.

With the help of same pattern found in numerator and denomenator we can find the requires number. 

Consider even number diagnal and odd one separately and thus we can find the required number.(For more help see Program below).

Java Program:-

/**

 * @(#)CANTON.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2015/4/21

 */

import java.io.*;

class CANTON {

    public static void main(String args[])throws IOException{

   

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    int T=Integer.parseInt(br.readLine());

   

    while(T--!=0){

   

    int n=Integer.parseInt(br.readLine());

   

    int diag=findDiagnal(n);

    int endPoint=((diag*diag)+diag)/2;

    int dif;

    if(n>endPoint){

    dif=n-endPoint;

    }else{

    dif=endPoint-n;

    }

   

    if(diag%2==0){

    System.out.println("TERM "+n+" IS "+(diag-dif)+"/"+(1+dif));

    }else{

    System.out.println("TERM "+n+" IS "+(1+dif)+"/"+(diag-dif));

    }

   

   

    }

   

    }

    

    static int findDiagnal(int n){

    return (int)Math.ceil((Math.sqrt(8*n+1)-1)/2.0);

    }

    

}