Loki contre Heimdall – Épreuve régionale 2024

Niveau 3 ⋅ Validation weight: 40%

Énoncé

Loki et Heimdall s'affrontent, et viennent de lancer toutes leurs troupes dans la bataille. Les guerriers, vaillants mais voulant se ménager, tentent de choisir leurs adversaires en se déplaçant le moins possible.

La position des troupes de Loki et de Heimdall est renseignée dans les tableaux d'entiers loki et heimdall.

La distance entre une troupe en position $i$ et une troupe adverse en position $j$ est donnée par $(i - j)^2$. Les troupes vont systématiquement attaquer la troupe adverse la plus proche.

Aidez Jøsëf à calculer la distance totale que vont parcourir les troupes des deux dieux.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de troupes de Loki.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : loki, les positions des troupes de Loki.
  • Sur la ligne suivante, un entier : M, le nombre de troupes de Heimdall.
  • Sur la ligne suivante, une liste de M entiers séparés par des espaces : heimdall, les positions des troupes de Heimdall.

Sortie

Afficher, sur une ligne, la distance totale que vont parcourir les troupes.

Contraintes

  • $1 \le N \le 100$
  • $1 \le \text{loki[i]} \le 100$
  • $1 \le M \le 100$
  • $1 \le \text{heimdall[i]} \le 100$

Contraintes de performance

  • $1 \le N \le 100\,000$
  • $1 \le M \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
6 3 11
2
5 8
Exemple de sortie
19
Commentaire

Loki possède trois troupes, en position $6$, $3$ et $11$. Heimdall possède deux troupes, en position $5$ et $8$.

Considérons les troupes de Loki.

  • La troupe en position $6$ va attaquer la troupe en position $5$, et va donc effectuer une distance de $1^2 = 1$
  • La troupe en position $3$ va attaquer la troupe en position $5$, et va donc parcourir une distance de $2^2 = 4$
  • La troupe en position $11$ va attaquer la troupe en position $8$, et va donc effectuer une distance de $3^2 = 9$

Considérons maintenant les troupes d'Hemdall.

  • La troupe en position $5$ va attaquer la troupe en position $6$, et va donc parcourir une distance de $1^2 = 1$
  • La troupe en position $8$ va attaquer la troupe en position $6$, et va donc effectuer une distance de $2^2 = 4$

La distance totale est donc de $1 + 4 + 9 + 1 + 4 = 19$.

Exemple d'entrée
2
3 7
2
13 2
Exemple de sortie
63
Exemple d'entrée
2
7 6
3
3 5 8
Exemple de sortie
13