Le Juste Semblable – Qualification 2025

Niveau 2 ⋅ Validation weight: 100%

Énoncé

Joseph se trouve près de l'entrée principale de la ville. Afin d'y entrer sans être démasqué, il va tenter de se faufiler dans une flotte de sous-marins.

Pour entrer, chaque sous-marin peut passer seulement s'il est accompagné d'un autre sous-marin partageant les mêmes critères.

Il y a $N$ sous-marins et chaque sous-marin possède $M$ critères (couleur, forme, sièges chauffants…) représentés par une suite de 0 ou 1. Deux sous-marins sont compatibles s'ils partagent exactement les mêmes critères, c'est-à-dire que leurs suites de critères sont identiques.

Les sous-marins ne peuvent entrer dans l'enceinte de la ville que deux par deux, et uniquement si les deux sous-marins sont compatibles.

Le but est de trouver le nombre minimum de sous-marins qui ne trouveront pas de paire compatible, et qui ne pourront donc pas entrer.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de sous-marins.
  • Sur la ligne suivante, un entier : M, le nombre de critères.
  • Sur les lignes suivantes, une liste de N éléments : criteres, les critères de chaque sous-marin.
    • Une ligne par élément de la liste : une liste de M entiers séparés par des espaces.

Sortie

Afficher le nombre minimum de sous-marins qui ne pourront pas entrer dans la ville.

Contraintes

  • $1 \le N \le 1\,000$
  • $1 \le M \le 1\,000$
  • $\mathtt{criteres}_{i,j} \in {0, 1}$

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
4
3
1 1 0
1 0 1
1 0 1
0 0 0
Exemple de sortie
2
Commentaire

Il y a 4 sous-marins (A, B, C, D) qui ont chacun 3 caractéristiques (1, 2 et 3).

  • A a comme caractéristique 1 et 2 mais n'a pas la caractéristique 3.
  • B et C ont les caractéristiques 1 et 3 mais pas la 2.
  • D n'en a aucune.

B et C sont compatibles et peuvent donc entrer dans la ville ensemble, tandis que les autres 2 sous-marins seront sans couple, ici A et D. On affiche donc le nombre de sous-marins qui ne peuvent entrer, c'est-à-dire 2 (A et D).

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

Il y a 7 sous-marins (A, B, C, D, E, F, G) ayant chacun 2 caractéristiques différentes (1 et 2).

  • A, B et D ont la caractéristique 2, mais pas la 1.
  • C, E et F ont la caractéristique 1, mais pas la 2.
  • G n'en a aucune.

Quelle que soit la manière d'arranger les couples, entre A, B ou D il y aura au mieux un seul sous-marin sans couple. Pareillement pour C, E ou F. Enfin, G sera nécessairement seul.

Il y a donc au mieux 3 sous-marins seuls qui ne pourront pas entrer.

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

Il y a 6 sous-marins (A, B, C, D, E et F) ayant 3 caractéristiques chacun (1, 2 et 3).

Il est possible de former 3 couples :

  • A avec C.
  • B avec E.
  • D avec F.

Tous les sous-marins peuvent entrer dans la ville.