Visuma pētnieki

ID: petnieki
Grūtība: 2/5
Laika limits: 1

Uzdevums

Visuma pētnieku pulciņa dalībnieki ilgākā laika posmā, izmantojot paškonstruētu aparatūru, ir ierakstījuši no kosmosa uztvertos signālus. Pulciņa dalībnieki ir noskaidrojuši, ka visus no visuma nākošos signālus var iedalīt svilpienos, pīkstienos un rūcienos. Beidzot signāli ir atkodēti un pierakstīti simbolu formā, izmantojot noteiktus latīņu alfabēta lielos burtus un punktus. Katrai ieraksta sekundei atbilst viens simbols virknē. Pieraksta simboli ir izvēlēti tā, lai būtu iespējams pierakstīt arī neprecīzu informāciju. Simbolu nozīme ir sekojoša:

SimbolsSignāla veids
SSvilpiens
PPīkstiens
RRūciens
XSvilpiens vai pīkstiens (noteikti nav rūciens)
YSvilpiens vai rūciens (noteikti nav pīkstiens)
ZPīkstiens vai rūciens (noteikti nav svilpiens)
. (punkts)Iespējams jebkurš signāla veids

Ja eksistē ārpuszemes civilizācija, tad visticamāk, ka viņi sūta atkārtojošos ziņojumus.

Tas nozīmē, ja šos ziņojumus pieraksta vienu otram galā bez pauzēm, tad ieraksts ir fragments no šīs garās virknes. Uzskatām, ka ieraksts satur vismaz vienu ziņojumu pilnībā.

Tā, piemēram, ja ieraksts ir SXXPS, tad tam atbilstošais ziņojums ir kāda no sekojošām signālu virknēm: SPPPS, SPSPS, SSPPS, SSSPS, SPPP, SPSP, SSPP, SSSP, PPPS, PSPS, SPPS, SSPS, SP vai PS. Īsākā iespējamā ziņojuma garums šajā gadījumā ir 2. Ievērojiet, ka ieraksta garumam nav noteikti jābūt ziņojuma daudzkārtnim un aplūkotajā piemērā simbolam X dazādās ziņojuma vietās var atbilst dažādi signāli.

Uzrakstiet programmu, kas dotam ierakstam nosaka īsākā iespējamā ziņojuma garumu sekundēs.

Ievaddati

Teksta faila petnieki.in pirmajā rindā dots vesels pozitīvs skaitlis n (n <= 1000) - ieraksta garums. Faila otrajā rindā dota n simbolu virkne - ieraksta saturs.

Izvaddati

Teksta faila petnieki.out vienīgajā rindā jāizvada viens vesels pozitīvs skaitlis - īsākā iespējamā ziņojuma garums sekundēs.

Piemērs

petnieki.in petnieki.out
13
SPR.XZ..YY.ZS
3

Piezīme: Iespējamie īsākie ziņojumi ir SPR, PRS vai RSP.


© 2001-2002 olimps! http://www.lio.lv/olimps/