Rite d'initiation – Épreuve régionale 2010

ÉNONCɶ

Un candidat de prologin se retrouve à sa première finale, il a douze ans et subit donc les rites d'initiation que tous suivent lors de leur première demi-finale : on fait croire à un candidat qu'il existe une piscine en haut de l'immeuble de 420 étages, il y monte, une fois en haut, il reste coincé car la porte se ferme dernière lui.

Une fois en haut, on allume une lance à incendie, et ils se retrouve trempé.

But de votre algorithme : aider le candidat à descendre du toit.

Principe : à plusieurs étages, on trouve des lances à incendies, le but du jeu est de s'en servir pour descendre (comme Bruce Willis dans Die Hard (le premier) ou Eric dans la Tour Montparnasse Infernale) les lances ne sont pas de la bonne hauteur, il faudra donc que le candidat s'en serve pour sauter, changer de lance et sauter à nouveau pour arriver en bas.

Écrivez un programme qui donne le nombre de lances à incendies à prendre au minimum pour arriver en bas.

ENTRÉE¶

• Sur la première ligne, un entier S, la taille de l'immeuble.
• Sur la seconde ligne, un entier N, le nombre de lances à incendie.
• Sur les N lignes suivantes, un couple d'entier (Di, Ai), le premier représente l'étage où se trouve la lance (départ), le second, l'étage où elle vous emmène (arrivée).

Attention : une lance ne vous permet pas remonter, et vous ne pouvez pas descendre au milieu de la lance.

Au début, vous vous trouvez au niveau (S-1) et vous devez aller au niveau 0.

SORTIE¶

• Un entier : le nombre minimal de lances à prendre pour parcourir l'immeuble (tous les tests admettent au moins un chemin pour arriver en bas)

CONTRAINTES¶

• 0 < N < 250000.
• 0 < S < 200000.
• 0 <= Di <= S.
• 0 <= Ai <= S.
• Di <= Ai (car la lance descend les étages).