Tableaux Autoréférents – Épreuve régionale 2024

Niveau 2 ⋅ Validation weight: 50%

Énoncé

Oh non ! Une divinité un peu tête en l'air à ouvert la mauvaise porte de l'Yggdrasil… et maintenant, le Ragnarök (l'événement mythique causant mort, destruction et fin du monde) approche à grands pas !

Jøsëf Marchand, armé de son courage, va essayer de le retarder un peu pour avoir le temps de sauver un maximum de vies.

Pour cela, il va essayer de retrouver la porte de l'Helheim, le monde des morts, afin de ramener à la vie un maximum de guerriers pour combattre à ses cotés. Mais il ne sait plus où se situe cette porte !

Il dispose en face de lui d'un tableau portes de portes, et sur chacune est gravé un nombre. L'inscription gravée sur la i-ème porte doit correspondre au nombre de portes sur lesquelles sont inscrits le nombre i. La première porte qui ment est forcément la porte de l'Helheim ! Si aucune ne ment, alors c'est que la porte n'est pas ici.

En clair, affichez le premier indice i dans l'ordre croissant tel que le nombre d'occurrences de i dans portes est différent de portes[i]. Si un tel i n'existe pas, on affichera -1.

Notez que portes est indexé à 0.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de portes.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : portes, les indications sur les portes.

Sortie

Afficher le premier indice $0 \le i < N$ tel que portes[i] ne correspond pas au nombre d'occurrences de $i$ dans portes, ou -1 sinon.

Contraintes

  • $1 \le N \le 20$
  • $0 \le \text{portes[i]} < N$

Contraintes de performance

  • $1 \le N \le 10\,000\,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
4
1 2 1 0
Exemple de sortie
-1
Commentaire

Ici, le tableau est composé de quatre éléments : 1 2 1 0

  • Il y a bien qu'un seul 0 dans le tableau, donc portes[0] = 1 est correct.
  • Il y a bien deux 1 dans le tableau, donc portes[1] = 2 est correct.
  • Il y a bien qu'un seul 2 dans le tableau, donc portes[2] = 1 est correct.
  • Il y a bien aucun 3 dans le tableau, donc portes[3] = 0 est correct.

Comme le tableau est autoréférent, aucune porte ne mène à l'Helheim. On affiche alors -1.

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

Ici, le tableau est composé de cinq éléments : 1 2 1 0 2

  • Il y a bien qu'un seul 0 dans le tableau, donc portes[0] = 1 est correct.
  • Il y a bien deux 1 dans le tableau, donc portes[1] = 2 est correct.
  • Il n'y a pas qu'un seul 2 dans le tableau, il y en a 2, donc portes[2] = 1 est incorrect.

Ici le tableau n'est pas autoréférent à cause, en premier lieu, de l'indice 2. Il s'agit donc de la porte vers Helheim, on affiche alors 2.

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

Ici, le tableau est composé de cinq éléments : 2 1 2 0 0

  • Il y a bien deux 0 dans le tableau, donc portes[0] = 2 est correct.
  • Il y a bien un unique 1 dans le tableau, donc portes[1] = 1 est correct.
  • Il y a bien deux 2 dans le tableau, donc portes[2] = 2 est correct.
  • Il y a bien aucun 3 dans le tableau, donc portes[3] = 0 est correct.
  • Il y a bien aucun 4 dans le tableau, donc portes[4] = 0 est correct.

Comme le tableau est autoréférent, aucune porte ne mène à Helheim. On affiche donc -1.