1.

package sem2.am.franzcantor;

/**
* Angewandte Mathematik, SS11
* Problem: 880 und 264 Cantor Problems
* Link: 264 http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=200&mosmsg=Submission+received+with+ID+8351132
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=10&problem=821&mosmsg=Submission+received+with+ID+8351360
*
* @author Sommer, Franz
* @author Stein, Florian
* @version alpha stage
*
* Method : Calculation , BigDecimal, Newton Approximation / Heron of Alexandria
* Status : Time Limit Exceeded, (didn't see the input limitation to integer)
* Runtime: 3+
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;

public class Main {

public static void main(String... args) throws IOException {
int PROBLEM = 880;// Control to use for 880 or 264

BufferedReader inputReader = new BufferedReader(new InputStreamReader(
System.in));
String line = inputReader.readLine();
String[] splitLine;

while (line != null) {
splitLine = line.split(" ");

BigInteger N = new BigInteger(Integer.toString(Integer
.parseInt(splitLine[0])));

BigInteger sqrtterm = (N.multiply(new BigInteger("8")))
.add(new BigInteger("1"));
BigDecimal sqrt = BigSquareRoot.get(sqrtterm).subtract(
new BigDecimal("3"));
BigDecimal K = sqrt;

K = K.divide(new BigDecimal("2"), 0, BigDecimal.ROUND_CEILING);
BigInteger KINT = K.toBigInteger();

BigInteger M = N.subtract(KINT.add(BigInteger.ONE).multiply(KINT)
.divide(new BigInteger("2")));

// TODO needs little adjustments in
// Output: a/b or b/a or ... Term N Is A/B or ... Term N Is A/B
String a = M.toString();
String b = ((K.toBigInteger().add(new BigInteger("2"))).subtract(M))
.toString();

// K+1 gerade oder ungerade Check if Problem 889

if (PROBLEM == 880) {
if (K.toBigInteger().mod(new BigInteger("2")) == BigInteger.ZERO
|| K.toBigInteger() != new BigInteger("2")) {
System.out.println(b + "/" + a);
} else {
System.out.println(a + "/" + b);
}
} else {
if (K.toBigInteger().mod(new BigInteger("2")) == BigInteger.ZERO) {
System.out.println("TERM" + N.toString() + " IS " + a + "/"
+ b);
} else {
System.out.println("TERM" + N.toString() + " IS " + b + "/"
+ a);
}
}
line = inputReader.readLine();
} // end of while
}
}


package sem2.am.franzcantor;

import java.math.BigDecimal;
import java.math.BigInteger;

/**
* See http://www.merriampark.com/bigsqrt.htm
*/
class BigSquareRoot {

private static BigDecimal ZERO = new BigDecimal("0");
private static BigDecimal ONE = new BigDecimal("1");
private static BigDecimal TWO = new BigDecimal("2");
public static final int DEFAULT_MAX_ITERATIONS = 15;
public static final int DEFAULT_SCALE = 5;

private static BigDecimal error;
private static int iterations;
private static boolean traceFlag;
private static int scale = DEFAULT_SCALE;
private static int maxIterations = DEFAULT_MAX_ITERATIONS;

// ---------------------------------------
// The error is the original number minus
// (sqrt * sqrt). If the original number
// was a perfect square, the error is 0.
// ---------------------------------------

public BigDecimal getError() {
return error;
}

// -------------------------------------------------------------
// Number of iterations performed when square root was computed
// -------------------------------------------------------------

public int getIterations() {
return iterations;
}

// -----------
// Trace flag
// -----------

public boolean getTraceFlag() {
return traceFlag;
}

public void setTraceFlag(boolean flag) {
traceFlag = flag;
}

// ------
// Scale
// ------

public int getScale() {
return scale;
}

public void setScale(int scale) {
this.scale = scale;
}

// -------------------
// Maximum iterations
// -------------------

public int getMaxIterations() {
return maxIterations;
}

public void setMaxIterations(int maxIterations) {
this.maxIterations = maxIterations;
}

// --------------------------
// Get initial approximation
// --------------------------

private static BigDecimal getInitialApproximation(BigDecimal N) {
BigInteger integerPart = N.toBigInteger();
int length = integerPart.toString().length();
if ((length % 2) == 0) {
length--;
}
length /= 2;
BigDecimal guess = ONE.movePointRight(length);
return guess;
}

// ----------------
// Get square root
// ----------------

public static BigDecimal get(BigInteger n) {
return get(new BigDecimal(n));
}

public static BigDecimal get(BigDecimal n) {

// Make sure n is a positive number

if (n.compareTo(ZERO) <= 0) {
throw new IllegalArgumentException();
}

BigDecimal initialGuess = getInitialApproximation(n);
trace("Initial guess " + initialGuess.toString());
BigDecimal lastGuess = ZERO;
BigDecimal guess = new BigDecimal(initialGuess.toString());

// Iterate

iterations = 0;
boolean more = true;
while (more) {
lastGuess = guess;
guess = n.divide(guess, scale, BigDecimal.ROUND_HALF_UP);
guess = guess.add(lastGuess);
guess = guess.divide(TWO, scale, BigDecimal.ROUND_HALF_UP);
trace("Next guess " + guess.toString());
error = n.subtract(guess.multiply(guess));
if (++iterations >= maxIterations) {
more = false;
} else if (lastGuess.equals(guess)) {
more = error.abs().compareTo(ONE) >= 0;
}
}
return guess;

}

// ------
// Trace
// ------

private static void trace(String s) {
if (traceFlag) {
System.out.println(s);
}
}

// ----------------------
// Get random BigInteger
// ----------------------

public static BigInteger getRandomBigInteger(int nDigits) {
StringBuffer sb = new StringBuffer();
java.util.Random r = new java.util.Random();
for (int i = 0; i < nDigits; i++) {
sb.append(r.nextInt(10));
}
return new BigInteger(sb.toString());

}
}
-------------------------------------------

1.

package problemSetVolumes.volume002;

import java.util.Scanner;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 264 - Count on Cantor
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=200&mosmsg=Submission+received+with+ID+8351132
*
* @author Siegfried Ippisch
* @version 1.0
*
* Method : -
* Status : Accepted
* Runtime: 0.676
*/
public class CountOnCantor {

public static short[] cNum;
public static short[] cDen;

private static void init(int max) {
cNum = new short[max];
cDen = new short[max];

short num = 1;
short den = 1;
int l = 1;
int j = 1;

for(int i=1; i<max; i++){
cNum[i] = num;
cDen[i] = den;

if(j == l){
j = 0;
l++;
if(num > den)
num++;
else
den++;
} else{
if(l%2 == 1){
num--;
den++;
} else{
num++;
den--;
}
}
j++;
}
}

public static void main(String[] args){
init(10000001);
Scanner in = new Scanner(System.in);

while(in.hasNext()){
int n = in.nextInt();
System.out.printf("TERM %d IS %d/%d%n",n,cNum[n],cDen[n]);
}

in.close();
}

}

2.

/*
* ACM Contest training
* Problem: 264 - Count on Cantor
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=200
*
* @author Christoph Goettschkes
* @version 1.0, 10/27/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.564
*/

import java.util.*;
import java.io.*;

class Main
{

static Map<Long, Long> test = new HashMap<Long, Long>();

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

long col = 1;
long adder = 4;
int base_adder = 4;
long n = 1;

while (n < 10006102) {
test.put(n, col);
col += 1;
n += 1;
test.put(n, col);
col += 1;
n += adder;
adder += base_adder;
}

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
n = Long.parseLong(reader.readLine().trim());

while (true)
{
long nextColNumber = nextCol(n);
long columnNumber = test.get(nextColNumber);

if (nextColNumber == n)
System.out.printf("TERM %d IS %d/%d%n", n, 1, test.get(n));
else {
if (nextColNumber - columnNumber + 1 <= n) {
long s = nextColNumber - n;
System.out.printf("TERM %d IS %d/%d%n", n, s+1, columnNumber - s);
} else {
nextColNumber = nextColNumber - ((columnNumber - 1)*2);
columnNumber--;
long a = n - nextColNumber;
System.out.printf("TERM %d IS %d/%d%n", n, a+1, columnNumber-a);
}
}


if (!reader.ready())
break;
n = Long.parseLong(reader.readLine().trim());

}
}

static long nextCol(long n) {
long next = 1;
long col = 1;

while (next < n) {
//System.out.printf("Col: %d / next: %d%n", col, next);
if (col % 2 == 1)
next += 1;
else
next += (col*2);
col++;
}
return next;
}
}