- Nosaukums
- Abrakadabra (abraka)
- Laika limits
- 1.00s
- Atmiņas limits
- 256.0 MB
- Grūtība
-
60%
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.