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

Pentru un numar natural nenul n, sa consideram toate numerele naturale nenule mai mici sau egale cu n, luand fiecare numar de cate doua ori: 1, 1, 2, 2, 3, 3, ... , n, n. Aceste numere le amestecam aleator, si le aranjam pe doua linii a cate n elemente. Structura astfel obtinuta o vom numi o bipermutare. In figurile 1, 2 si 3 avem cate un exemplu de bipermutare pentru n=5.
O bipermutare este perfecta, daca ambele linii ale structurii reprezinta cate o permutare (vezi figurile 2 si 3).
Prin mutare pe pozitia p, intelegem interschimbarea elementelor de pe aceeasi coloana p. In exemplele de mai jos, bipermutarea perfecta din figura 2 s-a obtinut din bipermutarea din figura 1, aplicand o mutare pe pozitia 2. Bipermutarea perfecta din figura 3 s-a obtinut din bipermutarea din figura 1, aplicand mutari pe pozitiile 1, 2, 4 si 5.

Pentru un numar natural nenul $n$, sa consideram toate numerele naturale nenule mai mici sau egale cu $n$, luand fiecare numar de cate doua ori: $1$, $1$, $2$, $2$, $3$, $3$, ... , $n$, $n$. Aceste numere le amestecam aleator, si le aranjam pe doua linii a cate $n$ elemente. Structura astfel obtinuta o vom numi o bipermutare. In figurile $1$, $2$ si $3$ avem cate un exemplu de bipermutare pentru $n=5$.
O bipermutare este perfecta, daca ambele linii ale structurii reprezinta cate o permutare (vezi figurile $2$ si $3$).
Prin mutare pe pozitia $p$, intelegem interschimbarea elementelor de pe aceeasi coloana $p$. In exemplele de mai jos, bipermutarea perfecta din figura $2$ s-a obtinut din bipermutarea din figura $1$, aplicand o mutare pe pozitia $2$. Bipermutarea perfecta din figura $3$ s-a obtinut din bipermutarea din figura $1$, aplicand mutari pe pozitiile $1$, $2$, $4$ si $5$.
 
!problema/biperm?biperm.jpg!
 
h2. Cerinta
 
Cunoscand o bipermutare, determinati:
 
* numarul bipermutarilor perfecte distincte ce se pot obtine prin mutari;
 
* numarul minim de mutari prin care se poate obtine o bipermutare perfecta;
 
* o bipermutare perfecta obtinuta din bipermutarea initiala.

h2. Date de intrare

Fişierul de intrare $biperm.in$ ...

Fişierul de intrare $biperm.in$ contine pe prima linie valoarea lui $n$. Urmatoarele doua linii contin, fiecare, cate $n$ elemente separate prin cate un spatiu, formand o bipermutare.

h2. Date de ieşire

În fişierul de ieşire $biperm.out$ ...

Fişierul de ieşire $biperm.out$ va contine:
 
* pe prima linie doua numere naturale separate printr-un spatiu, reprezentand numarul bipermutarilor perfecte distincte ce se pot obtine din bipermutarea data, respectiv numarul minim de mutari prin care se poate obtine o bipermutare perfecta;
* pe urmatoarele doua linii se vor tipari cate $n$ numere separate prin spatiu, reprezentand o bipermutare perfecta obtinuta din bipermutarea data.

h2. Restricţii

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

* $2 < n ≤ 10 000$
 
* calculul corect al numarului bipermutarilor perfecte distincte valoreaza $30%$ din punctaj.
 
* calculul corect al numarului minim de mutari valoreaza $10%$ din punctaj.
 
* tiparirea unei bipermutari perfecte valoreaza $60%$ din punctaj. Pot exista mai multe solutii, se va admite orice solutie corecta.
 
* se garanteaza ca numarul bipermutarilor perfecte distincte nu depaseste $2 000 000 000$ pentru niciun test.
 
* acordarea punctajului la un raspuns corect este conditionata de existenta raspunsurilor anterioare, indiferent de corectitudinea lor.
 
* pentru $40%$ din teste $n ≤ 20$
 
* pentru $40%$ din teste $20 < n ≤ 400$
 
* pentru $20%$ din teste $400 < n ≤ 10 000$

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

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

| 5
  1 5 5 3 4
  3 2 2 4 1
| 4 1
  1 2 5 3 4
  3 5 2 4 1

|
h3. Explicaţie

...

Sunt $4$ permutari perfecte. Numarul minim de mutari este $1$ si exista doua solutii cu numr minim de mutari:
$1 2 5 3 4$
$3 5 2 4 1$
si
$1 5 2 3 4$
$3 2 5 4 1$
Celelalte doua solutii, ce nu se obtin din numar minim de mutari sunt:
$3 2 5 4 1$
$1 5 2 3 4$
si
$3 5 2 4 1$
$1 2 5 3 4$
Pentru a treia cerinta oricare dintre cele $4$ solutii este acceptata.

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

9945