Nosaukums
Abrakadabra (abraka)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

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:

a   a   b   r   a   k  
a   b   r   a   k   a  
a   k   a   a   b   r  
b   r   a   k   a   a  
k   a   a   b   r   a  
r   a   k   a   a   b  

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

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


Ievaddatu raksturojums

Izvaddatu 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.


Izvaddatu raksturojums

Ievaddatu vienīgajā rindā jāizvada virkne S.


Piezīmes

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


Paraugdati

Stdin
2 6
karaab
Stdout
abraka

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.