Sujet 2 (B)

Contexte

Les types de fichiers volumineux comme les images, sons et vidéos sont généralement compressés afin d'économiser de l'espace disque (pour leur stockage) et de la bande passante (pour leur transmission). Pour compresser sans perte des images à faible nombre de couleurs, comme par exemple les icones ou les images utilisées dans les vieux jeux vidéos, une méthode très simple est la suivante :

  • on part de la description de l'image listant les couleurs des pixels de gauche à droite puis de haut en bas (il faut aussi savoir la longueur des lignes, mais on ne s'en occupera pas ici),
  • cette description, du fait du faible nombre de couleurs, contient généralement beaucoup de longues répétitions d'une même couleur : en imaginant une image en noir et blanc (qu'on représentera par les lettres `n` et `b`), on peut avoir par exemple "bbnbbbbnbbnnnnnbbnbbbbnbb",
  • on remplace les répétitions successives par deux caractères : la lettre à répéter et le nombre de répétitions : pour l'exemple précédent, ça donne "b2nb4nb2n5b2nb4nb2".

Cette méthode s'appelle Run-length encoding, ou RLE (il y a des variantes, et on n'a pas ici tenu compte du fait qu'utiliser de nouveaux symboles pour compter les répétitions augmente la taille de l'alphabet, ce qui vient contrebalancer, suivant les qualités de l'image, la réduction du nombre de symboles nécessaires pour la décrire). Dans cet exercice, on va écrire un décodeur de RLE.

Enoncé

Étant donnée une chaîne de caractères message composée de lettres minuscules non-accentuées et de chiffres, calculer la chaîne de lettres (sans chiffres) obtenue en remplaçant, lorsqu'une lettre (par exemple `a`) est suivie d'un nombre ("12"), l'ensemble des deux ("a12") par une répétition de la lettre autant de fois qu'indiqué par le nombre ("aaaaaaaaaaaa").

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 8 000 ko.

Entrée

L'entrée contient la chaîne de caractères message. Elle ne contient que de caractères de `a` à `z` et de `0` à `9`, et commence par une lettre. S'il y a plusieurs chiffres successifs, ils forment un unique nombre, et les nombres sont toujours supérieurs ou égaux à 2 (et représentables par un entier de base dans votre langage (type int/integer)).

Sortie

La sortie est le message d'entrée décodé comme décrit dans l'énoncé, et suivi d'un retour à la ligne.

Exemples

Exemple 1

entrée :

a2bcde10f

sortie :

aabcdeeeeeeeeeef

Exemple 2

entrée :

b2nb4nb2n5b2nb4nb2

sortie :

bbnbbbbnbbnnnnnbbnbbbbnbb

Commentaires

Squelettes de codes :

[GROUPFULL:skeleton]

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