Fişierul intrare/ieşire:rrmst.in, rrmst.outSursăHappy Birthday Infoarena 2014
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test3 secLimită de memorie54096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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

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.

Restricţii

  • Testele 1 - 3 au N = 1.000
  • Testele 4 - 10 au N = 100.000

Exemplu

rrmst.inrrmst.out
5
2 2
1 4
3 3
5 5
4 1
12
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?