Sur Algoréa, un nouveau jeu à la mode se joue en faisant traverser à une bille un plateau consistant en une série de marches de différentes hauteurs. On lance une bille vers la droite, puis on regarde jusqu'où elle va.

Une bille n'avance que vers la droite, et s'arrête dès que la hauteur de la marche située immédiatement à sa droite est strictement plus haute que celle sur laquelle elle se trouve. La dernière marche du plateau est toujours assez haute pour que les billes ne sortent jamais du plateau.

On lance la bille à l'extrémité gauche du plateau suivant, c'est à dire la marche 0.

Dans cette version, on lance la bille à l'extrémité gauche du plateau, c'est à dire la marche 0. Vous devez écrire un programme qui, étant donné les hauteurs des marches, détermine jusqu'où la bille va aller.

Dans cette version, on lance plusieurs billes successivement, à l'extrémité gauche du plateau (marche 0). À la fin de leur parcours, on laisse les billes là où elles s'arrêtent : elles ajoutent 1 à la hauteur de la marche sur laquelle elles se sont arrêtées. Vous devez écrire un programme qui, étant donné les hauteurs des marches au départ, détermine jusqu'où chaque bille va aller.

Il s'agit du même problème que la version B, mais avec bien plus de marches et de nombreux lancers depuis diverses positions. Pour passer tous les tests, il faut trouver une manière de rendre le programme très rapide.

Il s'agit exactement du même problème que la version C, mais avec bien plus de marches et de lancers. Pour passer tous les tests, il faut trouver une manière de rendre le programme très rapide.

Dans cette version, on lance plusieurs fois une bille à des positions données différentes, en la retirant du plateau à la fin de son parcours. Vous devez écrire un programme qui, étant donné les hauteurs des marches et les positions de départ des différents lancers, détermine jusqu'où la bille va aller pour chaque lancer.

Votre programme doit appeler une seule fois la fonction positionFinale(iMarche) où iMarche est le numéro de la marche sur laquelle la bille se trouve à la fin de son parcours. Par ailleurs, vous pouvez utiliser les fonctions suivantes : Pour écrire votre programme, vous pouvez utiliser les fonctions suivantes :

• nbMarches() retourne le nombre de marches du plateau.
• hauteur(iMarche) retourne la hauteur de la marche numéro iMarche.
• nbLancers() retourne le nombre de lancers de bille.
• marcheLancer(iLancer) retourne le numéro de la marche de départ du lancer iLancer.
• Votre programme doit faire un appel à positionFinale(iMarche) pour chaque lancer, où iMarche est le numéro de la marche sur laquelle la bille se trouve à la fin de son parcours.

#include <algorithm>
#include "lib.h"

using namespace std;

const int LARGEUR_MAX = 1000000;

int altitude[LARGEUR_MAX];

int main()
{
  for(int iPos = 0; iPos < nbMarches(); ++iPos)
    altitude[iPos] = hauteur(iPos);

  int posBille = 0;
  for(int iBille = 0; iBille < nbLancers(); ++iBille)
  {
    posBille = max(posBille-1, 0);

    while(altitude[posBille] >= altitude[posBille+1])
      ++posBille;

    ++altitude[posBille];
    positionFinale(posBille);
  }
  return 0;
}

#include <algorithm>
#include "lib.h"

using namespace std;

const int LARGEUR_MAX = 1000000;

int altitude[LARGEUR_MAX];

int main()
{
  for(int iPos = 0; iPos < nbMarches(); ++iPos)
    altitude[iPos] = hauteur(iPos);

  int posBille = 0;
  for(int iBille = 0; iBille < nbLancers(); ++iBille)
  {
    posBille = max(posBille-1, 0);

    while(altitude[posBille] >= altitude[posBille+1])
      ++posBille;

    ++altitude[posBille];
    positionFinale(posBille);
  }
  return 0;
}

open Lib

let altitude = Array.make (nbMarches()) 0

let _ =
  for iPos = 0 to nbMarches() - 1 do
    altitude.(iPos) <- hauteur iPos
  done

let posBille = ref 0

let _ =
  for iBille = 0 to (nbLancers()-1) do
    posBille := max (!posBille-1) 0;

    while altitude.(!posBille) >= altitude.(!posBille+1) do
      incr posBille
    done;

    altitude.(!posBille) <- altitude.(!posBille) + 1;

    positionFinale(!posBille)
  done

import static java.lang.Math.*;
import static algorea.Lib.*;

class Main
{
    final static int LARGEUR_MAX = 1000000;

    static int altitude[] = new int[LARGEUR_MAX];

    public static void main(String[] args)
    {
        for(int iPos = 0; iPos < nbMarches(); ++iPos)
            altitude[iPos] = hauteur(iPos);

        int posBille = 0;
        for(int iBille = 0; iBille < nbLancers(); ++iBille)
        {
            posBille = max(posBille-1, 0);

            while(altitude[posBille] >= altitude[posBille+1])
                ++posBille;

            ++altitude[posBille];
            positionFinale(posBille);
        }
    }
}

posBille = 0
for iBille in range(nbLancers()):
   posBille = max(posBille - 1, 0)

   while(altitude[posBille] >= altitude[posBille+1]):
      posBille += 1

   altitude[posBille] += 1
   positionFinale(posBille)