La prophétie – Qualification 2016

Level 3

É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 yi 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 ≤ yi ≤ 100 000 ;
  • -100 000 ≤ h ≤ 100 000.

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
0
13
-41 -47 -52 -57 -74 -77 -23 -14 -56 2 -74 -40 -59
Sample output
-77
Note

Ici, pour une hauteur d'eau de -77, aucune terre n'est recouverte donc le volume est nul alors que pour une hauteur de -76, le volume d'eau serait strictement positif. Comme on demande V=0, la réponse est donc -77.

Sample input
91
12
-53 35 -44 -55 -47 -65 42 -25 -6 78 -7 -79
Sample output
-42
Note

Ici, l'eau est à -42 unités de hauteur.

Submit your solution

You have to register or log in to be able to submit your solution.