teddy online judge

14. El problema 3n + 1

Limite de tiempo : 5 seg.   Total runs : 750  Aceptados : 89

Background

Los problemas en Ciencias de la Computación son a menudo clasificados como pertenecientes a una clase de problemas (ej. NP, irresoluble, recursivo, etc.). En este problema debes analizar una propiedad de un algoritmo cuya clasificación no es conocida para todas las entradas.

El problema

Considera el siguiente algoritmo:

		1. 		 input n

		2. 		 print n

		3. 		 if n = 1 then STOP

		4. 		 		 if n is odd then n ← 3n+1

		5. 		 		 else n ← n / 2

		6. 		 GOTO 2

Dada la entrada 22, la siguiente secuencia de números son impresos: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Esto hace presumir que el algoritmo citado arriba, termina cuando imprime 1, para algún único valor. A pesar de la simplicidad del algoritmo, se desconoce si la conjetura es cierta. Este ha sido verificado, únicamente, para todos los enteros n tal que 0<n<1,000,000.

Dada una entrada n, es posible determinar el número de números impresos (incluyendo el 1). Para un n esto es llamado "tamaño del ciclo de n. En el ejemplo citado, el tamaño del ciclo de 22 es 16.

Dados dos números i y j determina el tamaño de ciclo máximo entre estos.

La entrada

La entrada consiste de una serie de pares de entero i y j, un par de enteros por línea. Todos los enteros son menores que 1,000,000 y mayores que 0.

Debes procesar. todos los pares de enteros y para cada par determinar el ciclo de tamaño máximo, entre todos los valores incluidos i y j. Puedes asumir que no hay operaciones que sobrepasen un entero de 32-bits.

La salida

Para cada par de enteros i y j imprime i, j y el ciclo de tamaño máximo entre todos los valores incluidos i y j. Estos tres números deben estar separados por un solo espacio, todos en una sola línea y con una línea de salida por cada línea de entrada. Los enteros i y jdeben aparecer en la salida en el mismo orden en el cual ellos aparecen en la entrada y deben estar seguidos por el ciclo de tamaño máximo (en la misma línea).

1 10
100 200
201 210
900 1000

1 10 20
100 200 125
201 210 89
900 1000 174

Fuente: UVa Online Judge - The 3n + 1 problem