Maladie Maléfique – Épreuve régionale 2024

Niveau 5 ⋅ Validation weight: 10%

Énoncé

Lors du déclenchement du Ragnarök, les morts seront rappelés à la vie pour combattre. La déesse Hel, qui règne sur Helheim, le royaume des morts, grâcie certains guerriers décédés pour les autoriser à combattre lors de cette ultime bataille.

Cependant, une malédiction s'est propagée dans Helheim : une maladie contamine certains guerriers et empêche la déesse de les ressusciter. Chacun des morts doit désigner, à son arrivée dans Helheim, un guerrier qu'il souhaite maudire s'il est touché par la maladie. Chaque année, les guerriers qui étaient malades guérissent, mais transmettent alors la maladie à la personne qu'ils avaient désigné.

La déesse souhaite, s'il est possible, ressusciter l'ensemble des guerriers qu'elle a graciés pour aller combattre lors du Ragnarök. Aidez Jøsëf à lui indiquer le nombre d'années qu'elle devra attendre avant de pouvoir ressusciter l'ensemble des guerriers qu'elle a choisis.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : nombre personnes, le nombre de personnes présentes dans Helheim.
  • Sur la ligne suivante, un entier : nombre gracies, le nombre de personnes qui pourront être libérées du Helheim.
  • Sur la ligne suivante, une liste de nombre gracies entiers séparés par des espaces : gracies, liste des personnes qui pourront être libérées.
  • Sur la ligne suivante, un entier : nombre malades, le nombre de personnes qui sont actuellement malades.
  • Sur la ligne suivante, une liste de nombre malades entiers séparés par des espaces : malades, la liste des personnes qui sont actuellement malades.
  • Sur la ligne suivante, une liste de nombre personnes entiers séparés par des espaces : designes, pour chaque personne, la personne qui tombera malade l'année suivante si cette personne est malade cette année.

Sortie

Afficher le nombre d'années à attendre pour qu'aucune des personnes graciées ne soit malade, ou -1 si cela n'arrivera jamais. La réponse pouvant être très grande, si le résultat dépasse 1 000 000 007, afficher le résultat modulo 1 000 000 007.

Contraintes

  • $1 \le \text{nombre personnes} \le 100$
  • $\text{nombre personnes} - 5 \le \text{nombre gracies} \le \text{nombre personnes}$
  • $0 \le \text{nombre gracies}$
  • $1 \le \text{gracies}_i \le \text{nombre personnes}$
  • $1 \le \text{nombre malades} \le 20$

Contraintes de performance

  • $1 \le \text{nombre personnes} \le 100\,000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

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

Ici, 6 personnes sont dans Helheim.

Les personnes 1, 2 et 6 sont désignées pour quitter Helheim lors du Ragnarøk. On cherche donc à savoir dans combien d'années aucune de ces trois personnes ne sera malade.

  • Cette année, les personnes 1 et 4 sont malades.
  • La personne 1 désigne la personne 2, et la personne 4 désigne la personne 5. L'année suivante, les personnes malades seront donc les personnes 2 et 5.
  • L'année suivante, la personne 2 désigne la personne 3, et la personne 5 désigne la personne 6.
  • L'année suivante, la personne 3 désigne la personne 2, et la personne 6 désigne la personne 4.
  • Enfin, l'année suivante, la personne 2 désigne la personne 3 et la personne 4 désigne la personne 5.

Au bout de 4 ans, les personnes malades sont uniquement les personnes 3 et 5. Vu que ni 1, ni 2 et ni 6 ne sont malades, ils peuvent être libérés.

La réponse attendue est donc 4.

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

Ici, on a quatre personnes. Les personnes 2 et 4 sont graciées et seront libérées lorsque aucune de ces deux personnes ne sera malade.

Cette année, la personne 2 et la personne 3 sont malades. L'année suivante, les personnes 1 et 4 seront malades. L'année suivante, les personnes 2 et 3 seront malades à nouveau.

Ceci se répétera pour toujours, et ainsi les personnes 2 et 4 ne seront jamais saines en même temps.

Il n'y a pas de réponse, il faut donc afficher -1.