Avui dia és habitual comprimir un fitxer abans d'enviar-lo per correu electrònic o de guardar-lo en un disquet. La compressió consisteix a efectuar un algorisme que redueixi el nombre d’octets del fitxer sense perdre la informació. L’algorisme de compressió ha de ser reversible, és a dir, és necessari que es pugui tornar a recuperar el fitxer original del fitxer comprimit. Ens plantegem fer un programa que pugui comprimir i descomprimir un fitxer utilitzant un senzill algorisme de compressió.

El text original a comprimir contindrà n línies de m caràcters cada línia. Per simplificar, aquests m caràcters només podran ser el 0 o el 1. Podem interpretar aquest text com un dibuix on els dos caràcters representen dos colors diferents. Així, per exemple, el text:

0001111000

representa el següent dibuix:

L’algorisme de compressió que es demana és un algorisme que transformi k caràcters iguals consecutius pel número k. Aquest número k podrà ser un nombre comprés entre 0  i 9, d'aquesta forma ens assegurem que podem representar-lo amb un únic caràcter. Prendrem el conveni que el primer caràcter serà el nombre de zeros inicial. Les dades del text comprimit de sortida seran doncs: el nombre de zeros consecutius, el nombre d'uns consecutius, el nombre de zeros concecutius, i així successivament. Hi haurà dos casos en què serà necessari fer servir el caràcter 0:

• quan el primer caràcter sigui un 1,

• quan hi hagi més de 9 caràcters iguals consecutius.

Per últim, serà necessari que el text de sortida comenci pel nombre de caràcters de les columnes per tal de poder reconstruir de nou el text original.

Veiem, per exemple, com ha de quedar transformat el text anterior:

El primer número és el nombre de caràcters d'una columna, en aquest cas 10. A continuació, i en la línia següent, ens indica que hi ha tres zeros (000), quatre uns (1111), cinc zeros (00000), etc.. Els nombres marcats en groc representen els 1 i els marcats en rosa els 0. Fixeu-vos que les xifres 11, 12, 13 indiquen que hi ha tretze  uns seguits (9 + 4).

Per aclarir tot més, veiem un nou exemple:

1000

1100

0110

0011

que representa el dibuix:

En aquest cas, el fitxer de sortida serà:

4                

01323232

És a dir, interpretem que hi ha 4 caràcters per línia. Hi ha zero zeros () , un un (1), tres zeros (000), etc..

Construïu un programa que pugui comprimir i descomprimir textos de les característiques vistes abans amb aquest algorisme.

El fitxer d'entrada tindrà el nom comp.in i serà un fitxer de text amb la següent informació i característiques:

• Un 1 o un 0. Un 1 indicarà que ha de comprimir el text i un 0 indicarà que ha de descomprimir-lo.

• Si el primer caràcter és un 1, a partir de la següent línia hi haurà les n línies amb els m caràcters cada línia. Aquests caràcters només poden ser 1 o 0. Aquests caràcters estaran junts i no aniran separats per espais.

• Si el primer caràcter és un 0, a la següent línia hi haurà un nombre enter amb el nombre de columnes del text descomprimit i a la tercera línia i sense espais tots els caràcters numèrics del text comprimit.

• En qualsevol cas, el nombre de caràcters per línia del text sense comprimir no superarà les 50 ni el nombre de línies tampoc superarà aquesta xifra. 

El fitxer de sortida tindrà el nom comp.out i serà un fitxer de text amb la següent informació i característiques:

• Si el primer caràcter del fitxer d'entrada és un 1, la primera línia del fitxer de sortida serà el nombre m de columnes del text original. La següent línia contindrà, sense espais, tots els caràcters numèrics que correspongui a la codificació abans esmentada.

• Si el primer caràcter del fitxer d'entrada és un 0, el fitxer de sortida contindrà les n línies amb el text descomprimit.

Anomeneu al fitxer font compxx.___ , i al fitxer executable compxx.exe on xx representa el codi del concursant i l'extensió del fitxer font dependrà del llenguatge utilitzat.