Fişierul intrare/ieşire:wanted.in, wanted.outSursăpreONI 2008, Runda finala
AutorAdrian DiaconuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 oras folosind strada principala si potecile respective. In momentul in care ajunge intr-un oras intreaba locuitorii despre Gigel. Acestia ii vor spune daca Gigel este in orasul respectiv, daca el se afla intr-un oras cu coordonata X mai mare sau mai mica.
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 ≤ 10.000
  • 0 ≤ Yi ≤ 10.000
  • Nu vor exista doua orase la coordonate X egale
  • Rezultatul nu va fi mai mare de 2 000 000 000

Exemplu

wanted.inwanted.out
4
-10 3
-5 2
5 4
8 2
32

Explicatie

Eduard merge in orasul 2. Daca 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 orasul 2 si 2+5+3 pentru a ajunge in orasul 1 deci total 17. Altfel va merge in orasul 3 de unde, in cazul in care nu il va gasi pe Gigel trebuie sa mearga si in orasul 4. Costul total pentru acest caz va fi 32.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content