apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

sasp Virkņu saspiešana 1 sek.


 Uzdevums

Aplūkosim simbolu virknes, kas sastāv tikai no latviešu alfabēta lielajiem burtiem bez mīkstinājuma un garumzīmēm. Piemēram, virkne "AAAABBBAAAABBBC" ir viena no šādām virknēm un tās garums ir 15 simboli. Tā kā virknē var būt tikai burti, vairāku vienādu, pēc kārtas sekojošu burtu virkni varam aizvietot ar vienu šo burtu, kuram priekšā pierakstīts naturāls skaitlis - burtu skaits šajā virknē. Piemēram, iepriekšminēto virkni varētu pierakstīt arī kā "4A3B4A3BC" un šādas virknes garums būtu vairs tikai 9 simboli. Viegli ievērot, ka šajā virknē grupa 4A3B atkārtojas un šādu atkārtošanos pierakstīsim liekot atkārtojamo grupu iekavās, kurai priekšā pierakstīts atkārtošanās reižu skaits: 2(4A3B)C . Šīs virknes garums ir tikai 8 simboli. Protams, šī grupu atkārtošana var notikt arī vairākos līmeņos. Piemēram, virkni "ABABCABABC" var pierakstīt kā 2(2(AB)C). Uzrakstiet programmu, kas dotam saspiestam virknes pierakstam atrod un izvada sākotnējo burtu virkni!

 
 Ievaddati

Teksta faila sasp.dat vienīgajā rindā dota burtu virkne saspiestā formā. Tās garums nepārsniedz 100 simbolus.

 
 Izvaddati

Teksta faila sasp.rez vienīgajā rindā jāizvada burtu virkne nesaspiestā formā. Zināms, ka virknes garums nesaspiestā formā nepārsniedz 250 simbolus.

 
 Piemērs

sasp.datsasp.rez
2AB3CCC
AABCCCCC
  
sasp.datsasp.rez
F2(2(3FF))
FFFFFFFFFFFFFFFFF
  
sasp.datsasp.rez
F2(2(3(FF)))
FFFFFFFFFFFFFFFFFFFFFFFFF
  
sasp.datsasp.rez
21EU
EEEEEEEEEEEEEEEEEEEEEU

 
 Atsauces
Uzdevums izmantots Latvijas 17.informātikas olimpiādes rajona kārtā 2004.gadā

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS