1.
/**
* ACM Programming Contest WS 10/11 "100 - 3n+1"
* Accepted Run Time 0.640
* @author Patrick Bédat, IF3A Okt. 2010
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main
{
private static Map<Integer,Integer> cycleLengthCache = new HashMap<Integer,Integer>();
public static void main(String... args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String inputLine = reader.readLine();
while (inputLine != null)
{
StringTokenizer st = new StringTokenizer(inputLine);
int x = new Integer(st.nextToken());
int y = new Integer(st.nextToken());
int lower = Math.min(x, y);
int upper = Math.max(x, y);
int maxCycleLength = findMaximumCycleLengthBetween(lower, upper);
System.out.printf(String.format("%s %s %s%n", x, y, maxCycleLength));
inputLine = reader.readLine();
}
}
private static int findMaximumCycleLengthBetween(int lower, int upper)
{
int max = 0;
for (int i = lower; i <= upper; i++)
{
int cycleLength = computeCycleLength(i);
if (max < cycleLength)
max = cycleLength;
}
return max;
}
private static int computeCycleLength(int seed)
{
int cycleLength = 1;
int n = seed;
if(cycleLengthCache.containsKey(seed))
return cycleLengthCache.get(seed);
while (n != 1)
{
if (n % 2 == 0)
n = n / 2;
else
n = 3 * n + 1;
cycleLength++;
}
cycleLengthCache.put(seed,cycleLength);
return cycleLength;
}
}
2.
/*
* ACM Contest training
* Problem: 100 The 3n + 1 problem
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36
*
* @author Christoph Göttschkes
* @version 1.0, 10/19/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.648
*/
import java.util.*;
import java.io.*;
class Main
{
public static Map<Long, Long> colMap = new HashMap<Long, Long>();
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = reader.readLine();
while (true)
{
if (line == null || line.isEmpty())
break;
StringTokenizer tokenizer = new StringTokenizer(line);
int first = Integer.parseInt(tokenizer.nextToken());
int second = Integer.parseInt(tokenizer.nextToken());
int i = first;
int j = second;
if (i > j)
{
i = second;
j = first;
}
if (i < 1 || j < 1 || i >= 1000000 || j >= 1000000)
continue;
long longest = 0;
for (int k = i; k <= j; k++)
{
long cur = cycle(k);
if (cur > longest)
longest = cur;
}
System.out.println(first + " " + second + " " + longest);
if (!reader.ready())
break;
line = reader.readLine();
}
}
public static long cycle(long n)
{
if (colMap.containsKey(n))
return colMap.get(n);
long counter = 0;
long test = n;
while (n > 1)
{
n = nextFib(n);
if (colMap.containsKey(n))
{
counter += colMap.get(n);
n = -1;
}
else
counter++;
}
counter++;
colMap.put(test, counter);
return counter;
}
public static long nextFib(long n)
{
if (n % 2 == 0)
return n / 2;
return 3 * n + 1;
}
}
3. JAVA, Gunnar Hage
/**
* ACM programming Contest WS 08/09 "100 - 3n+1"
* Accepted Run Time 0.480
* @author Gunnar Hage, AP5(IFB5A) Okt. 2008
*
* Die Aufgabe ist bekannt.
* Meine Lösung nutzt ein Integerarray, wobei ich für jede Zahl die Anzahl der Iterationen gespeichert wird.
* So kann ich bei, wenn Zwischenergebnisse der Rechnung kleiner sind als die zu Berechnende Zahl direkt auf den bereits bekannten
* Wert im Array die bis dorthin benötigte Anzahl der Iterationsschritte addieren. (while(n>=i)). Dieses Vorgehen verkürzt die Laufzeit.
* Für alle gerade Zahlen wird so nur ein Itrationsschrit benötigt.
*/
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
int count, maxCount = 0, start, end, lowerParam, higherParam;
double n=0, i=0; //Double Aritmetik weil int für die Berechnung der Nachfolger von einigen großen Zahlen nicht ausreicht. BSPL: 113383 evtl. auf float ändern.
int[] oneMillion = new int[1000001];
String line ="";
StringTokenizer idata;
//Berechnung der Iterationsschrittzahl für alle Zahlen von 2 bis 1000000.
oneMillion[1] = 1;
for(i=2; i<oneMillion.length;i++)
{
n = i;
count = 0;
//hier die besonderheit die den Algorithmus recht schnell macht.
while(n >= i){
n = (n%2==0)? n/2 : 3*n+1;
count++;
}
//sobald n < als i ist, ist die Anzahl der restlichen schritte bekannt.
oneMillion[(int)i]= oneMillion[(int)n]+count;
}
// Input - Output. Wichtig hierbei ist, das die erste Zahl des Inputs nicht unbeingt die kleinere sein muss.
// bei der Eingabe "10 1" muss also auch bei der Ausgabe "10 1" stehen, dabei müssen trotdem die Zahlen von 1 bis 10 betrachtet werden.
line = Main.ReadLn (1000);
while (line != null)
{
idata = new StringTokenizer (line);
start = Integer.parseInt (idata.nextToken());
end = Integer.parseInt (idata.nextToken());
lowerParam = Math.min(start, end);
higherParam = Math.max(start, end);
for(int g = lowerParam; g <= higherParam; g++)
maxCount = Math.max(maxCount, oneMillion[g]);
System.out.println(start + " " + end + " " + maxCount);
maxCount = 0;
line = Main.ReadLn (1000);
}
}
// utility function to read from stdin (kopiert aus dem Forum)
static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if (((car < 0) || (car == 10)) && (lg <= 2)) return (null); // eof
return (new String (lin, 0, lg));
}
}
4. Java, Peter Schnitzle
/* Problem : 100
* Author : Peter Schnitzle
* Status : AC
* Runntime : 1.3
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
while (true) {
String line = reader.readLine();
if (line == null) {
// end of file reached
break;
}
StringTokenizer tokenizer = new StringTokenizer(line);
int start = Integer.parseInt(tokenizer.nextToken());
int end = Integer.parseInt(tokenizer.nextToken());
int max = 0;
if (start <= end)
{
for (int count = start; count <= end; count++)
{
int temp = circle(count);
if (temp > max)
{
max = temp;
}
}
}
else
{
for (int count = end; count <= start; count++)
{
int temp = circle(count);
if (temp > max)
{
max = temp;
}
}
}
System.out.println(start + " " + end + " " + max);
}
}
public static int circle(int v)
{
int count = 1;
while (v != 1)
{
if ((v & 1) == 0)
{
v = v>>1;
}
else
{
v = 3*v + 1;
}
count++;
}
return count;
}
}
5. C, Till Fischer
/*
============================================================================
Name : 100.c
Author : Till Fischer
Description : 100 - The 3n + 1 problem
Accepted : Accepted
Time : 0.990
============================================================================
*/
#include <stdio.h>
int main(void) {
int a, b, min, max,
cycle, cyclemax, num, n;
while(scanf("%d %d\n", &a, &b) == 2)
{
if(a > b)
{
max = a;
min = b;
}
else
{
max = b;
min = a;
}
for (cyclemax=-1, num=min; num<=max; num++) {
for (n=num, cycle=1; n != 1; cycle++)
{
if ((n % 2) != 0)
{
n=3*n+1;
}
else
{
n >>= 1;
}
}
if (cycle > cyclemax) cyclemax=cycle;
}
printf("%i %i %i\n", a, b, cyclemax);
}
return 0;
}
6.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 100 The 3n+1 Problem
* Link: http://uva.onlinejudge.org/external/1/100.pdf
*
* @author Siegfried Ippisch
* @version 1.0, 06/08/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.208
*/
import java.util.Scanner;
class Main{
private static int cycleLength(int n){
int length = 0;
while(true){
length++;
if(n == 1){
break;
} else if(n%2 == 1){
n = 3*n +1;
} else{
n = n/2;
}
}
return length;
}
private static int maxCycleLength(int i, int j){
int maxLength = 0;
for(int k=Math.min(i, j); k<=Math.max(i, j); k++){
int length = cycleLength(k);
if(length > maxLength)
maxLength = length;
}
return maxLength;
}
public static void main(String[] args){
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int i = input.nextInt();
int j = input.nextInt();
System.out.println(i+" "+j+" "+maxCycleLength(i,j));
}
input.close();
}
}
7.
/* ACM Problem 100 :)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36
* Fakultät für Informatik und Mathematik, Hochschule München
* Entwickelt mit: Eclipse
* Status: ACCEPTED
* Time: 1.232
*/
import java.util.*;
public class Main
{
/** Hauptprogramm.
* @param args Kommandozeilenargumente.
*/
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt())
{
// separate Abspeicherung des Inputs, um bei der Ausgabe
// wieder die selbe Reihen folge zu erhalten
final int is = sc.nextInt();
final int js = sc.nextInt();
// Input 1 10 Output 1 10 20
// Input 10 1 Output 10 1 20 sollen beide möglich sein
int i = Math.min(is,js);
int j = Math.max(is,js);
int maxLength = 0;
for(int k = i; k <= j; k++)
{
// maxLength = Math.max(maxLength, collatz(k, 1));
int length = 1;
int n = k;
while(n != 1)
{
n = (n % 2 == 0) ? n / 2 : 3 * n + 1;
length++;
}
maxLength = Math.max(maxLength, length);
}
System.out.printf("%d %d %d%n", is, js, maxLength);
}
}
}
8. Martin Lambeck
package acm_100_three_n_plus_one;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main
{
public static BufferedReader bsr = new BufferedReader(new InputStreamReader(System.in));
/**
* @param args
* @throws Exception
* @throws IOException
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
String line;
try
{
while(true)
{
line = bsr.readLine();
if (line == null)
return;
doLine(line);
}
} catch (Exception e)
{
}
}
public static void doLine(String line) throws IOException
{
StringTokenizer st = new StringTokenizer(line, " ");
long from = Long.parseLong(st.nextToken());
long to = Long.parseLong(st.nextToken());
long tmp = 0;
long max = 0;
long steps = 1;
String out = from + " " + to;
if (from > to)
{
tmp = from;
from = to;
to = tmp;
}
for (long i = from; i <= to; i++)
{
if ((i << 1) > to)
{
//if (!(((tmp % 3) == 0) && ((tmp / 3) >= from)))
if((i + i + i - 1) > from)
{
steps = 1;
tmp = i;
while (tmp > 1)
{
steps++;
if ((tmp & 1) > 0)
{
tmp = (tmp + tmp + tmp) + 1;
} else
{
tmp = tmp >> 1;
}
}
if (steps > max)
max = steps;
}
}
}
System.out.println(out + " " + max);
}
}