Challenge 4 - Statues

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

Pour vous aidez, vous pouvez utiliser l'exemple de code ci-dessous.

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 = " ")

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