# SPOJ CANTON

## Contents

## 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:

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