Oyez Oyez !

Aujourd’hui pour vos yeux ébahis, je vous propose une petite épreuve qui va réveiller vos neurones, tiré du Google Code Jam (Round 3 2010).

Tous les langages sont acceptés (même MATLAB si ça vous tente ), le principe c'est de s'amuser tout en apprenant, si vous avez des remarques, des idées n'hésitez pas à poster aussi, on est entre nous...

Problème : Prolifération de Hot Dog

Le problème est donc le suivant :

(Ceux qui trouvent l'histoire pourrie, vous pouvez poster vos réclamations chez Google )
Un certain nombre de vendeurs de hot-dogs ont commencé à vendre des hot-dogs dans les angles (intersections) le long d'une très longue rue est-ouest. Le problème c'est que plusieurs vendeurs pourraient vendre sur le même angle, ils occuperaient alors le même marché. Tout n'est pas perdu cependant ! Les vendeurs de hot-dogs ont un plan.

Si jamais il y a deux ou plusieurs vendeurs aux même angle, alors exactement deux des vendeurs peuvent effectuer un déménagement, ce qui signifie:

Un vendeur se déplace d'un coin plus à l'est le long de la rue. L'autre vendeur se déplace d'un angle plus à l'ouest le long de la rue. Rappelez-vous que la rue est très longue, il n'y a donc aucun danger de manquer d'angle. Compte tenu des positions de départ de tous les vendeurs de hot-dogs, vous devriez trouver le nombre minimum de coups dont ils ont besoin pour que les vendeurs soient tous séparés (ce qui signifie qu'ils sont tous sur différents coins).

Par exemple, supposons que la rue commence avec le nombre suivant de vendeurs de hot-dog à chaque coin, classés par ordre d'ouest en est:

... 0 0 2 1 2 0 0 ...
Ensuite, les vendeurs peuvent être séparés en trois coups, comme indiqué ci-dessous:

... 0 0 2 1 2 0 0 ...
.........|
.........+--- Mouvement ici

... 0 1 0 2 2 0 0 ...
............|
............+--- Mouvement ici

... 0 1 1 0 3 0 0 ...
...............|
...............+--- Mouvement ici

... 0 1 1 1 1 1 0 ...
Si vous voulez, vous pouvez donner le temps que votre programme aura mis pour trouver les réponses

Voici les jeux d’essais, un simple et un plus complexe.

Chaque coin de rue est marqué par un nombre entier, positif ou négatif. Pour chaque i, i +1 coin se réfère à l'autre coin à l'est du coin i. Nous allons utiliser ce système d'étiquetage pour décrire les coins dans le fichier d'entrée.

La première ligne du fichier d'entrée contient le nombre de cas, T cas de test. Chaque cas commence par le nombre C d'angles qui ont au moins un vendeur de hot-dog dans la configuration de départ. Les C lignes suivantes contiennent chacun une paire de nombres entiers séparés par des espaces P, V, indiquant qu'il existe V vendeurs à l'angle P.

C-small-practice
C-large-practice

J'attends vos réponses