USACO OCT06 2006 Problem 'acng' Analysis

by Rob Kolstad

This is the well-known 'Collatz conjecture' (check out the web page for an interesting picture of the Collatz Fractal), sometimes known as the 3n+1 problem.

The program is straightforward, with no tricks at all. Here is the JAVA solution of USA's Brian Hamrick:

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

class acng {
    public static void main(String[] args) throws IOException {
	BufferedReader f = new BufferedReader(new FileReader("acng.in")); 
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("acng.out"))); 
	StringTokenizer st = new StringTokenizer(f.readLine());
	int i = Integer.parseInt(st.nextToken());
	int score = 0;
	while (i != 1){
	    if(i%2==0){
		i /= 2;
	    } else {
		i = i*3 + 1;
	    }
	    score++;
	}
	out.println(score);
	out.close();
	System.exit(0);
    }
}