Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | wanted.in, wanted.out | Sursă | preONI 2008, Runda finala |
| Autor | Adrian Diaconu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Wanted
Dupa ce unii din voi l-au ajutat pe Gigel sa iasa din inchisoare rezolvand problema gather acum politia este pe urmele lui. Exista N orase si se stie ca Gigel este ascuns in unul din ele. Avem o strada infinita care pentru simplitate o vom considera identica cu axa Ox a unui sistem cartezian de coordonate. Pentru fiecare oras i se stiu coordonatele (Xi,Yi). Fiecare oras are o poteca care este paralela cu axa Oy si care il leaga de strada principala. Politistul Eduard se afla in acest moment in punctul de coordonate (0,0) si poate merge in orice sat folosind strada principala si potecile respective. In momentul in care ajunge intr-un sat intreaba locuitorii despre Gigel. Acestia ii vor spune daca Gigel este in satul respectiv, daca el se afla intr-un sat cu coordonata X mai mare sau mai mica.
Cerinta
Ajutati-l pe Eduard spunandu-i care este distanta minima pe care trebuie sa o parcurga pe cazul cel mai defavorabil alegand o strategie optima de a vizita orasele.
Date de intrare
Fisierul de intrare wanted.in contine pe prima linie N, numarul de orase. Pe urmatoarele N linii se afla cate doua numere intregi Xi, Yi reprezentand coordonatele oraselor.
Date de iesire
In fisierul de iesire wanted.out se va scrie distanta ceruta.
Restrictii
- 1 ≤ N ≤ 200
- -10.000 ≤ Xi,Yi ≤ 10.000
Exemplu
| wanted.in | wanted.out |
|---|---|
| 4 -10 3 -5 2 5 4 8 2 | 31 |
Explicatie
Initial Eduard va merge in orasul 2. In cazul in care i se spune ca Gigel se afla intr-un oras cu coordonata X mai mica se va duce in 1 unde il va gasi pe Gigel. In acest caz costul va fi 5+2=7 pentru a ajunge in satul 2 si 2+5+3 pentru a ajunge in satul 1 deci totalul va fi 17. Altfel Eduard va merge in satul 3 de unde in cazul in care nu il va gasi pe Gigel trebuie sa mearga si in satul 4. Costul total pentru acest caz vai 31.
