Quinta Evaluación de Temas Selectos de Sistemas
Jueves 9 de junio de 2005 (13:00 a 15:55)
Instrucciones: Deberán
resolver dos problemas, por lo que me deberán entregar dos
códigos fuente, uno para cada problema. Cada problema se
evaluará con 10 casos de prueba y cada uno de ellos vale 1
punto. Pongan un comentario en su código indicando los dos
integrantes del equipo. La lectura se hará desde la entrada
estándar y la escritura hacia la salida estándar. En sus
pruebas, usen la redirección de entrada y salida.
Problema 7.6.3: El problema de Euclides (euclid.c, euclid.cpp
ó euclid.java)
Desde los tiempos de Euclides se sabe que para cualesquiera dos enteros
positivos A y B existen enteros X e Y tales que AX + BY = D, donde D es
el máximo común divisor de A y B. El problema es el de
encontrar los valores correspondientes de X, Y y D para valores dados
de A y B.
Entrada: La entrada consiste de
un conjunto de líneas con dos enteros positivos A y B separados
por un espacio (A, B < 1,000,000,001).
Salida: Para cada línea
de entrada la línea de salida deberá consistir de tres
enteros X, Y y D separados por espacios. Si hay varios valores de X e
Y, tú debes generar aquellos tales que X <= Y y |X|+|Y| es
mínimo.
Pista: ¿Estás
seguro de que la construcción en el texto produce tal pareja
mínima?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban euclid < euclid.ent > euclid.txt
y comparen euclid.txt con
euclid.sal
Problema 7.6.6: Los números de Smith (nsmith.c, nsmith.cpp
ó nsmith.java)
Al estar revisando su directorio telefónico en 1982, el
matemático Albert Wilansky notó que el número
telefónico de su cuñado H. Smith tenía la
siguiente extraña propiedad: La suma de los dígitos de
ese número era igual a la suma de los dígitos de los
factores primos de ese número. ¿Le entendiste? El
número telefónico de Smith era 493-7775. Este
número se puede escribir como el producto de sus factores primos
de la siguiente forma: 4937775 = 3 x 5 x 5 x 65837. La suma de los
dígitos del número telefónico es 4 + 9 + 3 + 7 + 7
+ 7 + 5 = 42 y la suma de los dígitos de sus factores primos es
igualmente 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42. Wilansky nombró a
este tipo de números con el nombre de su cuñado: los
números de Smith. Como esta propiedad es cierta para todo
número primo, Winlansky los excluyó de la
definición. Otros números de Smith son 6036 y 9985.
Wilansky no fue capaz de encontrar un número de Smith que fuera
mayor que el número telefónico de su cuñado.
¿Podrías ayudarlo?
Entrada: La entrada consiste de
varios casos de prueba, cuya cantidad está dada en la primera
línea de la entrada. Cada caso de prueba consiste de una
línea que contiene un entero N mayor que 1 y menor que
1,000,000,000.
Salida: Para todo valor de
entrada N, calcula el menor número de Smith que sea mayor que N
e imprímelo en una línea. Puedes suponer que tal
número existirá.
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban nsmith < nsmith.ent > nsmith.txt
y comparen nsmith.txt con
nsmith.sal