Propagation Amicale – Qualification 2026

Niveau 3 ⋅ Validation weight: 20%

Énoncé

Joseph cherche à présent à comprendre comment se forment les liens de confiance entre les robots.

Joseph possède la liste des $N$ robots existants. Chaque robot possède un prénom et un nom.

Les robots peuvent être de deux types :

  • Les robots prénomials sont en relation avec tous les robots qui partagent le même prénom ;
  • Les robots nomials sont en relation avec tous les robots qui partagent le même nom.

Chaque robot possède également un indice d'amitié $\text{seuil}$. Joseph peut former un lien de confiance avec un robot si et seulement si il possède déjà un lien de confiance avec au moins $i$ de ses relations.

Chaque jour au matin, Joseph peut demander à former un lien de confiance avec les robots de son choix. Le soir, les robots pour lesquels les conditions sont remplies acceptent de former le lien de confiance.

Aidez Joseph à déterminer, pour chaque robot, en combien de jours il peut former un lien de confiance avec lui.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de robots.
  • Sur les lignes suivantes, une liste de N éléments : robots, la liste des descriptions des robots
    • Une ligne par élément de la liste : séparés par des espaces, d'abord le prénom (maximum 16 caractères), ensuite le nom (maximum 16 caractères), puis le type du robot (P pour un robot prénomial, N pour un robot nomial) et finalement un entier seuil, le nombre de relations en commun nécessaire avant que le robot n'accepte notre demande de lien.

Sortie

Afficher, sur une ligne et séparés par un espace, le nombre minimal de jours nécessaires pour former un lien de confiance avec chaque robot. S'il est impossible de former un lien de confiance avec un robot, afficher -1.

Contraintes

  • $1 \le N \le 20$
  • $0 \le \text{seuil} \le N$

Contraintes de performance

  • $1 \le N \le 100\,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
7
Alfred Albert P 0
Bob Albert N 1
Bob Bertrand P 2
Bob Calvente P 1
Charles Bertrand N 3
Charles Calvente P 2
Didier Calvente N 2
Exemple de sortie
1 2 4 3 -1 -1 -1
Commentaire

Voici à quoi ressemblent les relations avant l'arrivée de Joseph.

graphe_1

Le premier jour, Joseph peut former un lien de confiance avec Alfred Albert, qui accepte le soir même sans condition.

graphe_2

Le deuxième jour, on peut former un lien de confiance avec Bob Albert, car nous avons à présent une relation en commun avec lui : Alfred Albert. En effet, Bob Albert est un robot nomial, et Bob Albert et Alfred Albert partagent le même nom, donc notre lien de confiance avec Alfred Albert nous permet d'atteindre Bob Albert.

graphe_3

Le troisième jour, on peut former un lien de confiance avec Bob Calvente, car Bob Calvente est un robot prénomial, et nous avons donc à présent une relation en commun avec lui (Bob Albert, qui partage le même prénom).

graphe_4

Le quatrième jour, on peut finalement former un lien de confiance avec Bob Bertrand, qui est un robot prénomial car nous avons à présent deux relations en commun avec lui : Bob Albert et Bob Calvente, qui partagent le même prénom que Bob Bertrand.

graphe_5

Malheureusement, il nous est impossible de former un lien de confiance avec Charles Bertrand, Charles Calvente et Didier Calvente. On affiche alors "-1" pour eux.

Exemple d'entrée
8
Antoine Arnold P 0
Baptiste Arnold N 1
Baptiste Balatro P 3
Baptiste Canard P 2
Baptiste Doette N 1
Charlie Balatro N 0
Charlie Doette P 1
Didier Doette P 1
Exemple de sortie
1 2 5 4 3 1 2 -1
Commentaire

Voici à quoi ressemblent les relations avant l'arrivée de Joseph.

graphe_1

Le premier jour, Joseph peut former un lien de confiance avec Antoine Arnold et Charlie Balatro, qui acceptent le soir même sans condition.

graphe_2

Le deuxième jour, on peut former un lien de confiance avec Baptiste Arnold et Charlie Doette, car nous avons à présent une relation en commun avec eux (Baptiste Arnold, robot nomial, est en relation avec Antoine Arnold, qui partage le même nom ; et Charlie Doette robot prénomial, est en relation avec Charlie Balatro, qui partage le même prénom).

graphe_3

Le troisième jour, on peut former un lien de confiance avec Baptiste Doette, car nous avons à présent une relation en commun avec lui (Charlie Doette, qui partage le même nom).

graphe_4

Le quatrième jour, on peut former un lien de confiance avec Baptiste Canard, car nous avons à présent deux relations en commun avec lui : Baptiste Arnold et Baptiste Doette, qui partagent le même prénom.

graphe_5

Le cinquième jour, on peut finalement établir un lien de confiance avec Baptiste Balatro, car nous avons enfin trois relations qui partagent le même prénom que lui : Baptiste Arnold, Baptiste Canard et Baptiste Doette.

graphe_6

Malheureusement, il nous est impossible de former un lien de confiance avec Didier Doette, car aucun robot ne partage son prénom. On affiche alors "-1" pour lui.