Généalogie Divine – Qualification 2021

Level 2

Énoncé

En fouillant dans son grenier, Joseph Marchand est tombé sur un ancien jeu de carte. Disposant de temps libre pendant son confinement, Joseph décide de lancer une soirée jeu de société en famille.

Le jeu est similaire à celui des '7 familles', à ceci près qu'il concerne les divinités grecques. Comme dans le jeu des '7 familles', chaque joueur doit rassembler suffisamment de cartes pour compléter un ensemble donné. L'arbre généalogique des divinités grecques est toutefois un peu complexe, donc certains membres apparaissent dans le jeu dans différentes familles.

Joseph est un peu perdu pendant la partie et a du mal à se retrouver dans toutes ces familles entremêlées ! Le but est de l'aider à trouver le plus petit nombre de cartes manquantes pour compléter une famille et ainsi gagner la partie.

Entrée

L'entrée contiendra :

  • Sur la première ligne, un entier : $f$, le nombre de familles.
  • Sur la ligne suivante, un entier : $m$, le nombre de membres par famille.
  • Sur les lignes suivantes, une liste de $f$ éléments : $familles$, les différentes familles possible dans le jeu.
    • Une ligne par élément de la liste : une liste de $m$ caractères juxtaposés.
  • Sur la ligne suivante, un entier : $c$, le nombre de cartes dans la main de Joseph.
  • Sur la ligne suivante, une liste de $c$ caractères juxtaposés : $cartes$, les cartes dans la main de Joseph.

Sortie

Afficher le nombre minimal de carte nécessaire à Joseph pour compléter une famille. $0$ si une famille est déjà complétée.

Contraintes

  • $1 ≤ f ≤ 100$
  • $1 ≤ m ≤ 26$
  • $0 ≤ c ≤ 26$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4
5
GSRZD
ZHEPD
CGPOR
GZLAI
6
ZPAOLG
Sample output
1
Note

D'après la main de Joseph, voici l'état des familles possibles :

C'est donc la dernière famille qui est la plus complète, avec seulement $1$ carte manquante.

Submit your solution

You have to register or log in to be able to submit your solution.