Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-12-21 04:54:27.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rrmst.in, rrmst.out | Sursă | Happy Birthday Infoarena 2014 |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 54096 kbytes |
| Scorul tău | N/A | Dificultate | N/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ă perechi de 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ătoarea linie va conţine N numere, reprezentând permutarea P.
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 indus de permutarea P.
Restricţii
- Testele 1 - 3 au N = 1.000
- Testele 4 - 10 au N = 100.000
Exemplu
| rrmst.in | rrmst.out |
|---|---|
| 5 4 2 3 1 5 | 9 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
