La Juste Muraille – Qualification 2025

Niveau 6 ⋅ Validation weight: 10%

Énoncé

C'est fait, Joseph Nageant a réussi à s'infiltrer dans la muraille ! Cependant, il n'a pas réussi à obtenir de carte de la muraille en bonne et due forme, seulement une description des tours qui la compose. Joseph essaie donc de cartographier la muraille à partir des informations dont il dispose pour pouvoir se repérer.

La muraille est composée de $N$ tours, reliées par des remparts de manière à former un cycle. Chaque tour possède une unique porte d'entrée et une unique porte de sortie. La porte de sortie de la première tour est reliée à la porte d'entrée de la seconde tour, et ainsi de suite jusqu'à compléter la muraille.

Cependant, Joseph Nageant ne connait pas exactement l'ordre des tours. Il connait seulement la profondeur exacte de la porte d'entrée et de la porte de sortie de chaque tour, grâce aux tableaux $\mathtt{sortie}$ et $\mathtt{entree}$, où $\mathtt{sortie}_i$ indique la profondeur de la porte de sortie de la tour $i$, et $\mathtt{entree}_i$ indique la profondeur de la porte d'entrée de la tour $i$.

Dans la liste des tours que Joseph possède, les tours ne sont pas triées dans l'ordre du cycle, mais par ordre de profondeur. C'est-à-dire que pour deux tours en position $i < j$ dans sa liste, la porte d'entrée de la tour $j$ est toujours plus profonde que la porte d'entrée de la tour $i$, et la porte de sortie de la tour $j$ est toujours plus profonde que la porte de sortie de la tour $i$.

(Cependant, la porte d'entrée de la tour $i$ peut être plus profonde que la porte de sortie de la tour $j$, on sait simplement que les profondeur des portes d'entrées est une suite croissante, pareil pour les portes de sorties.)

Joseph Nageant sait aussi que la muraille a été construite de manière intelligente, de sorte que l'on puisse en faire le tour sans trop subir de dénivelé. Plus précisément, on considère que le coût de construire un rempart qui part de la porte de sortie d'une tour $A$ à la porte d'entrée d'une tour $B$ correspond à la différence de profondeur entre les deux portes, au carré.

Aidez Joseph Nageant à trouver un arrangement des tours qui pourrait être correct, c'est-à-dire qui minimise la somme des coûts de chaque rempart.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de tours.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : sortie, la profondeur de la porte de sortie de chaque tour.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : entree, la profondeur de la porte d'entrée de chaque tour.

Sortie

Afficher, sur une première ligne, le coût minimal d'un cycle passant par toutes les tours. Puis, sur une seconde ligne, afficher dans l'ordre les tours visitées par ce cycle, séparées par un espace. Si plusieurs cycles de même coût existent, afficher n'importe lequel d'entre eux.

Attention, la réponse peut être un entier supérieur à $2^{32}$, gare aux dépassements d'entier selon le langage !

Contraintes

  • $2 \le N \le 10$
  • $0 \le \mathtt{sortie}_i \le 1\,000\,000\,000$
  • $0 \le \mathtt{entree}_i \le 1\,000\,000\,000$
  • $\mathtt{sortie}$ est une liste strictement croissante
  • $\mathtt{entree}$ est aussi une liste strictement croissante

Contraintes de performance

  • $2 \le N \le 200\,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
4
1 2 3 4
1 4 5 6
Exemple de sortie
26
0 2 3 1 0
Commentaire

Voici la matrice décrivant le coût de placer un rempart de n'importe quelle tour $i$ vers n'importe quelle tour $j$:

   i\j       0       1       2       3   
0 9 16 25
1 1 9 16
2 4 1 9
3 9 0 1

Par exemple, pour considérer un rempart de la tour 1 à la tour 2, on emprunte un la porte de sortie de profondeur 2 pour aller à la porte d'entrée de profondeur 5, pour un coût de $(2-5)^2 = 9$.

La construction de muraille optimale est de construire un rempart de la tour 0 vers la tour 2, puis vers la tour 3, puis vers la tour 1, et revenir à la tour 0, pour un coût total de $16 + 9 + 0 + 1 = 26$.

Il n'est pas possible de prendre un cycle moins coûteux, et il n'existe pas non plus d'autre cycle du même coût.

Exemple d'entrée
5
3 7 10 12 17
5 9 13 15 17
Exemple de sortie
166
0 1 3 4 2 0
Commentaire

Voici la matrice des coûts associée à cette instance du problème.

   i\j       0       1       2       3       4   
0 36 100 144 196
1 4 36 64 100
2 25 1 25 49
3 49 9 1 25
4 144 64 16 4

La muraille proposée, $(0, 1, 3, 4, 2, 0)$, coûte $36 + 64 + 25 + 16 + 25 = 166$. Cependant, il existe deux autres possibilités de muraille qui possèdent le même coût : $(0, 1, 4, 3, 2, 0)$ coûte $36 + 100 + 4 + 1 + 25 = 166$, et $(0, 2, 4, 3, 1, 0)$ coûte également $100 + 49 + 4 + 9 + 4 = 166$.

Ces trois murailles sont trois solutions valides au problème.