Nosaukums
Lāču spēle (bear_game)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

Lācim Jānim patīk izdomāt sarežģītas spēles un ar tām izaicināt savu draugu, Lāci Mārtiņu. Ja Lācis Mārtiņš spēj uzvarēt Lāča Jāņa izdomātajā spēlē, tad Lācis Jānis dāvina Lācim Mārtiņam podu ar medu. Bet, ja Lācis Jānis ir izdomājis spēli, kurā Lācis Mārtiņš nespēj uzvarēt, Lācim Mārtiņam ir jādod 3 medus podi. Izklausās negodīgi, bet Lācis Mārtiņš ir aprēķinājis varbūtību ar kādu viņš parasti uzvar Lāča Jāņa izdomātajās spēlēs, un solot 3 podus par zaudējumu spēlē, viņš iegūst visvairāk.

Kādu dienu Lācis Jānis nāca klajā ar jaunu spēli, kura vēlāk izrādījās Lāča Mārtiņa mīļākā spēle, jo tā bija gaužām vienkārša. Spēle bija sekojoša: Lācis Jānis ar koku uz zemes uzrakstīja latīņu alfabēta burtu virkni, kurā katrs burts parādās tieši vienu reizi. Lācim Mārtiņam uz zemes ir jāuzraksta pareiza "transformācijas permutācija", ar kuras palīdzību uz zemes uzrakstīto virkni var transformēt atpakaļ uz virkni, kurā ir uzrakstīti visi latīņu alfabēta burti no a līdz z. Transformācijas permutācija ir pirmo 26 naturālo skaitļu permutācija. Transformācijas permutācijas pirmais skaitlis norādīs uz to, kurā pozīcijā pēc transformācijas jānokļūst simbolam, kurš atrodas virknes pirmajā pozīcijā, otrais norāda uz to, kurā pozīcijā, pēc transformācijas, jānokļūst simbolam, kurš atrods 2. pozīcijā un tā tālāk.

Piemēram: "bcadefghijklmnopqrstuvwxyz" transformācijas permutācija būs: 2,3,1,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26 .

Lācis Mārtiņš šajā spēlē uzvarēja katru reizi. Lācis Jānis negribēja atdot kārtējo medus podu, tāpēc viņš izdomāja spēli nedaudz sarežģīt. Lācim Mārtiņam ir jāizdomā transformācijas permutācija, ar kuras palīdzību transformējot Lāča Jāņa uzrakstīto virkni DIVREIZ  var iegūt virkni, kurā visi latīņu alfabēta burti sakārtoti no a līdz z.

Piemēram: "bcadefghijklmnopqrstuvwxyz" transformācijas permutācija varētu būt: 3,1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26

Pēc pirmās transformācijas: "cabdefghijklmnopqrstuvwxyz", pēc otrās - "abcdefghijklmnopqrstuvwxyz".

Lācis Mārtiņš saprata, ka šī spēle vairs nav tik vienkāršā, un viņš negrib atdot 3 podus ar medu. Palīdzi Lācim Mārtiņam uzvarēt šajā spēlē, un atrodi prasīto transofrmācijas permutāciju, ja tāda eksistē. Ja ir vairākas šādas permutācijas, jāizvada leksikogrāfiski mazākā no tām.


Ievaddatu raksturojums

Pirmajā un vienīgajā ievaddatu rindā ir dota 26 simbolu gara virkne, kurā katrs mazais latīņu alfabēta burts parādās tieši vienu reizi.


Izvaddatu raksturojums

Izvaddatu pirmajā rindā ir jāizvada "Nav", ja šādas transformācijas permutācijas neeksistē. Izvaddatu pirmajā rindā ir jāizvada "Ir", ja šāda transformācijas permutācija eksistē un, ja eksistē, tad otrajā izvaddatu rindā ir jāizvada transformācijas permutācija, kur katrs permutācijas elements atdalīts ar atstarpi.


Paraugdati

Stdin
abcdefghijklmnopqrstuvwxyz
Stdout
Ir
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

Stdin
jcqndkrszeiuwplyvgbmxaftho
Stdout
Nav

Stdin
bcadefghijklmnopqrstuvwxyz
Stdout
Ir
3 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

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