== 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$.
 
!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.

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.

h2. Date de intrare

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.

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

h2. Date de ieşire

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.

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

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 |

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

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

|
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