GroLopin – Qualification 2013

Niveau 1

Énoncé

Vous possédez un jeu de pin's distincts, tous composés d'un engrenage de plusieurs dents dont certaines percées d'un trou. Le laboratoire d'Okabé ne cesse de compter de nouveaux membres, et il s'attache à distribuer à chacun d'eux un de ces pin's, en respectant la contrainte suivante : la superposition de deux pin's quelconques doit toujours laisser apparaître un unique trou.

Ainsi, en cas de glissement dans une dimension parallèle, deux membres quelconques du laboratoire pourront toujours se reconnaître en vérifiant que leurs pin's respectent la propriété.

On vous demande de vérifier si l'ensemble de pin's donné respecte bien la contrainte. Il y a N membres dans le laboratoire donc N pin's à vérifier et chacun d'eux comporte M dents possibles dont certaines percées d'un trou. On vous garantit que tous les pin's ont le même nombre de trous.

Entrée

L'entrée comprendra :

  • deux nombres N et M représentant respectivement le nombre de pin's et le nombre de dents de chaque pin's.
  • sur chacune des N lignes suivantes, un pin's représenté par une chaîne de caractères avec un « o » pour un trou et une espace pour une dent intacte.

Sortie

Vous devez écrire une ligne sur la sortie standard : 1 si l'ensemble de pin's respecte la propriété, 0 sinon.

Contraintes

  • 1 <= N <= 273
  • 1 <= M <= 273

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
3 4
  oo
o o 
o  o
Exemple de sortie
1
Commentaire

Tout couple de pin's laisse toujours apparaître un unique trou après superposition, donc l'ensemble est valide.

Exemple d'entrée
4 4
o o 
o  o
 o o
oo
Exemple de sortie
0
Commentaire

Le premier et le troisième pin's n'ont pas de trou en commun. L'ensemble de pin's ne respecte donc pas la propriété.

Exemple d'entrée
3 3
o o
oo 
o o
Exemple de sortie
0
Commentaire

Le premier et le troisième pin's ont deux trous en commun. Cet ensemble est également incorrect.