SPOJ CANTON

From Algorithmist
Jump to navigation Jump to search

302 (CANTON) - Count On Cantor[edit]

Summary[edit]

Given a number n, find it's corresponding term in Cantor's enumeration.

Explanation[edit]

This problem breaks down into two steps:

  • 1) Find the diagonal for the given number.
  • 2) Find the value of the endpoint of the found diagonal.

    The first part is relatively straightforward. The length of each diagonal grows in a Triangular Series, therefore; where is the given number and is the diagonal. Next, the endpoint of the diagonal is given by; . Now, the difference from the given number and the endpoint can be found. Counting this difference from the lower left for odd numbered diagonals or the upper right for even numbered diagonals will yield the required term.

    Implementation[edit]

    Care must be taken with the integer division rounding. A function that takes this into account might look like this:

    int FindDiagonal(int n)
    {
    	return (sqrt(8*n+1))/2;
    }
    

    Input[edit]

    The first line contains the number of test cases . The next T lines each contain a number for which to find the associated term.

    5
    3
    14
    7
    10000000
    25
    

    Output[edit]

    Note that the extra verbiage is required.

    TERM 3 IS 2/1
    TERM 14 IS 2/4
    TERM 7 IS 1/4
    TERM 10000000 IS 2844/1629
    TERM 25 IS 4/4
    

    External Links[edit]

    Triangular Number - Wiki Link