Kill Karel

¡Karel ha hecho enojar a la temida asesina conocida como La Mamba Negra! A causa de ello, la Mamba, le ha aplicado a Karel el golpe secreto de los 9N pasos. Este golpe ocasionará que el corazón de Karel explote si llega a avanzar 9N veces. Por suerte para Karel, existe un antídoto para dicho golpe.

Después de darle el golpe, la Mamba dejó a Karel en un cuarto cerrado, junto a una de las paredes del mismo. Karel sabe que oculto en la pared del cuarto hay un frasco con el antídoto. Más aún, sabe que si avanza manteniéndose siempre junto a la pared podrá encontrar el frasco a una distancia de N pasos, sin embargo no sabe hacia qué lado debe buscar.

Ayuda a Karel a encontrar el antídoto avanzando menos de 9N veces.

El cuarto está totalmente delimitado por paredes y la posición donde se encuentra el frasco está representada por una casilla con 1 zumbador. Karel deberá apagarse en cuanto encuentre el antídoto.

• Karel inicia junto a una de las paredes del cuarto en alguna dirección.
• Karel lleva 0 zumbadores en la mochila.
• El cuarto no necesariamente es rectangular.
• Karel no conoce el número N.
• Para obtener puntos en este problema, Karel deberá encontrar el frasco y apagarse antes de haber avanzado 9N veces. NOTA: El número N varía con cada caso de prueba, al momento de ser evaluado, se verificará que para cada caso, tu ejecución no avance más veces de las permitidas. ES IMPORTANTE QUE ENTIENDAS QUE NO BASTA ENCONTRAR EL FRASCO, TIENES QUE ENCONTRARLO AVANZANDO MENOS DE 9N VECES.
• No importa la orientación final de Karel, únicamente su posición.
• En este problema cada caso de prueba constará de 2 mundos los cuales son un reflejo horizontal uno del otro.

La figura a) muestra a Karel en su posición de inicio junto a la pared del cuarto. Para este mundo N=2 ya que el frasco está a 2 avances. La figura b) muestra a Karel después de detenerse al encontrar el frasco. Las figuras c) y d) muestran la misma entrada y salida, pero esta vez con el mundo reflejado.

La última consideración originalmente decía: "En este problema cada caso de prueba constará de 2 mundos los cuales son un reflejo horizontal uno del otro, para obtener los puntos, tu programa deberá resolver correctamente ambos." Sin embargo, el evaluador de Karelotitlán no puede agrupar casos, por lo tanto debes tomar en cuenta que si no resuelves el caso N y el caso N + 10, no hubieras tenido puntos por esos casos en el examen nacional.

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 16a OMI, celebrada en la ciudad de Cuernavaca, Morelos en el año 2011.