Cargo – Qualification 2009

Level 4

Énoncé

Un avion cargo peut contenir exactement 2N conteneurs, alignés sur deux rangées de N conteneurs chacune. Chaque conteneur a un poids, et le poids d´une rangée est la somme des poids des conteneurs dans celle-ci. Pour équilibrer l'avion, on veut répartir les conteneurs dans les deux rangées de façon à ce que leur différence de poids (en valeur absolue) soit minimale. Étant donnés les poids des 2N conteneurs, écrivez un programme qui renvoie ce minimum.

Contraintes

  • 1 <= N <= 100 Chaque poids sera compris entre 0 et 2000 (inclus)

Entrée

  • Sur la première ligne, un entier : N.
  • Sur la deuxième ligne, 2*N valeurs correspondant aux poids des conteneurs, séparées chacune par un espace.

Sortie

Un entier, indiquant la différence de poids minimale (en valeur absolue) entre les deux rangées de l'avion.

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
10000 milliseconds

Input/output samples

Sample input
2
1 3 8 9
Sample output
1
Sample input
4
1000 2 3 4 5 6 7 2000
Sample output
991

Submit your solution

You have to register or log in to be able to submit your solution.