Ley Vinicius-Prestianni

Probablemente estás enterado de que en el Mundial 2026 entró en vigor la Ley Vinicius-Prestianni para evitar insultos racistas. Dicha ley se creó a partir de un incidente entre los jugadores Vinicius Jr y Gianluca Prestianni en el que se intercambiaron insultos con la boca tapada para evitar ser vistos por las cámaras. De ahora en adelante, los jugadores deben hablarse sin taparse la boca so pena de expulsión.

Para poder aplicar la Ley Vinicius-Prestianni de forma correcta, la FIFA requiere que los estadios tengan una cobertura total de la cancha mediante cámaras de video, es decir, cada posición del campo debe estar cubierta por alguna cámara que permita ver la boca de los jugadores cuando se hablan.

La Federación Mexicana de Fútbol le pidió ayuda a Karel para condicionar el Estadio Banorte (antiguamente Azteca) para que configure las cámaras de la cancha.

Karel tiene a su disposición cámaras que pueden cubrir un sector de la cancha, cada cámara tiene un alcance ~R~, si Karel posiciona la cámara en una coordenada ~x~, la cámara es capaz de cubrir el rango ~[x-R, x+R]~. Sin embargo, debido a las modificaciones que le hicieron al estadio, no es posible colocar cámaras en cualquier lugar. Karel puede colocar cámaras sólo en ciertos lugares y utilizando dichos lugares debe cubrir el campo completo usando el mínimo número posible de cámaras.

Problema

La primera fila del mundo tiene algunos montones de ~1~ zumbador. Dichos montones indican las columnas en las que Karel puede colocar una cámara. Karel debe colocar cámaras en algunas de esas posiciones de modo que el mundo completo quede cubierto. Además, Karel debe utilizar el mínimo número posible de cámaras para hacerlo.

Karel lleva en su mochila una cantidad de zumbadores igual a ~R~ el rango de cobertura de las cámaras.

• Si es posible cubrir el mundo, Karel debe terminar orientado al norte.
• Si NO es posible cubrir el mundo, Karel debe terminar orientado al sur.

En caso de que sea posible cubrir el mundo, Karel debe dejar únicamente aquellos montones en lo que se debe colocar cámara y eliminar los demás.

Entrada

Salida

Descripción

Observa que ~R = 5~, ya que Karel inicia con ~5~ zumbadores en la mochila. Eso quiere decir que si colocas cámara en una columna, la cámara cubre ~5~ columnas hacia la izquierda y ~5~ columnas hacia la derecha. El ejemplo de salida muestra una configuración que cubre todo el campo y que utiliza 3 cámaras. Este es el mínimo de cámaras que se puede utilizar para este ejemplo, sin embargo, existen otras soluciones que utilizan 3 cámaras distintas a esta.

Consideraciones

• Karel inicia en la posición (1, 1) viendo al norte.
• Karel lleva ~R~ zumbadores en la mochila. El valor de ~R~ estará en el rango [1, 100].
• La primera fila del mundo contiene montones de ~1~ zumbador separados entre sí que indican las posiciones en dónde se puede colocar una cámara.
• El mundo de Karel puede tener anchos que van desde ~10~ hasta ~1000~.
• El mundo tiene $100$ filas de altura.
• Para obtener los puntos, tu programa deberá:
  • Si es posible cubrir el mundo:
    • Deberá dejar a Karel orientado al norte.
    • Deberá dejar, en la primera fila del mundo, los montones de zumbadores en los que se colocó cámara. Los montones que deje deben ser el mínimo posible.
    • Si hay más de una solución que utilice el mínimo de cámaras, cualquiera de ellas se considerará correcta.
  • Si NO es posible cubrir el mundo:
    • Deberá dejar a Karel orientado al sur.

Subtareas

En este problema, los casos de cada subtarea se encuentran agrupados. Para obtener el puntaje de una subtarea deberás resolver correctamente todos los casos del grupo.

• Subtarea 1 (25 puntos): El mundo inicial tendrá únicamente un montón de zumbadores. Es decir, sólo habrá una posición en la que puedes colocar cámara.
• Subtarea 2 (25 puntos): Todas las posiciones de la primera fila tienen zumbador. Es decir, puedes colocar cámaras en cualquier posición que quieras.
• Subtarea 3 (25 puntos): Sin restricciones.
• Subtarea 4 (25 puntos): Debes ejecutar la instrucción avanza / move() como máximo ~2N~ veces, donde ~N~ es el ancho del mundo.