Joseph Macadam – Épreuve régionale 2025

Niveau 1 ⋅ Validation weight: 100%

Énoncé

Joseph a obtenu une réponse d'un de ses collègues, Joseph Macadam, qui occupe un poste d'agent d'exploitation des routes maritimes dans la cité.

Joseph Macadam lui indique avoir de précieuses informations à lui transmettre, et lui promet de l'aider à condition que Joseph l'aide en retour.

Une route est composée de $N$ portions. Chaque portion peut soit être trouée, soit être bouchée par des déblais. Les portions trouées sont indiquées dans la liste $\mathtt{route}$ par un nombre négatif, dont la valeur absolue représente le volume de manque à remplir. Les portions bouchées sont indiquées dans la liste $\mathtt{route}$ par un nombre positif, représentant la quantité de déblais qui bloque la portion.

Heureusement, le département des routes maritimes dispose de bulldozers afin de pousser les gravats de portion en portion suivante de la route.

Cependant, cet engin ne peut pousser que $X$ unités de gravats simultanément. Il ne peut pas non plus franchir les trous présents sur les routes, mais ces derniers peuvent être comblés grâce aux gravats cumulés et poussés par le bulldozer. Dans ce cas, le volume de gravats utilisé pour combler le trou est retiré des gravats actuellement poussés par la machine.

Le bulldozer s'arrête d'avancer si le volume cumulé de gravats est supérieur à $X$, ou si un trou ne peut être comblé. L'engin avance de gauche à droite sur les portions.

Pour aider Joseph, déterminez combien de portions pourra parcourir sa machine avant d'être bloquée.

Entrée

  • Sur la première ligne, un entier : N, le nombre de portions de la route.
  • Sur la seconde ligne, un entier : X, la puissance de l'engin.
  • Sur la ligne suivante, une liste route de N entiers représentant les déblais.

Sortie

Afficher, sur une ligne, l'entier représentant la distance dégagée de déblais.

Contraintes

  • $1 \le N \le 1\,000$
  • $0 \le X \le 1\,000\,000\,000$
  • $-1\,000\,000\,000 \le \mathtt{route}_i \le 1\,000\,000\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
10
5 -3 4 6
Exemple de sortie
3
Commentaire

Joseph dispose ici d'un bulldozer ayant une capacité de 10.

Il commence par pousser les 5 gravats de la première portion sur la seconde. Ainsi, il remplit avec 3 gravats le trou de la seconde portion, et continue à pousser les 2 gravats restants sur la 3e portion. Finalement un total de 6 gravats sont encore entraînés à la dernière portion. Là, la machine accumule 12 gravats, ce qui est trop lourd pour permettre de pousser les gravats plus loin. La machine s'arrête donc au bout du 3e tronçon.

schema

Exemple d'entrée
4
10
3 -5 4 6
Exemple de sortie
1
Commentaire

Joseph dispose ici aussi d'un bulldozer ayant une capacité de 10.

Cependant, après avoir poussé les 3 premiers gravats dans la seconde portion de route, Joseph se rend compte que cela ne suffit pas à combler le trou. La machine reste donc bloquée après 1 tronçon traversé.

schema

Exemple d'entrée
3
1
10 1 -5
Exemple de sortie
0
Commentaire

Joseph dispose ici aussi d'un bulldozer ayant une capacité de 1.

Cependant, le premier tronçon contenant déjà plus de 1 unité de déblai, Joseph ne parvient pas à dégager le premier tronçon.

Comme Joseph n'a pas pu dégager un seul tronçon, il faut afficher 0.