La prophétie – Qualification 2016

Énoncé¶

Le grand conseil des Prolosaures a mis la main sur une tablette très ancienne annonçant le désastre que les dinosaures sont en train de vivre. Sur cette pierre oubliée de tous, il est indiqué le volume d’eau qui est en train de noyer le monde. Pour anticiper le désastre, le conseil cherche à savoir jusqu’à quelle altitude la mer va continuer de monter.

On vous donne une liste de nombres représentant les altitudes des différentes montagnes qui composent le continent ainsi que le volume total d’eau au-dessus des terres submergées. Écrivez un programme qui indique l’altitude (arrondie à l'entier inférieur) que va atteindre l’eau une fois la catastrophe terminée. Plus précisément, étant donné le volume V d'eau déversé par la tempête, on vous demande de trouver l'entier h tel que :

• si le niveau de la mer est h, alors le volume de l'eau sur les zones inondées est au plus V ;
• si le niveau de la mer est h+1, alors le volume d'eau sur les terres est strictement supérieur à V.

Entrée¶

L’entrée comprendra :

• un entier relatif V représentant le volume d'eau issu de la tempête ;
• sur la ligne suivante, un entier naturel non nul N correspondant au nombre de montagnes ;
• sur la ligne suivante, N entiers relatifs y_i séparés par des espaces, représentant l’altitude de chaque montagne.

Sortie¶

Vous afficherez en sortie :

• L’arrondi inférieur h de l’altitude qui sera atteinte par l’eau une fois la tempête terminée.

Contraintes¶

• 0 ≤ V ≤ 100 000 000 ;
• 1 ≤ N ≤ 10 000 ;
• -100 000 ≤ y_i ≤ 100 000 ;
• -100 000 ≤ h ≤ 100 000.