Acte de grâce – Épreuve régionale 2011

Niveau 3

Énoncé

Joseph Marchand a décroché son job rêvé : gardien de prison. Aujourd'hui, il doit libérer certains prisonniers (la famille avant tout), mais ces fichus interrupteurs qu'il doit manipuler ouvrent plusieurs grilles à la fois. Par souci d'économie d'énergie, Joseph veut en actionner le moins possible. Bien entendu, il ne faut surtout pas garder sous cellule des prisonniers graciés, ni laisser sortir des prisonniers non libérés.

Entrée

  • Sur la première ligne, le nombre P de prisonniers.
  • Sur la deuxième ligne, l'acte de grâce représentant les prisonniers à libérer (le k-ième entier indique si le prisonnier n° k est gracié (1) ou non (0)).
  • Sur la troisième ligne, le nombre N d'interrupteurs.
  • Sur les N lignes suivantes, un interrupteur par ligne (le k-ième entier indique si l'interrupteur ouvre la cellule n° k (1) ou non (0)).

Sortie

  • Le nombre minimal d'interrupteurs à actionner afin de libérer tous les prisonniers graciés.

Contraintes

  • 1 <= P <= 30
  • 1 <= N <= 300

Contraintes d'exécution

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

Exemples d'entrée/sortie

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