Nombre y enunciado
El cuerpo de Ingenieros de la Legión de Reconocimiento fue asignado a proteger el Muro Rose ante un inminente ataque de titanes.
A lo largo del muro se instalaron cañones de defensa. Cada cañón tiene un alcance limitado, que le permite cubrir una porción específica del muro. Sin embargo, activar un cañón consume una gran cantidad de pólvora y recursos, por lo que solo deben encenderse los estrictamente necesarios para proteger toda la sección crítica del muro.
Definición formal
Entrada:
El tramo de muro a defender está representado por el intervalo:
Cada cañón posee:
- una posición , que indica su ubicación sobre el muro, medida en metros desde el punto ;
- un alcance , medido en metros.
Por lo tanto, el cañón cubre el segmento:
Además, se asegura que:
- es posible cubrir todo el tramo con los cañones disponibles;
- todos los valores son positivos y reales.
Salida:
Activar la menor cantidad posible de cañones de forma que cada punto del muro dentro del intervalo esté protegido por al menos un cañón. La salida debe indicar:
- el número mínimo de cañones activados;
- la lista de cañones seleccionados, ya sea por índice o por posición.
Ejemplo concreto
Tramo a defender:
Los ingenieros disponen de los siguientes cañones:
| Cañón | Posición | Alcance | Segmento cubierto |
|---|---|---|---|
| C1 | 2 | 3 | |
| C2 | 7 | 5 | |
| C3 | 14 | 4 | |
| C4 | 17 | 6 | |
| C5 | 20 | 2 | |
| C6 | 5 | 1 |
Salida esperada:
Cañones seleccionados: C1, C2 y C4
Número mínimo: 3 cañones activados
Por dónde empezar
La tarea consiste en diseñar un algoritmo de defensa ávido que determine qué cañones deben activarse para que toda la muralla quede bajo protección, minimizando la cantidad de cañones encendidos.