Pyramide maudite – Épreuve régionale 2015

Niveau 7

Énoncé

Jadis, la pyramide de Quuxfootl était réputée maudite : les passants qui s'y égaraient se retrouvaient égarés dans des galeries semblant être mues par une force vitale, le chemin qu'ils avaient pris pour arriver se refermant derrière eux.

De récentes recherches archéologiques ont révélé le mécanisme employé par les prêtres pour effrayer les intrus : ils commandaient, par des interrupteurs, les tunnels du complexe pyramidal ; chaque interrupteur était relié à deux galeries, et selon sa position, l'une s'ouvrait alors que l'autre était fermée. (Les Mésoaméricains n'ayant pas connaissance du circuit va-et-vient malgré leurs connaissances sophistiquées en mécanique, deux interrupteurs n'étaient jamais reliés à un même tunnel.)

Le professeur Marchand a remarqué que quand les interrupteurs sont tous en position basse, deux chambres sont toujours reliées par un unique chemin simple empruntant les galeries ouvertes. Il se demande si cette propriété reste vraie quelle que soit la position des interrupteurs.

Pour répondre à sa question, il vous fournit un plan du complexe pyramidal (c'est un multigraphe : deux chambres peuvent être reliées par plusieurs tunnels) et, pour chaque interrupteur, une paire (a,b)a est le tunnel ouvert lorsque l'interrupteur est en position basse (b étant alors fermé), et b est ouvert lorsque l'interrupteur est en position haute (a étant alors fermé). Les paires sont disjointes. Les tunnels qui ne sont commandés par aucun interrupteur sont tout le temps ouverts.

Entrée

L’entrée comprendra :

  • sur la première ligne, 3 entiers séparés d’une espace : le nombre de chambres, de tunnels et d'interrupteurs, respectivement notés nc, nt et ni
  • sur chacune des nt lignes suivantes, la description d'un tunnel : deux entiers séparés d'une espace donnent les numéros des chambres aux deux extrémités du tunnel
  • sur chacune des nc lignes suivantes, la description d'un interrupteur : les deux tunnels qu'il commande sont identifiés par leurs deux numéros séparés d'une espace

Les chambres sont numérotées de 0 à nc - 1 ; les tunnels sont numérotés de 0 à nt - 1 selon l'ordre dans lequel leurs descriptions sont fournies.

Sortie

Vous afficherez en sortie :

  • 1 si la condition demandée est bien satisfaite par tous les multigraphes induits par sélection d'une arête sur deux dans chaque paire ;
  • 0 sinon.

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

dessin : 2 segments appariés entre deux points

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

Lorsque l'unique l'interrupteur est en position basse, les deux salles sont reliés par un tunnel, c'est bon (comme garanti par l'énoncé). Par contre, en position haute, la condition est doublement violée :

  • il est impossible de rejoindre une salle depuis l'autre
  • il y a deux chemins simples pour aller de la salle 1 jusqu'à elle-même : le chemin nul (rester sur place) et le chemin empruntant la boucle
Exemple d'entrée
3 4 2
0 2
1 2
0 1
1 0
0 2
1 3
Exemple de sortie
0
Commentaire

On voit sur cet exemple qu'une seule configuration des interrupteurs pose problème : celle où ils sont tous deux en position haute, auquel cas on a une boucle entre les salles 0 et 1 et la salle 2 est inaccessible.

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

dessin : carré apparié + diagonale non appariée