Karel Attractio

Después de jugar Attractio, Karel quedó muy emocionado y decidió hacer sus propios experimentos de alteración de gravedad.

Karel ha creado un mundo en donde hay montones que atraen a Karel con una fuerza gravitacional igual al número de zumbadores en el montón. Karel puso estos montones a todo lo largo de la fila 1 del mundo, pero no contaba con que una vez colocados, la fuerza gravitacional le haría muy difícil moverse.

Si Karel tiene montones a su derecha y a su izquierda, la fuerza gravitacional de unos y otros se anula. De modo que el único lugar en que Karel está libre de fuerza gravitacional es donde la suma de las fuerzas de los montones a su izquierda es igual a la suma de las fuerzas de los montones a su derecha. Si Karel está sobre un montón, se considera que este montón lo está atrayendo hacia la izquierda.

Escribe un programa que, colocados los montones de zumbadores, posicione y apague a Karel en la casilla de la fila 1 donde las fuerzas gravitacionales sobre él se anulan (ver ejemplo).

• Karel inicia en la posición (1,1) del mundo viendo al Norte.
• La fila 1 del mundo está llena de montones de zumbadores, ningún montón tiene más de 100 ni menos de 1.
• Karel inicia con 0 zumbadores en la mochila.
• Los mundos tienen sólo 1 fila de alto.
• Para obtener los puntos en un caso, tu programa deberá apagar a Karel en la posición donde las fuerzas gravitacionales sobre él se anulen (se asegura que siempre habrá una casilla dónde eso suceda), no importan la dirección final de Karel ni los montones de zumbadores que queden en el mundo.

• En casos que valen el 32% de los puntos, Karel podrá ejecutar la instrucción avanza/move como máximo 500 veces. Si en algún caso tu programa ejecuta la instrucción avanza/move más de 500 veces obtendrás 0 puntos para ese caso.
• En los casos que valen el restante 68% de los puntos, Karel no tiene ese límite

Recuerda que si Karel está sobre un montón se considera que el montón lo está atrayendo hacia la izquierda. Para este ejemplo Karel se detiene en la casilla (5,1), eso quiere decir que la fuerza que lo atrae hacia la izquierda es igual a: 1+10+3+5+7=26. La fuerza que lo atrae hacia la derecha es igual a: 11+9+6=26. De modo que las fuerzas a la izquierda y derecha se anulan mutuamente y Karel puede descansar tranquilamente.

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 18a OMI, celebrada en la ciudad de Toluca, Estado de México en el año 2013.