== include(page="template/taskheader" task_id="twinperms") ==
Poveste şi cerinţă...
bq. Zi-mi ce alegi: ori ne-apărăm spatele, ori ni-l înjunghiem
Georgian şi Ştefan, căutând în 3 camere din casă, au găsit două permutări gemene, $p$ şi $q$, de mărime $N$. Atunci când cineva interschimba elementele de pe poziţiile $i$ şi $j$ dintr-o permutare, în paralel se interschimbau şi elementele de pe aceleaşi poziţii în cealaltă permutare. De exemplu, dacă cele două permutări sunt: $p = [2, 1, 3]$ şi $q = [3, 2, 1]$, atunci prin interschimbarea elementelor de pe poziţiile $1$ şi $3$, atunci permutările devin $p = [3, 1, 2]$ şi $q = [1, 2, 3]$. Ei pot aplica oricâte interschimbări de acest fel.
Şi Georgian şi Ştefan vor să îşi minimizeze numărul de inversiuni al permutărilor fiecăruia, dar pentru că de fiecare dată când cineva schimbă ceva la o permutare, se schimbă şi în cealaltă, atunci ei s-au decis să facă astfel încât numărul de inversiuni în total din ambele permutări să fie cât mai mic.
h2. Cerinţă
Dându-se două permutări de mărime $N$, calculaţi suma minimă a numărului de inversiuni din cele două permutări după ce se aplică operaţia de interschimbare descrisa mai sus de oricâte ori.
h2. Date de intrare
Fişierul de intrare $twinperms.in$ ...
Fişierul de intrare $twinperms.in$, pe prima linie se găseşte numărul $N$, ce reprezintă mărimile celor două permutări.
Pe următoarele două linii se află câte $N$ elemente, reprezentând cele două permutări $p$ şi $q$.
h2. Date de ieşire
În fişierul de ieşire $twinperms.out$ ...
În fişierul de ieşire $twinperms.out$ se va afişa un singur număr ce reprezintă suma minimă a numărului de inversiuni din cele două permutări.
h2. Restricţii
* $... ≤ ... ≤ ...$
* Permutările sunt indexate de la $1$ până la $N$.
* $1 ≤ N ≤ 100.000.$
* Pentru 10 puncte, avem $p{~i~} = q{~i~}$ pentru toate $i$, unde $1 ≤ i ≤ N$.
* Pentru alte 10 puncte, avem $p{~i~} + q{~i~} = N + 1$ pentru toate $i$, unde $1 ≤ i ≤ N$.
* Pentru alte 10 puncte, avem $1 ≤ N ≤ 9$.
* Pentru alte 15 puncte, avem $1 ≤ N ≤ 16$.
* Pentru alte 35 de puncte, avem $1 ≤ N ≤ 3.000$.
* O permutare de mărime $N$ este un şir de $N$ elemente unde fiecare număr de la $1$ până la $N$ apare exact o dată.
* Numărul de inversiuni dintr-o permutare $p$ este numărul de perechi $i, j$, unde $1 ≤ i < j ≤ N$, cu proprietatea că $p{~i~} > p{~j~}$.
h2. Exemplu
table(example). |_. twinperms.in |_. twinperms.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
3 4 1 2
1 4 2 3
| 2
|
h3. Explicaţie
...
Putem să interschimbăm elementele de pe poziţiile $1$ şi $3$, astfel permutările devin: $p = [1, 4, 3, 2]$ şi $q = [2, 4, 1, 3]$. După asta, putem interschimba elementele de pe poziţiile $2$ şi $3$, astfel permutările devin: $p = [1, 3, 4, 2]$ şi $q = [2, 1, 4, 3]$. La sfârşit, putem interschimba elementele de pe poziţiie $3$ şi $4$. Permutările vor ajunge în final: $p = [1, 3, 2, 4]$ şi $q = [2, 1, 3, 4]$. Cum prima permutare are o inversiune, şi anume cea de pe poziţiile $2$ şi $3$, iar a doua permutare are tot o singură inversiune, şi anume cea de pe poziţiile $1$ şi $2$, numărul total de inversiuni va fi 2. Această sumă este minimă.
== include(page="template/taskfooter" task_id="twinperms") ==
