Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

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.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 32 000 ko.

Contraintes

  • 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.

Entrée

La première ligne de l'entrée contient 2 entiers séparés par un espace : le nombre C de couleurs de bonbons, et le nombre B de bonbons de chaque couleur.

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.

Sortie

Sur la première ligne de l'entrée, vous devez afficher un entier : le plus petit nombre de bonbons que Tom doit nécessairement gâcher, c'est à dire manger seuls.

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.

Exemple

entrée :

3 4
0 1 2 2 1 0 2 1 2 0 0 1

sortie :

2
0 0
2 3
11 4
9 5
7 7
6 8

Commentaires

Détails de la sortie

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).

Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction sera mise en ligne après la fin de l'épreuve.