Passage Tout Juste – Qualification 2025

Niveau 2 ⋅ Validation weight: 100%

Énoncé

Joseph Nageant est maintenant aux abords de la ville. Cependant, il doit à présent pénétrer dans l'enceinte de la ville. Pour cela il peut compter sur les informations qu'il avait récupérées avant l’expédition. L'un des documents trouvés faisait mention d'un vieux passage souterrain qui permettait aux marchands du Marché Noir de poissons de s'approvisionner en espèces rares et interdites.

Cependant, ce passage est très étroit, mal entretenu, et comporte de nombreux pièges mortels. Afin de franchir ce long périple, Joseph Nageant va devoir s'appuyer sur son agilité pour esquiver les dangers.

Le passage souterrain est un tunnel de $\mathtt{longueur}$ mètres de long, qui alterne entre zones sûres et zones de danger. On vous décrit le passage à l'aide d'un tableau de 0 et de 1 : un chiffre tous les mètres, un 0 décrit une position dans une zone sûre, un 1 décrit une position dans une zone de danger. Une zone sûre est donc représentée par un ou plusieurs 0 consécutifs, et une zone de danger par un ou plusieurs 1 consécutifs.

Lors de sa traversée, à chaque mètre, Joseph Nageant peut soit effectuer une esquive, soit se reposer. Joseph Nageant doit traverser le souterrain en effectuant des esquives dans toutes les zones de danger. Dans les zones sûres, il peut soit esquiver, soit se reposer.

Par précaution, Joseph doit se reposer au moins une fois dans chaque zone sûre. Il ne peut pas esquiver l'intégralité d'une zone sûre.

Cependant, Joseph dispose d'une certaine endurance $E \geq 0$ qui lui permet d'esquiver pendant au maximum $E$ mètres avant de devoir se reposer. Après avoir effectué une esquive, il est obligé de se reposer pendant au minimum $R$ mètres avant la prochaine esquive ou la fin du tunnel. (Joseph ne peut donc pas entamer une phase de repos pendant les $R-1$ derniers mètres. Par ailleurs, si Joseph commence par une phase de repos, il doit tout de même se reposer au moins sur les $R$ premiers mètres.)

On appelle la force de Joseph la valeur de $R$ - $E$. Aidez Joseph Nageant à trouver une stratégie de déplacement qui maximise sa force.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : longueur, la longueur (en mètres) du passage souterrain.
  • Sur la ligne suivante, une liste de longueur entiers séparés par des espaces : tunnel, le tableau représentant les zones sûres et les zones de danger du passage souterrain. Un chiffre par mètre : Un 0 correspond à une position dans une zone sûre, et un 1 correspond à une position dans une zone de danger.

Sortie

Afficher la valeur de force maximale que Joseph Nageant peut obtenir en passant le tunnel.

Contraintes

  • $1 \le longueur \le 1\,000$
  • $\mathtt{tunnel}_i \in {0, 1}$
  • Il y a toujours au moins une zone de repos

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
12
0 0 0 1 0 0 0 1 1 1 0 0
Exemple de sortie
-1
Commentaire

En prenant comme valeur d'endurance $E = 3$ et comme valeur de repos minimal $R = 2$, voici un exemple de parcours que pourrait effectuer Joseph :

  • D'abord, il se repose sur les deux premiers mètres ($2 \geq R$);
  • Ensuite, il esquive sur les deux mètres suivants ($2 \leq E$);
  • Il se repose sur les trois mètres suivants ($3 \geq R$);
  • Il esquive la dernière zone de danger pendant trois mètres ($3 \leq E$);
  • Et finalement, il profite des deux derniers mètres pour se reposer ($2 \geq R$).

parcours

Cet exemple de parcours attribue à Joseph une force de $R - E = 2 - 3 = -1$. Il n'est pas possible d'esquiver toutes les zones de dangers avec une plus grande force.

Exemple d'entrée
9
1 0 1 0 0 0 1 1 1
Exemple de sortie
-2
Commentaire

En prenant comme valeur d'endurance $E = 3$ et comme valeur de repos minimal $R = 1$, voici un exemple de parcours que pourrait effectuer Joseph :

  • D'abord, il esquive la première zone de danger sur un mètre ($1 \leq E$);
  • Il se repose sur le mètre suivant ($1 \geq R$);
  • Il esquive la seconde zone de danger pendant un mètre ($1 \leq E$);
  • Pour la zone sûre de trois mètres, il décide de :
  • se reposer le premier mètre ($1 \geq R$);
  • effectuer une esquive sur le second mètre ($1 \leq E$);
  • se reposer le troisième mètre ($1 \geq R$);
  • Et finalement, il effectue une esquive sur trois mètres pour passer la dernière zone de danger ($3 \leq E$).

Cet exemple de parcours attribue à Joseph une force de $R - E = 1 - 3 = -2$. Il n'est pas possible d'esquiver toutes les zones de dangers avec une plus grande force.

Notez que l'esquive effectuée au 5ᵉ mètre n'est pas nécessaire, Joseph aurait aussi pu se reposer pendant les trois mètres de la zone sûre.

En revanche, Joseph n'aurait pas pu effectuer une esquive sur les trois premiers mètres, car il doit se reposer au moins une fois dans chaque zone de repos.

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

Ici, Joseph peut traverser le passage avec une endurance $E = 1$ et un repos minimal $R = 2$. Cela lui attribue un score de force de $R - E = 1$.

Il n'est pas possible d'esquiver toutes les zones de dangers avec plus de force.