Llegando en k movimientos
Páginas: 2 (348 palabras)
Publicado: 18 de agosto de 2013
Llegando en K movimientos
Tiempo límite por caso: 1seg
Memoria límite por caso: 128MB
El COMI acaba de inventar un nuevo juego. El objetivo del juego es hacer llegar una ficha de laposición de salida a una posición destino en exactamente k movimientos.
En total hay N posiciones numeradas del 1 al N. Además hay M caminos que unen, cada uno, un par de posiciones. El juego iniciasiempre con la ficha en la posición 1. En cada turno, si la ficha está en la posición i y hay un camino entre la posición i y la j es posible mover la ficha de la posición i a la j. Si hay uncamino entre la posición i y la j, ese camino puede usarse para moverse tanto de i a j como de j a i. Durante el juego, está permitido que la ficha pase por la misma posición cualquier cantidad deveces. Es obligatorio mover la ficha en cada turno.
Problema
Escribe un programa que recibiendo el número N de posiciones y la lista de M caminos en el juego pueda contestar preguntas del tipo:“¿Es posible llegar, desde la posición 1 a la posición d en k movimientos?”
Entrada
Tu programa debe leer del teclado la siguiente información:
En la primer línea los números N y M, elnúmero de posiciones y de caminos, respectivamente.
En las siguientes M líneas hay dos números enteros separados por un espacio que representan las casillas que une ese camino.
En la siguientelínea, el número P que representa la cantidad de preguntas que se le harán a tu programa.
En las últimas P líneas hay dos enteros separados por un espacio que representan la posición destino di a laque se quiere llegar y el número ki de movimientos que se deben utilizar.
Salida
Tu programa debe escribir en pantalla P líneas con un número cada una. La i-ésima línea debe contener 1 si esposible llegar desde la posición de salida (posición 1) a la posición destino di en exactamente ki movimientos, en caso contrario debe contener 0 como respuesta.
Restricciones
1 < N
Tiempo límite por caso: 1seg
Memoria límite por caso: 128MB
El COMI acaba de inventar un nuevo juego. El objetivo del juego es hacer llegar una ficha de laposición de salida a una posición destino en exactamente k movimientos.
En total hay N posiciones numeradas del 1 al N. Además hay M caminos que unen, cada uno, un par de posiciones. El juego iniciasiempre con la ficha en la posición 1. En cada turno, si la ficha está en la posición i y hay un camino entre la posición i y la j es posible mover la ficha de la posición i a la j. Si hay uncamino entre la posición i y la j, ese camino puede usarse para moverse tanto de i a j como de j a i. Durante el juego, está permitido que la ficha pase por la misma posición cualquier cantidad deveces. Es obligatorio mover la ficha en cada turno.
Problema
Escribe un programa que recibiendo el número N de posiciones y la lista de M caminos en el juego pueda contestar preguntas del tipo:“¿Es posible llegar, desde la posición 1 a la posición d en k movimientos?”
Entrada
Tu programa debe leer del teclado la siguiente información:
En la primer línea los números N y M, elnúmero de posiciones y de caminos, respectivamente.
En las siguientes M líneas hay dos números enteros separados por un espacio que representan las casillas que une ese camino.
En la siguientelínea, el número P que representa la cantidad de preguntas que se le harán a tu programa.
En las últimas P líneas hay dos enteros separados por un espacio que representan la posición destino di a laque se quiere llegar y el número ki de movimientos que se deben utilizar.
Salida
Tu programa debe escribir en pantalla P líneas con un número cada una. La i-ésima línea debe contener 1 si esposible llegar desde la posición de salida (posición 1) a la posición destino di en exactamente ki movimientos, en caso contrario debe contener 0 como respuesta.
Restricciones
1 < N
Leer documento completo
Regístrate para leer el documento completo.