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:
| Simbols | Signāla veids |
|---|---|
| S | Svilpiens |
| P | Pīkstiens |
| R | Rūciens |
| X | Svilpiens vai pīkstiens (noteikti nav rūciens) |
| Y | Svilpiens vai rūciens (noteikti nav pīkstiens) |
| Z | Pī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.
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.
Teksta faila petnieki.out vienīgajā rindā jāizvada viens vesels pozitīvs skaitlis - īsākā iespējamā ziņojuma garums sekundēs.
| petnieki.in | petnieki.out |
13 |
3 |