All pastes #2087720 Raw Edit

Mine

public text v1 · immutable
#2087720 ·published 2011-10-07 17:43 UTC
rendered paste body
import java.io.IOException;
import java.util.Scanner;
import java.util.StringTokenizer;


/*
 * 3n+1 Problem: problema basico para entender memoria dinamica
 * la version de aqui es diferente a la que entregue al juez
 * la razon es que el problema si lo leen no tiene condcion de
 * escape, me toco implementar unas cosas remamonas con buffer
 * reader y una funcion que encontre por internet pero ambas hacen
 * ruido por lo cual lo dejo con solo el scanner >_<
 * 
 */

public class Main {

	//Nos dicen que las entradas estan entre 1 y 1000000
	static int size = 1000005;
	//El Vector para almacenar los valores ya calculados 
	static long[] granizada = new long[size];
	
	
	public static void main(String[] args) {

		
		long i = 1;
		long j = 1;
		long temp;
		granizada[1]=1;
		Scanner scn = new Scanner (System.in);
		
		while (scn.hasNext()){
			i = scn.nextInt();
			j = scn.nextInt();
		
			
			
		String n = null;
		
			long mem=0;
			long max=0;

			
			// no dice que i se siempre menor que j
			
			if(i>j){
				temp=i;
				i=j;
				j=temp;
				
			}				
			// ojo aqui va hasta j
			for (long a=i; a<=j; a++){
				mem = memDinamCic(a);
				if(max < mem)
					max = mem;
			}
			System.out.println(i + " " + j + " " + max);
		}

	}
	
	/*
	 * La vaina se reduce a que si estamos buscando un numero
	 * que se demora una cantidad x de ciclos, por ejemplo 3
	 * la secuencia seria:
	 * 3 -> son 8 Ciclos
	 * 10 -> son 7 Ciclos
	 * 5 -> son 6 Ciclos
	 * 16 -> son 5 Ciclos
	 * .
	 * .
	 * .
	 * Ya vieron el invariante, si yo guardo en el vector la 
	 * la cantidad de ciclos de 10 cuando me pidan 3 solo voy
	 * a tener sumarle 1 al valor de 10 que ya conosco...
	 * */
		
	private static long memDinamCic(long a) {
		

		if(a<size){
			if(granizada[(int) a]!=0)
				return granizada[(int) a];
		}
		if(a%2!=0){
			if(a<size){
				granizada[(int) a] = 1 + memDinamCic((a*3)+1);
				return granizada[(int) a];
			}
			
			return 1 + memDinamCic((a*3)+1);
		}
		else{
			if(a<size){
				granizada[(int) a]= 1 + memDinamCic(a/2);
				return granizada[(int) a];
			}
			return 1 + memDinamCic(a/2);
		}

	}
}