File d'attente – Épreuve régionale 2023

Niveau 2

Énoncé

L'architecte ayant terminé ses occupations, il indique aux aventuriers de précieuses informations leur permettant de se repérer dans le temps. Supposant qu'il s'agissait simplement d'un problème de précision lors du placement du dernier point de contrôle, Valérian et Oscar tentent alors d'effectuer un déplacement relatif pour arriver à la bonne année. Oscar consulte de nouveau son manuel, effectue les calculs d'encodage, et indique à Valérian la combinaison à effectuer pour arriver à l'année désirée. L'indicateur temporel s'agite, puis s'arrête à nouveau, mais l'année indiquée n'est toujours pas compréhensible. Seraient-ils alors toujours en Antiquité ? Pendant que Valérian et Oscar continuent leurs investigations sur la cause de ces erreurs, les autres jeunes ressortent de la machine pour évaluer leur avancée temporelle.

Les jeunes croisent alors N soldats en file indienne, tous chargés comme des mules. En écoutant les conversations, ils comprennent alors que ces soldats se préparent pour la bataille de Marathon ! Pour en être certain, ils aimeraient interroger les soldats, mais ces derniers sont malheureusement trop occupés pour pouvoir les aider.

Alors Cyril remarque que les soldats en tête de file prennent quelques temps pour déposer leur matériel. En fait, il s'aperçoit même que les soldats mettent autant de secondes à déposer leur matériel que de kilogrammes de matériel qu'ils portaient. Il lui vient alors l'idée de les réordonner pour leur faire gagner du temps.

Le temps d'attente d'un soldat est égal au temps total que mettent tous les soldats devant lui à déposer leur matériel. Le soldat en tête de file aura donc un temps d'attente de 0, le second soldat aura un temps d'attente égal à la charge en kilogrammes du soldat en tête de file, le soldat suivant un temps d'attente égal à la charge des deux premiers soldats, et ainsi de suite. Le temps d'attente cumulé total est égal à la somme des temps d'attente de tous les soldats. Étant donné les charges en kilogrammes de tous les soldats, aidez Cyril à trouver le meilleur ordre possible pour les soldats afin de minimiser le temps d'attente cumulé total !

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de soldats.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : charges, la liste des poids du matériel de chaque soldat, en kilogrammes.

Sortie

Afficher le temps d'attente cumulé total minimal après avoir réordonné les soldats.

Contraintes

  • $1 \le N \le 10$
  • $1 \le $charges$_i \le 100$

Contraintes de performance

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

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
4
10 3 5 7
Exemple de sortie
26
Commentaire

Quatre soldats sont actuellement en file indienne :

  • Le premier soldat est chargé de 10 kg de matériel
  • Le deuxième soldat est chargé de 3 kg de matériel
  • Le troisième soldat est chargé de 5 kg de matériel
  • Le quatrième soldat est chargé de 7 kg de matériel

Si on ne change pas leur ordre :

  • Le temps d'attente du premier soldat sera de 0 seconde
  • Le temps d'attente du deuxième soldat sera de 10 secondes
  • Le temps d'attente du troisième soldat sera de 13 secondes
  • Le temps d'attente du quatrième soldat sera de 18 secondes

Le temps d'attente cumulé total sera donc de $0 + 10 + 13 + 18 = 41$ secondes.

Cependant, en mettant en premier le soldat chargé de 3 kg, en deuxième le soldat chargé de 5 kg, en troisième le soldat chargé de 7 kg et en dernier le soldat chargé de 10 kg, on aura alors:

  • 0 seconde d'attente pour le premier soldat
  • 3 secondes d'attente pour le deuxième soldat
  • 8 secondes d'attente pour le troisième soldat
  • 15 secondes d'attente pour le dernier soldat

Le temps cumulé total sera alors de 26 secondes. Il s'agit du plus petit temps cumulé total possible à obtenir, c'est donc la réponse à afficher.

Exemple d'entrée
3
1 3 19
Exemple de sortie
5
Commentaire

Trois soldats sont actuellement en file indienne :

  • Le premier soldat est chargé d'1 kg de matériel
  • Le deuxième soldat est chargé de 3 kg de matériel
  • Le troisième soldat est chargé de 19 kg de matériel

Si on ne change pas leur ordre :

  • Le temps d'attente du premier soldat sera de 0 seconde
  • Le temps d'attente du deuxième soldat sera d'1 seconde
  • Le temps d'attente du troisième soldat sera de 4 secondes

Le temps d'attente cumulé total sera donc de $0 + 1 + 4 = 5$ secondes.

Il n'est en fait pas possible d'obtenir un meilleur temps d'attente cumulé total. La réponse à afficher est donc 5.