Lost in space – Épreuve régionale 2020

Niveau 1

Énoncé

Joseph Marchand est sur la planète Gwendln-A et veut retrouver ses amis sur la planète Gwendln-B, à $D$ années-lumière. Malheureusement, son gadget de téléportation est cassé. En se téléportant depuis sa position d'origine, le gadget va choisir aléatoirement sa position d'arrivée, ce qui déplace Joseph de $M$ années-lumière.

Il est donc très possible que Joseph soit happé par un trou noir en atterrissant exactement à sa position. Les positions de tous les trous noirs sur le chemin sont regroupées dans une liste de $N$ entiers. Une autre possibilité est qu'il soit perdu en route, et donc n'est jamais arrivé à la bonne planète.

Aidez le gadget à déterminer l'état de Joseph après la fin de la téléportation: perdu dans l'espace, tombé dans un trou noir, ou arrivé à destination.

Entrée

  • Sur la première ligne, $D$ qui est la distance entre les 2 planètes.
  • Sur la deuxième ligne, $M$ qui est la distance à laquelle Joseph s'est téléporté.
  • Sur la troisième ligne, $N$ qui est le nombre de trous noirs.
  • Sur la quatrième ligne, $N$ entiers séparés par des espaces représentant la position de chaque trou noir.

Sortie

L'état de Joseph Marchand:

  • S'il est perdu dans l'espace, le message sera 0.
  • S'il est tombé dans un trou noir, il sera -1.
  • Sinon le message sera 1.

Contraintes

  • $1 ≤ D ≤ 1000$
  • $1 ≤ M ≤ 1000$
  • $1 ≤ N ≤ 100$

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
18
4
4
5 12 14 15
Exemple de sortie
0
Commentaire

Dans cet exemple, la distance entre les deux planètes est de 18 années-lumière. Joseph s'est téléporté à 4 années-lumière de son point d'origine. Il n'est donc pas arrivé à destination et est perdu. Par contre, il n'est pas tombé à la position d'un trou noir, d'où le résultat 0.

Exemple d'entrée
16
12
4
5 12 14 15
Exemple de sortie
-1
Commentaire

Ici, le résultat montre que Joseph a été happé par un trou noir qui est à la position 12.

Exemple d'entrée
18
18
4
5 12 14 15
Exemple de sortie
1
Commentaire

Joseph a pu arriver à la bonne destination !