Capitalisme Interplanétaire – Qualification 2020

Niveau 4

É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

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
5000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
4
0 0 0
2 0 1
0 3 1
1 3 2
5
0 1 2 1 2
Exemple de sortie
6
Commentaire

Sur l'illustration, un chemin qui demande de parcourir un minimum de distance et permet de remplir la mission. Les flèches représentent le chemin et sont annotées par la distance parcourue.

Exemple d'entrée
3
5
0 1 0
1 1 1
6 2 0
6 0 1
7 1 2
14
1 0 1 0 1 2 0 1 0 1 2 0 0 1
Exemple de sortie
24
Commentaire