Exploitation Equitable – Épreuve régionale 2020

Niveau 4

Énoncé

La Space Mining Intergalactic Company, leader intergalactique de l'extraction de minerai vient tout juste de recevoir le rapport d'exploration d'une nouvelle galaxie. Ce rapport contient le nombre de planètes et la quantité de minerai présent sur chacune d'elles.

La SMIC possède deux flottes de vaisseaux miniers et souhaiterait les charger d'extraire tout ce minerai. Cependant les équipages de ces deux flottes sont très jaloux les uns des autres.

Pour éviter de créer des tensions, la compagnie souhaiterait que les deux flottes collectent des quantités de minerai aussi proches que possible. Cependant, il reste important de ne pas gâcher de ressources: il faudra faire attention à bien récolter toutes les planètes quoi qu'il arrive.

Ainsi, en formant deux groupes de planètes, quelle est la différence minimum possible entre les sommes des quantités de minerai collectés par ces groupes ?

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : $N$, le nombre total de planètes dans cette galaxie.
  • Sur la ligne suivante, une liste de $N$, entiers séparés par des espaces : liste taille, liste des quantités respectives de minerais présents sur chacune des $N$ planètes. Ces entiers ont une taille inférieure à $M$.

Sortie

Un seul entier représentant la différence minimale possible entre la somme des quantités de minerai des deux groupes de planètes.

Contraintes

  • $1 ≤ N ≤ 80$
  • $1 ≤ M ≤ 1000$

Contraintes de performance

  • $1 ≤ N ≤ 500$
  • $1 ≤ M ≤ 1000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
5
37 7 28 27 11
Exemple de sortie
0
Commentaire

En comptant la quantité totale de minerai dans la galaxie, on obtient 110. La SMIC souhaiterait donc créer deux ensembles de planètes de taille 55 chacun, si possible. C'est en effet possible, voici ces deux groupes: A: 27, 28 B: 7, 11, 37

La différence minimale est donc de 0.

Exemple d'entrée
7
21 46 38 34 15 20 8
Exemple de sortie
2
Commentaire

En sommant les quantités de minerai de cette galaxie, on obtient 182. L'objectif est donc de faire deux groupes de taille 91. En mettant tous ses mathématiciens sur l'affaire (soit deux personnes), la SMIC découvre qu'il n'existe pas de telle répartition possible. Cependant il est possible de faire deux groupes de tailles 90 et 92: A: 15, 20, 21, 34 B: 8, 38, 46

La différence la plus faible est donc 2 (92 - 90, je vous jure que ça fait 2).