Cifru 2

cifru2

== include(page="template/taskheader" task_id="cifru2") ==

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{~1~}$ $c{~2~}$ ... $c{~n~}$, codificarea mesajului se realizeaza astfel: se inlocuieste fiecare litera $c{~i~}$ cu {$p$}({$c{~i~}$}),  apoi sirul obtinut  {$p$}({$c{~1~}$}) {$p$}({$c{~2~}$}) ... {$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{~1~}$}), {$p$}({$c{~2~}$})... {$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 pozitii obtinem codificarea {$1 3 1 3 2 2$}.
 
h2. Cerinta
 
Date fiind un mesaj necodificat si codificarea sa, determinati cifrul folosit (permutarea $p$ si numarul $d$).

Poveste si cerinta...

h2. 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.

...

h2. 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.

...

h2. Restrictii

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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. cifru2.in |_. cifru2.out |

| 6 3
2 1 3 3 2 1
1 3 1 3 2 2
| 2
3 1 2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

== include(page="template/taskfooter" task_id="cifru2") ==
 

h3. Explicatie
...
== include(page="template/taskfooter" task_id="cifru2") ==

1795