Dans les monts de Kalos, Violette et vous venez de découvrir un lieu contenant de très nombreux Pokémons, rangés en file.
Après négociations avec Violette, vous décidez de vous partager équitablement le groupe de Pokémons. Mais chaque membre de ce groupe est particulièrement lié à ses deux voisins, de droite et de gauche (les Pokémons du bout n'ont qu'un seul voisin).
Vous cherchez donc à vous partager équitablement ces Pokémons, en brisant la chaîne le moins souvent possible.
L'objectif est donc de réaliser moins d'un certain nombre de groupes, de manière à ce qu'en prenant chacun un groupe sur deux, vous ayez chacun les mêmes Pokémons au final.
Le nombre de groupes maximum est donné en entrée, ainsi que la liste des Pokémons.
Pour valider, donnez le nombre de Pokémons par groupe constitué (dans l'ordre).
Exemple
Imaginons que la liste des Pokémons soit :
Ptitard, Ptitard, Ptitard, Ptitard,
Sorboul, Blizzi, Blizzi, Blizzi,
Sorboul, Blizzi, Sorboul, Sorboul
Ce qu'on peut écrire :
P, P, P, P, S, B, B, B, S, B, S, S
Si le nombre de groupes maximum était 4, une solution acceptable serait :
P, P | P, P, S, B, B | B, S, B, S | S
En prenant, alternativement, chacun un groupe, vous auriez finalement les mêmes Pokémons :
P, P | B, S, B, S pour vous,
P, P, S, B, B | S pour Violette.
La solution au problème du partage peut être indiquée en donnant le nombre de Pokémons dans chaque groupe.
Dans cet exemple, seule la solution 2, 5, 4, 1 serait donc acceptable.
Autre exemple.
Si l'énoncé était :
P, P, S, S, P, B, B, B, S, B, S, P
avec la contrainte de faire au plus 4 groupes, il y aurait plusieurs solutions possibles :
1, 6, 5(il y a moins de 4 groupes),1, 1, 5, 52, 5, 4, 1,3, 3, 3, 3,3, 4, 3, 2,4, 1, 2, 5,4, 2, 2, 4.
