Description| Problem G: Prime Network |
| Time Limit: 5 seconds |
DescriptionEn el año 1975, el módulo 1 de la FCC tenía n computadoras, cada computadora estaba conectada físicamente con las (n-1) restantes para formar su red local (si el cable que conectaba la computadora i con j se averiaba, ya no existía forma alguna de comunicarse entre i y j). ¡Ya se imaginarán el cablerío que existía!
Cada computadora tenía una dirección IP única 192.168.0.i (0 < i <= n) con respecto a las demás computadoras enlazadas en la misma red. Un virus ha atacado a la red y no permite comunicar a cualquier equipo con dirección 192.168.0.i con otro equipo con dirección 192.168.0.j si i + j no es primo.
Cansados de intentar eliminar el virus, optaron por modernizar la red a una con topología de anillo donde cada computadora está conectada a otras dos computadoras distintas de tal forma que se puedan comunicar entre ellas aún con el virus. Puedes ver un ejemplo de una red con topología de anillo en el dibujito del problema.
Dada una red con n ( n < 256) computadoras con direcciones 192.168.0.1, 192.168.0.2, …, 192.168.0.n. Imprime alguna configuración en que debe estar conectadas las computadoras de tal forma que se pueda hacer una red con estructuras de anillo tomando en consideración las restricciones que el virus presenta.
La entrada consiste de varios casos de entrada. Cada caso consiste de una línea que contiene un número entero positivo 2 < n < 256. La entrada termina con un caso cuando n = 0, este último caso no debe producir salida alguna.
Por cada caso imprime una lista con las n direcciones IP, enteros separados por un espacio en blanco, de la forma en que las computadoras deben estar conectadas para formar la estructura de anillo y que cumpla los requerimientos mostrados antes. En caso de no existir ninguna imprime ‘Imposible’.
Sample input |
Sample output |
|---|---|
3 |
Imposible |
Nota: Cualquier solución de más de 8K de código será respondido como 'Wrong Answer'. Lo cuál siendo sinceros no es una limitante para enviar una tabla.