| 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, 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
- 2 ≤ n ≤ 100 000
- 2 ≤ m ≤ 9999
- Mesajul contine fiecare numar natural din intervalul [1, m] cel putin o data.
Exemplu
| cifru2.in | cifru2.out |
|---|---|
| 6 3 2 1 3 3 2 1 1 3 1 3 2 2 | 2 3 1 2 |
