Assemblage de clés – Épreuve régionale 2022

Niveau 2

Énoncé

Une autre porte se présente, verrouillée par $N$ serrures. Votre objectif va être de déverrouiller un maximum de serrures simultanément. Cependant, toutes les clés de ces serrures ont été coupée en $P$ morceaux.

Chaque serrure et chaque partie de clé possède un type $i$. Pour ouvrir une serrure, il est donc nécessaire de reformer une clé du même type en rassemblant tous les morceaux correspondants.

Les serrures ainsi que chaque partie de clé sont ordonnées par ordre de type.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de serrures.
  • Sur la ligne suivante, un entier : P, le nombre de parties nécessaires pour composer une clé.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : serrures, le type de chaque serrure.
  • Sur les lignes suivantes, une liste de P éléments : cles, les différentes parties des clés.
    • Une ligne par élément de la liste : une liste de N entiers séparés par des espaces.

Sortie

Afficher, sur une première ligne, le nombre de serrures ouvrables simultanément. Sur une deuxième ligne, afficher, séparés par des espaces, le type de chaque serrure qui peut être ouverte, par ordre croissant de leur type.

Contraintes

  • $1 \le N \le 1\,000$
  • $1 \le P \le 10$
  • Il est garanti qu'au moins une serrure peut être ouverte.
  • $-1\,000\,000 \le t \le 1\,000\,000$, $t$ étant le type d'une serrure ou d'une partie de clé.

Contraintes de performance

  • $1 \le P \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
5
2
2 3 5 5 11
5 7 9 11 13
-1 2 2 5 5
Exemple de sortie
1
5
Commentaire

Porte d'entrée

La serrure de type 2 ne peut pas être ouverte, car malgré le fait qu'il existe deux parties de clés de type 2, ces deux parties sont de même forme et ne peuvent donc pas être combinées ensemble.

Il est possible de combiner chaque partie de type 5 afin de former une clé pouvant ouvrir une serrure typée 5. C'est en fait la seule serrure qu'il est possible d'ouvrir. Il n'est pas possible d'ouvrir les deux serrures de type 5 simultanément, car il aurait fallu pouvoir former deux clés de type 5.

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

Des deux serrures de type -1, il n'est possible d'en ouvrir qu'une, car vous disposez d'au moins une partie de clé de type -1 de chaque forme, mais pas de deux.

Vous ne pouvez pas ouvrir la serrure de type 0, car vous ne disposez pas de partie de clé intermédiaire de type 0.

Vous pouvez ouvrir deux des trois serrures de type 1, car vous disposez d'au moins deux parties de clé de type 1 de chaque forme.

Au total, vous pourrez ouvrir simultanément 3 serrures.