Collier de bonbons

Tom vient de s'acheter un gros collier de bonbons à la boulangerie, et s'apprête à croquer les anneaux multi-colores qui le composent. Le collier est composé de bonbons de divers goûts, chaque goût est identifié par une couleur. Mais voilà, un collier de bonbons, cela ne se mange pas n'importe-comment !

Tom mange son collier en plusieurs étapes : à chaque étape, il sélectionne une suite de bonbons consécutifs parmi ceux restant sur le collier, puis croque d'un coup tous les bonbons sélectionnés. Tom a cependant plusieurs exigences : il ne supporte absolument pas de manger ensemble des bonbons de couleurs différentes : les goûts se mélangent, et du coup, cela n'a goût de rien du tout, ou même mauvais goût. D'autre part, Tom trouve que les bonbons sont trop petits pour être croqués seuls : lorsqu'il mange un seul bonbon à la fois, il ne sent pas suffisamment le goût, et surtout, il adore faire tourner plusieurs bonbons sur sa langue. Il considère donc qu'un bonbon mangé seul est un bonbon gâché.

Votre objectif est d'aider Tom à gâcher le moins de bonbons possible de son collier, tout en ne mangeant jamais de bonbons de couleur différente en même temps.

Le sujet est décomposé en deux parties : fournir le nombre minimal de bonbons gâchés rapporte 50% des points, et décrire les étapes permettant d'arriver à ce nombre donne les 50% restants.

• 1 <= C <= 100, où C est le nombre de couleurs différentes des bonbons situés sur le collier
• 1 <= B <= 10, où B est le nombre de bonbons de chaque couleur

De plus, dans 70% des tests, C <= 20.

Les C*B entiers suivants décrivent la couleur des bonbons du collier, dans l'ordre. Les couleurs sont identifiées par des entiers de 0 à C-1 inclus.

Vous devez ensuite décrire comment Tom doit s'y prendre pour gâcher le moins possible de bonbons, en décrivant un par ligne, les groupes de bonbons qu'il doit croquer, dans l'ordre.

Pour identifier les bonbons à manger, on les numérote 0 à C*B-1 dans l'ordre dans lequel ils sont fournis au départ.

Chaque ligne doit contenir deux entiers P et Q séparés par un espace : les numéro du premier et du dernier bonbon du groupe qu'il doit manger à cette étape. Si P <= Q, le groupe est composé de tous les bonbons restant sur le collier, dont le numéro est compris entre P et Q inclus. Sinon, le groupe est composé de tous les bonbons dont le numéro est soit supérieur ou égal à P, soit inférieur ou égal à Q.

S'il y a plusieurs manières possibles de gâcher le nombre minimal de bonbons, afficher l'une d'entre-elles, au choix.

Pour ne gâcher que 2 bonbons au total, Tom peut commencer par manger le bonbon 0 (de couleur 0) seul, et le gâcher.

Il mange ensuite les bonbons 2 et 3, de couleur 2, puis les bonbons restant entre 11 et 4, soit 11, 1 et 4, tous de couleur 1, puis les bonbons 9, 10 et 5, de couleur 0. Il gâche alors le bonbon 7 de couleur 1, en le mangeant seul, puis termine par les bonbons 6 et 8, de couleur 2.

La figure ci-dessous représente les différentes étapes de cet exemple.

Score :

Pour chaque test, vous obtiendrez 50% des points si le nombre de bonbons gâchés est le bon, et les 50% restants si l'ensemble des étapes à suivre pour atteindre ce nombre est correct (en supposant que vous l'avez fourni).