Capitalisme Interplanétaire – Qualification 2020

Énoncé¶

Suite à la pénurie d'hypercarburant de 8153, le conseil suprême de la corporation a voté des coupes de budget. Pour faire toujours plus d'économies les différents vaisseaux de la flotte vont devoir subir un emploi du temps bien plus chargé.

La corporation décide d'assigner des ordres de missions à ses équipages, chaque ordre de mission est constitué d'un emploi du temps d'une durée de d jours. Le i^ème jour, l'équipage doit remplir un objectif qui ne peut être exécuté que sur un certain type de planète mission[i]. Pour rappel, les planètes du système ont été catégorisées en t types différents, numérotés de 0 à t - 1. À noter qu'il y a au moins une planète de chaque type dans le système. Aussi, grâce à OpenSpaceMap il est facile de lister le type de chacune des n planètes et leurs coordonnées précises.

La corporation s'est rendu compte que les équipages profitaient de leurs missions pour aller voir leurs proches ou se dorer la pilule sur ZT637, et engendrent des surcouts à cause de leurs détours. Elle a donc besoin d'un moyen de calculer la distance minimale à parcourir lors d'une mission pour imposer des budgets réalistes aux équipages. Elle en profite aussi pour mieux répartir ses ordres de missions, donc vous pouvez supposer qu'une mission commence sur n'importe la planète qui arrange le plus la corporation.

Distance de Manhattan¶

La distance de Manhattan est la distance entre deux points d'un quadrillage représentant la distance parcourue afin de rejoindre ces deux points en suivant les lignes du quadrillage. Par exemple deux points A(1, 4) et B(4, 1) auront une distance de Manhattan de 6.

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : t, nombre de types de planètes distincts.
• Sur la ligne suivante, un entier : n, le nombre de planètes dans le système.
• Sur les lignes suivantes, une liste de n éléments : planetes, les planètes du système.
  • Une ligne par élément de la liste : séparés par des espaces, un entier x (abscisse de la planète), un entier y (ordonnée de la planète), et un entier k (type de planète).
• Sur la ligne suivante, un entier : d, la durée de la mission à traiter.
• Sur la ligne suivante, une liste de d entiers séparés par des espaces : mission, pour chaque jour de la mission, le type de planète à visiter.

Sortie¶

Affichez un entier : la distance minimale à parcourir pour remplir la mission décrite. Les distances devront être calculées en utilisant la distance de Manhattan, décrite ci-dessus.

Contraintes¶

• 1 ≤ t ≤ 500
• 0 ≤ n ≤ 500
• 1 ≤ d ≤ 500
• 0 ≤ mission[i] ≤ 500
• 0 ≤ x ≤ 1000000
• 0 ≤ y ≤ 1000000
• 0 ≤ k < t