Joseph Maçon – Épreuve régionale 2025

Niveau 6 ⋅ Validation weight: 20%

Énoncé

Joseph Marchand et sa bande, ayant enfin semé les deux gardes à l'entrée de la tour, y entrent enfin ! Pour être sûrs de ne pas être dérangés, Joseph Maçon propose alors de barricader l'entrée.

Joseph Maçon tente alors de construire un mur pour barricader l'entrée.

Ce mur est composé de briques colorées, dont la couleur est décrite par un triplet $(\mathtt{rouge}, \mathtt{vert}, \mathtt{bleu})$. Pour des raisons esthétiques, Joseph tente d'effectuer un joli dégradé avec les couleurs des briques. Plus précisément :

  • Les briques tout en bas, posées au sol, doivent être de couleur $(1, 1, 1)$
  • Les briques tout en haut, au sommet du mur, doivent être de couleur $(C, C, C)$
  • On ne peut poser une brique sur une autre brique que si la couleur de la brique supérieure est :
    • la même que la brique inférieure pour deux des trois composantes de la couleur
    • de 1 supérieure à la brique inférieure pour la composante restante.

Par exemple, sur une brique de couleur $(1, 2, 3)$, Joseph peut poser une brique de couleur $(2, 2, 3)$, $(1, 3, 3)$ ou $(1, 2, 4)$.

Étant donné la quantité de briques que Joseph possède pour certaines couleurs, déterminer la plus grande largeur de mur que Joseph peut construire.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de couleurs de briques différentes disponibles.
  • Sur la ligne suivante, un entier : C, l'intensité des couleurs désirée pour le sommet de la tour.
  • Sur les lignes suivantes, une liste de N éléments : briques, la liste des briques.
    • Une ligne par élément de la liste : séparés par des espaces, un entier quantite (le nombre de briques de cette couleur), un entier rouge (la quantité de rouge dans la couleur de la brique), un entier vert (la quantité de vert dans la couleur de la brique), et un entier bleu (la quantité de bleu dans la couleur de la brique).

Sortie

Afficher, sur une première ligne, la largeur maximale d'un mur que peut construire Joseph. Puis, pour chaque couleur de brique, dans le même ordre que la liste des briques données en entrée, afficher sur une ligne un entier : le nombre de briques de cette couleur qui seront utilisées pour le mur.

Si plusieurs solutions existent, afficher n'importe laquelle d'entre elles.

Contraintes

  • $1 \le N \le 15$
  • $1 \le C \le N$
  • $1 \le \mathtt{quantite} \le 15$
  • $1 \le \mathtt{rouge} \le C$
  • $1 \le \mathtt{vert} \le C$
  • $1 \le \mathtt{bleu} \le C$

Contraintes de performance

  • $1 \le N \le 10\,000$
  • $1 \le \mathtt{quantite} \le 1\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
2
2 1 1 1
2 1 1 2
1 1 2 1
1 1 2 2
1 2 2 1
3 2 2 2
Exemple de sortie
2
2
1
1
1
1
2
Commentaire

Dans cet exemple, Joseph dispose d'un total de 10 briques de 6 couleurs différentes pour construire notre mur. Plus précisément, Joseph dispose de :

  • 2 briques de couleur $(1, 1, 1)$
  • 2 briques de couleur $(1, 1, 2)$
  • 1 brique de couleur $(1, 2, 1)$
  • 1 brique de couleur $(1, 2, 2)$
  • 1 brique de couleur $(2, 2, 1)$
  • 3 briques de couleur $(2, 2, 2)$

En disposant ses briques comme ceci :

mur

Joseph parvient à créer un mur de 2 de largeur, respectant toutes les contraintes décrites dans l'énoncé. Il n'est pas possible pour Joseph de créer un mur plus large avec les briques à sa disposition.

Exemple d'entrée
11
3
1 3 1 2
2 2 2 2
5 2 1 2
5 3 2 2
7 1 2 2
7 2 3 2
11 3 3 3
12 1 1 1
13 1 1 2
13 1 3 2
14 3 3 2
Exemple de sortie
10
1
2
3
3
7
7
10
10
10
7
10
Commentaire

En disposant ses briques comme ceci :

mur

Joseph parvient à créer un mur de 10 de largeur, respectant toutes les contraintes décrites dans l'énoncé. Il n'est pas possible pour Joseph de créer un mur plus large avec les briques à sa disposition.