SW V : Les attaques chronométrées

L'empire a déployé une flotte d'armes puissantes dans toute la galaxie. Il projette de détruire des centaines de planètes habitées grâce à ces armes. Un agent rebelle a pu s'emparer du planning d'extermination projeté par l'empire. L'alliance sait maintenant où et quand auront lieu chacune des attaques et dispose d'un moyen de les contrer. Les scientifiques de l'alliance peuvent en effet déployer un bouclier, tout au long de l'attaque de l'Empire, mais à un seul endroit à la fois.

Connaissant le planning d'extermination et le nombre d'habitants de la planète visée à chaque fois, vous avez pour difficile tâche d'optimiser l'emploi du bouclier afin de préserver un maximum de vies.

Les données volées par l'agent rebelle sont une liste de quadruplets. Le premier élément est le nom de code de la planète, par exemple P456SR. Le second élément est le moment de début de l'attaque, en temps universel galactique, par exemple 3239. Le troisième élément est le moment de fin de l'attaque, en temps universel galactique aussi, par exemple 6000. Enfin le quatrième élément est le nombre d'habitants sur la planète visée, par exemple 50000. Pour contrer l'attaque, le bouclier doit être déployé tout au long de l'attaque prévue. Dès que le bouclier est désactivé quelque part, vous pouvez instantanément le déployer ailleurs dans la galaxie.

Voici un exemple de données factices :

P456SR 3239 6000 50000
P156DS 2340 8123 110000
P489HY 7345 9234 52000
P476ZE 1324 3239 22000
P989XY 1000 2000 5000

Sur l'axe du temps, on peut représenter les données ainsi :

Planning des attaques

La stratégie permettant de sauver le plus de monde est d'intervenir sur les attaques à l'encontre des planètes P476ZE, P456SR, P489HY :

Stratégie de défense optimale

Pour valider le défi, vous devez donner la liste des planètes sur lesquelles intervenir dans l'ordre chronologique des interventions. Dans le cas précédent, il faudrait donc répondre pour valider (attention aux guillemets) :

"P476ZE", "P456SR", "P489HY"
Ce problème est tiré de c0d1ng UP 2018

Type de retour

une séquence de chaînes de caractères

Entrée du problème

Lien vers les données d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : récursivité optimisation cup18