== include(page="template/taskheader" task_id="examen") ==
Poveste și cerință...
La școala militară galactică, o mulțime de N dispozitive amorsate fictiv sunt plasate pe un teren plan, în puncte de coordonate întregi. Dispozitivele sunt numerotate de la 1 la N. Elevul WXP7 aflat la școala militară, pentru a trece o probă de examen, se va plasa într-un punct al terenului (tot de coordonate întregi) și va dezamorsa dispozitivele, în ce ordine dorește, folosind o telecomandă cu raza laser de acțiune reglabilă.
Astfel, el va regla telecomanda EXACT pentru distanța Manhattan la care se află un dispozitiv și va acționa cu ea asupra dispozitivului dezamorsându-l, apoi va regla telecomanda EXACT pentru distanța Manhattan la care se află un alt dispozitiv și va acționa cu ea dezamorsandu-l etc. până ce toate dispozitivele vor fi dezamorsate.
Costul total de dezamorsare (cel care va stabili calificativul elevului WXP7) este dat de distanța reglată pentru primul dispozitiv plus diferența (în valoare absolută) dintre distanța reglată inițial și distanța reglată pentru al doilea dispozitiv, plus diferența (în valoare absolută) dintre distanța reglată pentru al doilea dispozitiv și distanța reglată pentru al treilea dispozitiv etc. De exemplu, dacă sunt 4 dispozitive și ele, în ordinea în care sunt dezamorsate, se află la distanțele 8, 6, 2 și respectiv 8 de punctul în care se află WXP7 cu telecomanda, atunci costul inițial este 8, la care se adaugă 2 (8-6), la care se adaugă 4 (6-2), la care se mai adaugă 6 (8-2), obținând costul total 20.
Dacă poziția în care s-a plasat WXP7 conține unul dintre dispozitive, el se va dezamorsa automat, cu costul 0.
Cunoscându-se numărul N de dispozitive și pozițiile acestora în plan, să se determine costul total minim de dezamorsare și numărul de poziții în care se poate plasa WXP7, astfel încât, în oricare dintre aceste poziții s-ar situa WXP7, va exista o strategie prin care poate obține acest cost minim de dezamorsare.
h2. Date de intrare
Fișierul de intrare $examen.in$ ...
Din fișierul examen.in se citesc:
- de pe prima linie un număr natural N reprezentând numărul de dispozitive
- de pe următoarele N linii, câte două numere întregi, Xi Yi (i{1,…,N}), despărțite prin câte un spațiu, reprezentând coordonatele întregi, întâi abscisa și apoi ordonata, ale fiecărui dispozitiv.
h2. Date de ieșire
În fișierul de ieșire $examen.out$ ...
În fișerul examen.out se afișează:
- pe prima linie un număr natural C, reprezentând costul minim de dezamorsare
- pe linia următoarele un număr natural P reprezentând numărul de poziții în care se poate plasa WXP7 pentru a realiza un cost minim de dezamorsare
h2. Restricții
* $... ≤ ... ≤ ...$
• 0 < N < 100000
• –10000 ≤ Xi ≤ 10000 ; –10000 ≤ Yi ≤ 10000
• Distanța Manhattan între două puncte cu coordonatele X1, Y1 și respectiv coordonatele X2, Y2 se calculează cu ajutorul formulei: |X1-X2|+|Y1-Y2|
• Pentru fiecare dintre cele două valoari, C și P, se acordă 50% din punctaj
• Pentru 50% din teste, toate numerele din problemă sunt numere cu cel mult 4 cifre
h2. Exemplu
table(example).
|_. examen.in |_. examen.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|4
1 1
6 1
6 6
3 4
|5
2
|
table(example).
|_. examen.in |_. examen.out |
|4
1 1
6 1
6 6
1 6
|6
4
|
h3. Explicație
...
Exemplul 1. Pentru dispozitivele numerotate de la 1 la 4 din figura alăturată, elevul se poate situa în oricare dintre cele două poziții de coordonate 4 3 și respectiv 5 2 pentru a obține costul minim de dezamorsare, 5. Pentru amplasarea în punctul de coordonate 4 3, acest cost se obține dezamorsând întâi dispozitivul 4 (reglaj1=dist1=2), apoi dispozitivul 2 (reglaj2= |dist1-dist2|=2), apoi dsipozitivul 3 (reglaj3= |dist2-dist3|=1 și în final dispozitivul 1 (reglaj 4=|dist3-dist4|=0).
!problema/examen?exemplu1.png!
Exemplul 2
!problema/examen?exemplu2.png!
== include(page="template/taskfooter" task_id="examen") ==
