RRMST

rrmst

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

Fie $P$ o permutare de lungime $N$, aleasă *aleatoriu* cu probabilitate uniformă din mulţimea tuturor permutărilor de lungime $N$. Vom desena în plan toate punctele de forma $(i, P[i])$. Distanţa dintre două puncte $(x1, y1)$ şi $(x2, y2)$ este dată de valoarea $|x1 - x2| + |y1 - y2|$. Se cere să se calculeze costul arborelui parţial de cost minim al setului de puncte date.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $rrmst.in$ va conţine pe prima sa linie numărul $N$. Următoarele $N$ lini vor conţine câte o pereche de numere $x y$, semnificând coordonatele unui punct din set. Se garantează că setul de puncte este obţinut prin metoda descrisă în enunţ.

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

h2. Date de ieşire

În fişierul de ieşire $rrmst.out$ va conţine o singură valoare, costul arborelui parţial de cost minim al setului de puncte dat.

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

h2. Restricţii

* $Testele 1 - 3 au N = 1.000$
* $Testele 4 - 10 au N = 100.000$

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

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

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

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

|

h3. Explicaţie
 
...
 

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