Programmation - La famille de Vito
Le site UVa Online Judge regroupe des problèmes de plusieurs concours de programmation ouvert aux étudiants. Il propose de nombreux exercices de nature algorithmique dont la résolution se fait en écrivant un programme en C, C++ ou Java qui est ensuite vérifié automatiquement sur un ensemble de données test.
Pour illustrer certains points du cours, nous vous proposerons des problèmes issus de ce site. Après la création d'un compte, vous pourrez donc soumettre vos solutions au site UVa Online Judge puis envoyer à l'adresse vergnaud@di.ens.fr votre solution (ainsi qu'une courte justification théorique) lorsque celles-ci auront été acceptées.
Problème original : Vito's family
Description
Le gangster mondialement connu Vito Deadstone déménage à New York. Il y possède une grande famille dont tous les membres habitent Lamafia Avenue. Puisqu'il compte rendre visite à ses proches, très souvent, il essaie de trouver une maison près d'eux.
Vito veut minimiser la distance totale à chacun des membres de sa famille et vous fait chanter pour écrire un programme qui résoudra son problème.
Entrée
L'entrée consiste en plusieurs cas à traiter. La première ligne contient le nombre de cas à traiter.
Pour chaque cas, vous aurez le nombre (entier) r de membres de la famille de Vito (0 < r < 500) puis les numéros de rue (également entiers) s1 , s2, ..., sr où ils habitent. Notez que plusieurs membres de la famille peuvent habiter la même rue.
Sortie
Pour chaque cas, votre programme doit retourner la somme minimale des distances de la maison de Vito optimale à chacun des membres de sa famille. La distance entre deux numéros de rue si et sj est dij = | si - sj |.
Exemple d'entrée
2 2 2 4 3 2 4 6
Exemple de sortie
2 4
