Les Fouinettes sont connus pour leur manière de monter la garde. Ils se répartissent le territoire, et lorsqu'un Fouinette donne l'alerte, il pousse un cri qui prévient ses voisins. À leur tour, les voisins poussent un cri, prévenant leur propres voisins. Au bout d'un moment, tous les Fouinettes de la région sont au courant de l'alerte.
Entre le moment où un Fouinette donne l'alerte, et le moment où ses voisins immédiats la donnent à leur tour, il s'écoule une seconde. Vous allez devoir déterminer, connaissant le voisinage de chaque Fouinette, combien de temps il s'écoulera entre le moment où le premier Fouinette donne l'alerte, et le moment où tous les Fouinettes sont au courant du danger, dans le pire des cas.
Voici un exemple. Pour simplifier, on numérote les Fouinettes de 1 à 8. Pour chaque Fouinette, on indique les numéros des Fouinettes qui sont voisins immédiats :
1: 2, 4, 6
2: 1, 3
3: 2, 4, 5
4: 1, 3, 5
5: 3, 4
6: 1, 7, 8
7: 6
8: 6
Notez que le voisinage est cohérent : si 2, 4 et 6 sont voisins de 1, alors 1 est effectivement voisin de 2, 4 et 6.
Voyons ce qui se produit si 2 soupçonne un danger. Il sonne l'alerte à t=0. À t=1, 1 et 3 sont sur le qui-vive. Les Fouinettes 1 et 3 donnent à leur tour l'alerte et une seconde plus tard, à t=2, les Fouinettes 4, 5 et 6 sont au courant du danger. Ces derniers donnent l'alerte, et à t=3, les deux derniers Fouinettes, 7 et 8 sont alertés (par le Fouinette 6 dans ce cas) Par conséquent, si c'est le Fouinette 2 qui sonne l'alerte, tout le monde sera prévenu en 3 secondes. Et les derniers au courant seront les Fouinettes 7 et 8.
Est-ce qu'il y a une situation pire que ces 3 secondes ? La réponse est oui. Dans certains cas, il s'écoulera 4 secondes entre le moment où le premier Fouinette donne l'alerte et le cas où tout le monde est prévenu. Cela se produira si un des Fouinettes 3, 5, 7 ou 8 sont alertés les premiers. Dans le cas où c'est le Fouinette 3 ou 5 qui donne l'alerte, alors les Fouinettes 7 et 8 ne le sauront que 4 secondes plus tard, et inversement.
Pour le voisinage des Fouinettes donné plus haut, on peut donc affirmer que dans le pire des cas, l'alerte est donnée en 4 secondes
et que les Fouinettes en position critique sont 3, 5, 7 et 8. Il faut donner toutes ces informations pour valider le défi : le temps
maximum, en premier, suivi des numéros des Fouinettes en position critique : 4, 3, 5, 7, 8.
