Cuarta Evaluación de Temas Selectos de Sistemas
Jueves 2 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 6.6.3: Contando (contar.c, contar.cpp
ó contar.java)
Gustavo sabe contar, pero apenas está aprendiendo como escribir
números. Él ya aprendió los dígitos 1, 2, 3
y 4. Pero aún no se da cuenta de que el 4 es diferente al 1, de
modo que piensa que el 4 es sólamente otra forma de escribir 1.
Él se está divirtiendo con un jueguito que el
creó: el construye números con los cuatro dígitos
que conoce y suma sus valores. Por ejemplo 132 = 1 + 3 + 2 = 6 y 112314
= 1 + 1 + 2 + 3 + 1 + 1 = 9 (recuerda que Gustavo cree que 4 = 1).
Ahora Gustavo quiere saber cuántos de estos números puede
crear cuya suma sea un número N. Para N = 2, él puede
construir 5 números: 11, 14, 41, 44 y 2. (Él sabe contar
más allá del cinco, lo que no sabe es cómo
escribirlo.) Sin embargo, el no puede encontrar esta cantidad para N
mayor que 2, y por eso pide tu ayuda.
Entrada: La entrada
consistirá de una cantidad arbitraria de enteros N tales que 1
<= N <= 1000. Debes leerlos hasta el fin de archivo.
Salida: Para cada entero
leído, escribe en cada renglón la cantidad de
números que puede construir Gustavo tales que la suma de sus
dígitos sea N.
Pista:
¿Podrías encontrar una recurrencia para la cantidad
pedida?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban contar < contar.ent > contar.txt
y comparen contar.txt con
contar.sal
Problema 6.6.8: Paso a paso (pasoxy.c, pasoxy.cpp ó
pasoxy.java)
Considere el proceso de avanzar del entero X al entero Y a lo largo de
los puntos enteros de una línea recta. La longitud de cada paso
deber ser positiva y puede ser uno mayor que, igual a ó uno
menor que la longitud del paso previo. ¿Cuál es el
número mínimo de pasos necesarios para llegar de X a Y?
Las longitudes del primer paso y del último paso deben ser
iguales a 1.
Entrada: La entrada comienza
con una línea conteniendo a N, el número de casos de
prueba. Cada caso de prueba que sigue consiste de una línea con
dos enteros X y Y tales que 0 <= X <= Y < 231.
Salida: Para cada caso de
prueba, escribe una línea dando el número mínimo
de pasos para llegar de X a Y.
Pista: ¿Qué tipo
de sucesiones de longitudes pasos quedan definidas por las soluciones
óptimas?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban pasoxy < pasoxy.ent > pasoxy.txt
y comparen pasoxy.txt con
pasoxy.sal