Fişierul intrare/ieşire:	cifru2.in, cifru2.out	Sursă	Baraj 2006
Autor	Nistor Eugen Mot	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.05 sec	Limită de memorie	20096 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cifru 2

Copiii solarieni se joaca adesea trimitandu-si mesaje codificate. Pentru codificare ei folosesc un cifru bazat pe o permutare p a literelor alfabetului solarian si un numar natural d.
Alfabetul solarian contine m litere foarte complicate, asa ca noi le vom reprezenta prin numere de la 1 la m.
Dat fiind un mesaj in limbaj solarian, reprezentat de noi ca o succesiune de n numere cuprinse intre 1 si m, c₁ c₂ ... c_n, codificarea mesajului se realizeaza astfel: se inlocuieste fiecare litera c_i cu p(c_i), apoi sirul obtinut p(c₁) p(c₂) ... p(c_n) se roteste spre dreapta, facand o permutare circulara cu d pozitii rezultand sirul p(c_n-d+1), ... ,p(c_n-1), p(c_n), p(c₁), p(c₂)... p(c_n-d).
De exemplu, pentru mesajul 2 1 3 3 2 1, permutarea p=(3 1 2) (adica p(1)=3, p(2)=1, p(3)=2) si d=2. Aplicand permutarea p vom obtine sirul 1 3 2 2 1 3, apoi rotind spre dreapta sirul cu doua poziÅ£ii obtinem codificarea 1 3 1 3 2 2.

Cerinta

Date fiind un mesaj necodificat si codificarea sa, determinati cifrul folosit (permutarea p si numarul d).

Date de intrare

Fisierul de intrare cifru.in contine pe prima linie numele naturale n si m, separate prin spatiu, reprezentand lungimea mesajului si respectiv numarul de litere din alfabetul solarian. Pe cea de a doua linie este scris mesajul necodificat ca o succesiune de n numere cuprinse intre 1 si m separate prin cate un spatiu. Pe cea de a treia linie este scris mesajul codificat ca o succesiune de n numere cuprinse intre 1 si m separate prin cate un spatiu.

Date de iesire

Fisierul de iesire cifru.out va contine pe prima linie numarul natural d, reprezentand numarul de pozitii cu care s-a realizat permutarea circulara spre dreapta. Daca pentru d exista mai multe posibilitati se va alege valoarea minima. Pe urmatoarea linie este descrisa permutarea p. Mai exact se vor scrie valorile p(1), p(2), …, p(m) separate prin cate un spatiu.

Restrictii

• {$ 2 ≤ n ≤ 100 000 $}
• {$ 2 ≤ m ≤ 9999 $}
• Mesajul contine fiecare numar natural din intervalul [1, m] cel putin o data.

Exemplu

Explicatie

...

Cum se trimit solutii?