apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

abraka Abrakadabra 1 sek.


 Uzdevums

Datu saspiešanas algoritms, kas darbojas pēc "bloku saspiešanas"metodes, pielieto datu blokiem sekojošu pārveidojumu.
Simbolu virkni P sauc par simbolu virknes S rotāciju, ja tā iegūta cikliski pārbīdot S simbolus, t.i., ja S=a1a2...aN, kur ai - virknes S i-tais elements, tad P=apap+1...aNa1..ap-1, kur 1<=p<=N.

Aplūkosim tabulu M, kas sastāv no N rindām un N kolonnām, kur katrā rindā ir kāda no S rotācijām. Tabulā ir visas rotācijas, kas sakārtotas leksikogrāfiskā(vārdnīcas) secībā augošā secībā.

L ir virkne, ko veido matricas M pēdējā kolonna. Tiešais pārveidojums dotai virknei S kā rezultātu atdod virkni L un skaitli K - tās tabulas M rindas numuru, kurā ierakstīta virkne S. (Ja tādas ir vairākas, tiek atdots jebkurš no numuriem.)
Virknei S='abraka' tabula M ir sekojoša:
aabrak
abraka
akaabr
brakaa
kaabra
rakaab

Virkne S atrodas tabulas otrajā rindā. L='karaab'.

Uzrakstiet programmu, kas veic apgriezto pārveidojumu - dotai virknei L un skaitlim K atrod virkni S.

 
 Ievaddati

Teksta faila abraka.in pirmā rinda satur naturālus skaitļus K un N, kas atdalīti ar tukšumsimbolu. 1<=N<=30000, 1<=K<=N.
Faila otrā rinda satur N latīņu alfabēta mazos burtus - virkni L.

 
 Izvaddati

Teksta faila abraka.out vienīgajā rindā jāizvada virkne S.

 
 Piemērs

abraka.inabraka.out
2 6
karaab
abraka

 
 Atsauces
Uzdevums izmantots Ukrainas XV informātikas olimpiādē 2002.gadā.

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS