Fişierul intrare/ieşire:cifru2.in, cifru2.outSursăBaraj 2006
AutorNistor Eugen MotAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.05 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultateN/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, c1 c2 ... cn, codificarea mesajului se realizeaza astfel: se inlocuieste fiecare litera ci cu p(ci), apoi sirul obtinut p(c1) p(c2) ... p(cn) se roteste spre dreapta, facand o permutare circulara cu d pozitii rezultand sirul p(cn-d+1), ... ,p(cn-1), p(cn), p(c1), p(c2)... p(cn-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 pozitii 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 cifru2.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 cifru2.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

  • 2n100 000
  • 2m9999
  • Mesajul contine fiecare numar natural din intervalul [1, m] cel putin o data.

Exemplu

cifru2.incifru2.out
6 3
2 1 3 3 2 1
1 3 1 3 2 2
2
3 1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content