Fişierul intrare/ieşire:examen.in, examen.outSursăOlimpiada locală 2015, clasele 11-12
AutorRodica PinteaAdăugată deanarogozAna Rogoz anarogoz
Timp execuţie pe test0.3 secLimită de memorie5000 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Examen (clasele 11-12)

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.

Date de intrare

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.

Date de ieşire

Î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

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

examen.inexamen.out
4
1 1
6 1
6 6
3 4
5
2
examen.inexamen.out
4
1 1
6 1
6 6
1 6
6
4

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).

Exemplul 2

Trebuie sa te autentifici pentru a trimite solutii. Click aici