Habitantes: 31962
18 invitados en línea.
Karelotitlán OMI OMI-DF
Página principal R e g í s t r a t e Problemas Karel Usuarios

   Bienvenido(a) invitado(a)
Iniciar sesión

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

Imagen

Mundo de ejemplo



Imagen

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.




Envio de archivos para evaluación
Para enviar una solución a este
problema, por favor inicia sesión.

Karelotitlán v1.2.6
por Félix Rafael Horta Cuadrilla
Créditos

Karelotitlán funciona mejor en Mozilla Firefox y Google Chrome ¡Pruébalos!