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éroiMarche
. -
nbLancers()
retourne le nombre de lancers de bille. marcheLancer(iLancer)
retourne le numéro de la marche de départ du lanceriLancer
.- 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.
Contraintes
Les données du problème vérifient les contraintes suivantes :
- 1 ≤ nbMarches ≤ 20100 000, où nbMarches est le nombre de marches du plateau.
- 1 ≤ hauteur ≤ 20, où hauteur est la hauteur d'une marche.
- 1 ≤ nbLancers ≤ 2010 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" const int LARGEUR_MAX = 1000000; int destinationBille[LARGEUR_MAX+1]; int main() { for(int iPos = nbMarches() - 2; iPos >= 0; --iPos) { if(hauteur(iPos) < hauteur(iPos+1)) destinationBille[iPos] = iPos; else destinationBille[iPos] = destinationBille[iPos+1]; } for(int iBille = 0; iBille < nbLancers(); ++iBille) { int posBille = marcheLancer(iBille); positionFinale(destinationBille[posBille]); } return 0; }
#include "lib.h" const int LARGEUR_MAX = 1000000; int destinationBille[LARGEUR_MAX+1]; int main() { for(int iPos = nbMarches() - 2; iPos >= 0; --iPos) { if(hauteur(iPos) < hauteur(iPos+1)) destinationBille[iPos] = iPos; else destinationBille[iPos] = destinationBille[iPos+1]; } for(int iBille = 0; iBille < nbLancers(); ++iBille) { int posBille = marcheLancer(iBille); positionFinale(destinationBille[posBille]); } return 0; }
open Lib let destinationBille = Array.make (nbMarches()+1) 0 let _ = for iPos = nbMarches() - 2 downto 0 do if hauteur iPos < hauteur (iPos+1) then destinationBille.(iPos) <- iPos else destinationBille.(iPos) <- destinationBille.(iPos+1) done let _ = for iBille = 0 to nbLancers() - 1 do let posBille = marcheLancer iBille in positionFinale destinationBille.(posBille) done
import static algorea.Lib.*; class Main { final static int LARGEUR_MAX = 1000000; static int destinationBille[] = new int[LARGEUR_MAX+1]; public static void main(String[] args) { for(int iPos = nbMarches() - 2; iPos >= 0; --iPos) { if(hauteur(iPos) < hauteur(iPos+1)) destinationBille[iPos] = iPos; else destinationBille[iPos] = destinationBille[iPos+1]; } for(int iBille = 0; iBille < nbLancers(); ++iBille) { int posBille = marcheLancer(iBille); positionFinale(destinationBille[posBille]); } } }
from lib import * destinationBille = [nbMarches()-1] * nbMarches() for iPos in range(nbMarches() - 2, -1, -1): if(hauteur(iPos) < hauteur(iPos+1)): destinationBille[iPos] = iPos else: destinationBille[iPos] = destinationBille[iPos+1] for iBille in range(0, nbLancers()): posBille = marcheLancer(iBille) positionFinale(destinationBille[posBille])
Vous pouvez voir ci-dessous le résultat de l'exécution de cet exemple.
LAIKO IR ATMINTIES RIBOJIMAI (Python)
- Laiko ribojimas: 2 sek., procesorius: 1GHz.
- Atmintis: 64,000 KB.
Tik užsiregistravę ir prisijungę galite pateikti šio uždavinio sprendimą.
Registravimasis užims vos keletą minučių, tuomet galėsite svetainėje spręsti uždavinius, juos testuoti bei pateikti jų sprendimus.
Prisijungę gausite iš anksto paruoštas užuominas arba galėsite kreiptis pagalbos į forumą.
Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.
Une correction sera mise en ligne après la fin de l'épreuve.