Le Juste Échafaudage – Qualification 2025

Niveau 5 ⋅ Validation weight: 15%

Énoncé

Joseph Nageant dispose enfin de toutes les informations dont il a besoin pour s'immiscer dans la forteresse sous-marine ! Pour pouvoir accéder à l'intérieur des remparts, il tente de construire un échafaudage en vitesse pour s'infiltrer par une meurtrière, en se faisant passer pour un ouvrier.

Joseph Nageant dispose de $N$ barres de tailles variables pour construire son échafaudage sur $K$ étages.

Pour chaque étage de l'échafaudage, Joseph Nageant doit sélectionner deux barres de taille $i$ et $j$ parmi les barres à sa disposition. Le déséquilibre de son échafaudage est alors augmenté de $|i - j|$, où $|\cdot|$ représente la valeur absolue.

Déterminez le déséquilibre minimal que Joseph peut obtenir pour un échafaudage de $K$ étages.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de barres.
  • Sur la ligne suivante, un entier : K, le nombre d'étages à construire.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : barres, la taille des barres.

Sortie

Afficher, sur une ligne, le déséquilibre minimal possible pour construire son échaufadage.

Contraintes

  • $2 \le N \le 50$
  • $1 \le K \le \left\lfloor\frac{N}{2}\right\rfloor$
  • $1 \le \mathtt{barres}_i \le 1\,000\,000\,000$

Contraintes de performance

  • $2 \le N \le 1\,000\,000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
7
2
1 4 5 5 6 9 12
Exemple de sortie
2
Commentaire

Joseph Nageant peut utiliser une barre de taille 4 et une barre de taille 5 pour construire le premier étage de l'échafaudage, ainsi qu'une barre de taille 5 et une barre de taille 6 pour construire le second étage de l'échafaudage. Le déséquilibre total est alors de $|5 - 4| + |6 - 5| = 2$.

Il est impossible d'obtenir un déséquilibre plus faible. Cependant, il existe d'autres manières d'obtenir le même déséquilibre (par exemple, en sélectionnant (5, 5) et (4, 6), on obtient également un déséquilibre total de 2)

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

Joseph Nageant peut utiliser une barre de taille 1 et une barre de taille 3 pour construire le premier étage de l'échafaudage, ainsi qu'une barre de taille 4 et une barre de taille 6 pour construire le second étage de l'échafaudage. Le déséquilibre total est alors de $|1 - 3| + |4 - 6| = 4$.

Il est impossible d'obtenir un déséquilibre plus faible.