Fişierul intrare/ieşire:inundatii.in, inundatii.outSursăpreONI 2008 Runda 3
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.05 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Inundatii

Anul acesta este foarte posibil ca in orasul lui Zaharel sa aiba loc inundatii. Zaharel trebuie sa se gandeasca la un plan prin care sa protejeze cele N cladiri din orasul sau de inundatii. Pentru a simplifica problema vom considera o cladire ca fiind un punct in spatiu. In plus, cladirile din orasul lui Zaharel au niste proprietati interesante:

  • sunt numerotate cu numere distincte intre 1 si N
  • coordonatele sunt numere intregi
  • cladirea cu numarul i domina cladirea cu numarul i+1 pentru orice 1 ≤ i < N; formal, asta inseamna ca Xi > Xi+1, Yi > Yi+1 si Zi > Zi+1, unde (Xi, Yi, Zi) reprezinta pozitia cladirii cu numarul i

Dupa o lunga analiza, Zaharel a ajuns la concluzia ca cel mai sigur mod de a evita inundatiile este mutarea cladirilor astfel incat cladirea i sa domine cladirea i-1 pentru orice 1 < i ≤ N. Desigur, mutarea unei cladiri nu este o treaba usoara, asa ca Zaharel vrea sa minimize suma distantelor cu care se muta fiecare cladire.

Date de intrare

Fisierul de intrare inundatii.in contine pe prima linie numarul N, iar pe urmatoarele N linii cate 3 numere intregi Xi Yi Zi separate prin spatii, reprezentand pozitiile cladirilor.

Date de iesire

In fisierul de iesire inundatii.out se va scrie un singur numar natural, reprezentand suma distantelor cu care se muta fiecare cladire, in cazul cel mai favorabil.

Restrictii

  • 1 ≤ N ≤ 50.000
  • 0 ≤ Xi, Yi, Zi ≤ 108
  • Coordonatele la care se muta casele trebuie sa fie numere intregi
  • Se considera ca distanta dintre doua puncte (x1,y1,z1) si (x2,y2,z2) este |x1-x2|+|y1-y2|+|z1-z2|

Exemplu

inundatii.ininundatii.out
2
8 5 10
5 4 7
10

Explicatie

O solutie posibila este:
Se muta prima cladire de la (8,5,10) la (6,4,8), distanta fiind de |8-6|+|5-4|+|10-8|=2+1+2=5.
Se muta a doua cladire de la (5,4,7) la (7,5,9), distanta fiind de |5-7|+|4-5|+|7-9|=2+1+1=5.
Suma distantelor este 10, iar solutia este valida deoarece a doua cladire domina prima cladire (7 > 6, 5 > 4, 9 > 8).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content