Patrones
17a OMI, Hermosillo 2012
Descripción
Karel se ha vuelto aficionado a encontrar patrones generadores dentro de listas de números. Si se tiene una lista de números, un patrón generador es cualquier secuencia de números que al escribirla una cierta cantidad de veces genere la lista completa.
Por ejemplo, la lista 123123123123 puede ser generada tanto por el patrón 123 como por el patrón 123123, sin embargo el primer patrón (123) tiene longitud menor.
Problema
Ayuda a Karel a que dada una lista de números, deje sólo el patrón generador de menor longitud y borre todos los demás números.
Consideraciones
- El mundo no contiene paredes internas.
- Además de los montones que representan la lista, no hay ningún otro zumbador en el mundo.
- Karel inicia en esquina inferior izquierda del mundo orientado al Norte.
- Karel inicia con infinitos zumbadores en su mochila.
- La lista de números está representada por montones contiguos de zumbadores en la fila inferior del mundo, iniciando en la casilla (1,1).
- La lista termina con el primer espacio en blanco.
- Karel deberá dejar el patrón generador de menor longitud a partir de la casilla (1,1).
- Además del patrón generador, NO deben quedar zumbadores en la primera fila.
- No importa la posición ni la orientación final de Karel. Solamente importa que dejes los zumbadores que representan el patrón generador de menor longitud.
Ejemplo
Mundo de ejemplo
Solución al mundo de ejemplo
Explicación al mundo de ejemplo
Al final de la ejecución Karel debe dejar sólo el patrón generador (123) y eliminar el resto de la lista. Como puede verse en la figura ni la posición ni la orientación finales de Karel importan. Tampoco los zumbadores en posiciones que no pertenecían a la lista original. Por ejemplo, el montón de 5 zumbadores en la posición (1,2) no se toma en cuenta para tu calificación.
Agradecimiento
Se agradece al Comité Olímpico Mexicano de Informática el permiso para publicar este problema en nuestro sitio; que fue aplicado en el examen nacional de la 17a OMI, celebrada en la ciudad de Hermosillo, Sonora en el año 2012.