Billes, version B

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)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.
Les marches sont numérotées de 0 à 9. Les marches sont numérotées de 0 à nbMarches() - 1. Les lancers sont numérotés de 0 à nbLancers() - 1.

Contraintes

Les données du problème vérifient les contraintes suivantes :

  • 1 ≤ nbMarches20100 000, où nbMarches est le nombre de marches du plateau.
  • 1 ≤ hauteur ≤ 20, où hauteur est la hauteur d'une marche.
  • 1 ≤ nbLancers2010 000, où nbLancers est le nombre de lancers de billes.

Exemple

Voici un exemple de code qu'il faudrait écrire si la bille s'arrêtait à la position 8. Remplacez le 8 par la bonne valeur et soumettez le code obtenu dans l'onglet Résoudre

Voici un exemple de code qui lit les hauteurs de toutes les marches, et appelle positionFinale avec le numéro de la plus basse pour chacun des lancers. Bien sûr il ne donne pas tous les points, mais il peut vous servir de modèle pour écrire votre propre programme.

#include "lib.h"

int main()
{
  int posBille = 0;
  for (int iMarche = 0; iMarche < nbMarches(); iMarche++) {
     if (hauteur(iMarche) < hauteur(posBille)) {
        posBille = iMarche;
     }
  }
  positionFinale(posBille);
  return 0;
}

#include "lib.h"

int main()
{
  int posBille = 0;
  for (int iMarche = 0; iMarche < nbMarches(); iMarche++) {
     if (hauteur(iMarche) < hauteur(posBille)) {
        posBille = iMarche;
     }
  }
  positionFinale(posBille);
  return 0;
}

open Lib

let posBille = ref 0

let _ =
  for iMarche = 0 to nbMarches() - 1 do
     if hauteur iMarche < hauteur !posBille then
        posBille := iMarche
  done;
  positionFinale !posBille

import static algorea.Lib.*;

class Main
{
    public static void main(String[] args)
    {
       int posBille = 0;
       for (int iMarche = 0; iMarche < nbMarches(); iMarche++)
       {
          if (hauteur(iMarche) < hauteur(posBille))
          {
             posBille = iMarche;
          }
       }
       positionFinale(posBille);
    }
}

import static algorea.Lib.*;

int posBille = 0;
for (int iMarche = 0; iMarche < nbMarches(); iMarche++)
{
   if (hauteur(iMarche) < hauteur(posBille))
   {
      posBille = iMarche;
   }
}
positionFinale(posBille);

from lib import *

posBille = 0

for iMarche in range(0, nbMarches()):
   if (hauteur(iMarche) < hauteur(posBille)):
      posBille = iMarche
positionFinale(posBille)

import static algorea.Lib.*;

class Main
{
    public static void main(String[] args)
    {
        int posBille = 0;

        while(hauteur(posBille) >= hauteur(posBille+1))
            ++posBille;

        positionFinale(posBille);
    }
}

Vous pouvez voir ci-dessous le résultat de l'exécution de cet exemple.


Source : https://www.france-ioi.org/