Ruisseau progressif – Regional event 2017

Level 4

Énoncé

Près du village de Joseph Marchand, il y a un ruisseau assez spécial : sa vitesse d'écoulement varie tout au long de la journée (en restant positive), et dès qu'elle atteint une certaine vitesse de seuil $M$, elle ne redescendera plus en-dessous de celle-ci le reste de la journée. Pour cette raison, ce ruisseau porte la dénomination de ruisseau progressif.

Joseph souhaite se convaincre de la véracité de la propriété du ruisseau. Une après-midi il décide de mesurer, à intervalles réguliers de temps, la vitesse d'écoulement du ruisseau.

Cependant, après expérience, il remarque que la propriété n'est pas toujours vérifiée en pratique, il vous montre ses résultats.

Vous, persuadé que le ruisseau est bien progressif, tentez d'expliquer à Joseph qu'il a très probablement fait des erreurs de mesure. Afin que votre argumentation soit crédible, calculez l'erreur minimale que Joseph a pu commettre en relevant les données.

L'erreur, par rapport à une solution acceptable, est la somme des différences absolues pour chaque instant de mesure.

Formellement, lors d'une après-midi, si le ruisseau est progressif alors :

  • soit chaque vitesse mesurée $v_i$ est strictement inférieure au seuil $M$
  • soit il existe $1 \le j \le N$ tel que pour tout $1 \le i \le j-1$ on a $v_i$ qui est strictement plus petit que $M$, et pour tout $j \le i\le N$ on a $v_i$ qui vaut au moins $M$.

Entrée

L'entrée comprendra deux lignes :

  • La première ligne contiendra deux entiers $N$ et $M$, le nombre de mesures effectuées par Joseph, et le seuil $M$ du ruisseau.
  • La seconde ligne contiendra $N$ entiers. Le i-ème d'entre eux, $v_i$, désignera la i-ème mesure de la vitesse.

Sortie

Vous afficherez un entier, la plus petite erreur effectuée par Joseph si le ruisseau était effectivement progressif (affichez 0 si la mesure de Joseph était initialement correcte).

Contraintes

  • $1 \le N \le 500$
  • $1 \le M \le 1\ 000$
  • $0 \le v_i \le 1\ 000$

Contrainte de performance

  • $1 \le N \le 200\ 000$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4 5
5 3 7 3
Sample output
3
Note

Pour cet exemple, le ruisseau (4, 3, 7, 5) est progressif et est à une distance de 3 de celui donné en entrée.

Sample input
4 5
4 3 5 2
Sample output
1
Note

Pour celui-là, le ruisseau progressif le plus proche est (4, 3, 4, 2) qui est à une distance de 1.

Sample input
4 5
6 5 7 8
Sample output
0
Note

Ici, le ruisseau donné en entrée est déjà progressif.

Submit your solution

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