De nombreuses statues de chevaliers sont disposées dans un coin d'une salle. Leur disposition vous intrigue : elles sont bien alignées comme si elles occupaient des cases d'une grille. Chaque rangée est constituée d'un certain nombre de statues en partant de la gauche et sans laisser de case vide. Étrangement, le nombre de statues d'une rangée est toujours inférieur ou égal au nombre de statues de la rangée précédente.
Vous avez compté le nombre de statues de chaque rangée, et souhaitez écrire un programme qui à partir de ces nombres, détermine rapidement le nombre de statues de chaque colonne de la grille.
L'illustration ci-dessous représente une répartition des statues dans une grille de 10 rangées de 10 cases. Les nombres de statues des rangées sont 9, 8, 8, 8, 7, 5, 3, 1, 0 et 0, comme représenté en noir sur le côté gauche. Les nombres que votre programme doit déterminer sont les nombres rouges représentés au dessus des colonnes.
Limites de temps et de mémoire (Python)
- Temps : 2 s sur une machine à 1 GHz.
- Mémoire : 8 000 ko.
Contraintes
- 1 <= N <= 100 000.
De plus, dans 40% des tests, N <= 1000, et dans 20% d'autres tests, N <= 10 000.
Entrée
La première ligne de l'entrée contient l'entier N : le nombre de rangées et de colonnes de la grille.
La deuxième ligne contient N entiers compris entre 0 et N, et séparés par des espaces. Chaque nombre est forcément inférieur ou égal au précédent, et le dernier des nombres est forcément un zéro.
Sortie
Votre programme doit afficher une ligne contenant N entiers séparés par des espaces : le nombre de statues de chaque colonne de la grille.
Exemple
entrée :
10 9 8 8 8 7 5 3 1 0 0
sortie :
8 7 7 6 6 5 5 4 1 0
Commentaires
EXEMPLE DE CODE
Si vous n'êtes pas très à l'aise avec la lecture de l'entrée ou l'affichage en sortie, vous pouvez vous inspirer de l'exemple de programme suivant. Celui-ci lit l'entrée et affiche les valeurs lues.
#include <stdio.h> #define MAX_TAILLE (100 * 1000) int longueurLigne[MAX_TAILLE]; int main() { int taille; scanf("%d", &taille); for (int iLigne = 0; iLigne < taille; iLigne++) scanf("%d", &longueurLigne[iLigne]); for (int iLigne = 0; iLigne < taille; iLigne++) { printf("%d ", longueurLigne[iLigne]); } return 0; }
#include <iostream> using namespace std; const int MAX_TAILLE = 100 * 1000; int longueurLigne[MAX_TAILLE]; int main() { int taille; cin >> taille; for (int iLigne = 0; iLigne < taille; iLigne++) cin >> longueurLigne[iLigne]; for (int iLigne = 0; iLigne < taille; iLigne++) { cout << longueurLigne[iLigne] << " "; } return 0; }
import algorea.Scanner; class Main { public static void main(String [] args) { Scanner input = new Scanner(System.in); int taille; taille = input.nextInt(); int [] longueurLigne = new int[taille]; for (int iLigne = 0; iLigne < taille; iLigne++) longueurLigne[iLigne] = input.nextInt(); for (int iLigne = 0; iLigne < taille; iLigne++) { System.out.print(longueurLigne[iLigne] + " "); } } }
void main() { int taille = readInt(); int [] longueurLigne = new int[taille]; for (int iLigne = 0; iLigne < taille; iLigne++) longueurLigne[iLigne] = readInt(); for (int iLigne = 0; iLigne < taille; iLigne++) print(longueurLigne[iLigne] + " "); }
let read_int() = Scanf.scanf " %d" (fun x -> x) let taille = read_int() let longueurLigne = Array.init taille (fun _ -> read_int()) let _ = for iLigne = 0 to taille - 1 do print_int longueurLigne.(iLigne); print_string " " done
program Solution; const MAX_TAILLE = 100 * 1000; var iLigne,taille: LongInt; longueurLigne: array[0..MAX_TAILLE - 1] of LongInt; begin readln(taille); for iLigne := 0 to taille - 1 do read(longueurLigne[iLigne]); for iLigne := 0 to taille - 1 do write(longueurLigne[iLigne],' '); end.
taille = int(input()) longueurLigne = list(map(int, input().split())) for iColonne in range(taille): print(longueurLigne[iColonne], end = " ")
Vous devez être connecté(e) pour résoudre ce problème.
L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.
Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.
Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.
Une correction sera mise en ligne après la fin de l'épreuve.