Count on Cantor
Time limit1sMemory limit128 MB
For given indices n, find the n-th fraction a/b in Cantor's diagonal enumeration of positive rationals and print it in a fixed format.
- Level
Easy3 of 10
- Topics
- Math, Implementation, Simulation
- Solved
- No attempts yet
Problem
One of the famous results of modern mathematics is Georg Cantor's proof that the set of positive rational numbers is enumerable. The proof arranges the fractions (for positive integers and ) in the table below and enumerates them along its diagonals.
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
The fractions are read along successive anti-diagonals, alternating direction (each anti-diagonal collects the fractions whose numerator and denominator have the same sum). So the 1st term is 1/1, the 2nd is 1/2, the 3rd is 2/1, the 4th is 3/1, the 5th is 2/2, and so on.
Given a term index , output the corresponding fraction in Cantor's enumeration.
Input
The input contains one integer per line; each is a term index with . The list is terminated by end-of-file.
Output
For each input index , print one line in the form TERM n IS a/b, where a/b is the -th fraction of Cantor's enumeration. Print the results in the same order as the input, and do not print an extra blank line after the last one.