Le Juste Message – Qualification 2025

Niveau 1 ⋅ Validation weight: 100%

Énoncé

Après avoir retrouvé sa machine à voyager dans le temps l'année dernière, Joseph Marchand continua son voyage. On le retrouve actuellement au ⅩⅨᵉ siècle à bord d'un super sous-marin monoplace à la pointe de la technologie… de l'époque. En effet, Joseph Marchand, sous le nom de code de Joseph Nageant est en mission à la recherche d'une cité perdue qu'on dit cachée au fond des mers.

Malheureusement, Joseph a quelques problèmes pour se diriger. Un Guide Puissant Sous-marin (GPS) lui aurait bien été utile, mais cela n'a pas encore été inventé. C'est donc son équipe depuis la terre ferme qui le guide en envoyant un poisson voyageur pour transmettre des indications. Lors de certains échanges, les messages arrivent complètement détériorés à cause de l'eau : certains chiffres se sont ajoutés dans le message par transfert d'encre.

On vous indique le dernier message transmis à Joseph Nageant par le poisson voyageur. Ce message peut contenir des chiffres, des lettres, et certaines ponctuations.

Un chiffre est considéré comme en trop seulement s'il s'agit d'un chiffre strictement inférieur au dernier chiffre qui le précède. Le premier chiffre du message qu'il reçoit fait donc toujours partie du message original.

Pour l'aider à atteindre sa destination, retrouvez le juste message original.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, la taille du message reçu.
  • Sur la ligne suivante, une liste de N caractères juxtaposés : message, le message à restaurer.

Sortie

Afficher, sur une ligne, le message restauré, c'est-à-dire le message sans les chiffres qui ont été ajoutés lors du transfert.

Contraintes

On vous garantit que ces contraintes sont respectées dans les tests effectués. Vous n'avez pas besoin de les vérifier par vous-même.

  • $1 \le N \le 420$
  • Le message reçu ne peut contenir que des caractères alphanumériques et certaines ponctuations ([a-zA-Z0-9.,_\-]+)

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
12345
Exemple de sortie
12345
Commentaire

Les chiffres sont déjà triés par ordre croissant : $1 < 2 < 3 < 4 < 5$. Ainsi, aucun chiffre n'est plus petit que le chiffre précédent. Quelle chance ! Aucun bruit ne s'est ajouté au message, pas besoin de le modifier.

Exemple d'entrée
5
54321
Exemple de sortie
5
Commentaire

Ici, le message reçu est une suite décroissante : $5 > 4 > 3 > 2 > 1$. À l'inverse, la plupart des chiffres sont donc plus petits que le chiffre précédent : beaucoup de bruit s'est rajouté au message ! Mis à part le tout premier chiffre, qui n'a pas de chiffre précédent, tout le message est constitué de bruit.

Exemple d'entrée
42
go_to_215.32498887125,3_-7501.853723432117
Exemple de sortie
go_to_25.498825,_-71.873417
Commentaire

Ce cas est plus complexe : il n'y a pas que des chiffres dans le message ! Qui est en trop ? Le bruit ajouté n'étant composé que de chiffres, tous les caractères qui ne sont pas des chiffres proviennent du message original. Les chiffres extraits du message forment la suite suivante : 2153249888712537501853723432117.

Parmi ces chiffres, la moitié sont plus petits que le chiffre précédent, en gras ici : 2153249888712537501853723432117. En supprimant ces caractères qui ne font pas partie du message originel, on obtient le juste message : go_to_25.498825,_-71.873417.