== include(page="template/taskheader" task_id="agitatie") ==
Poveste si cerinta...
O firma producatoare de software organizeaza un interviu pentru ocuparea unui post de programator, la care s-au prezentat $N$ candidati. Acestia sunt ordonati in functie de momentul la care si-au trimis CV-ul si numerotati cu numere consecutive de la {$1$} la {$N$}. Fiecarui candidat i-a fost realizat in prealabil un profil psihologic si i s-a determinat nivelul de agitatie provocat de interviul care urmeaza sa aiba loc, precum si un sens (crescator sau descrescator) de modificare a acestui nivel. Astfel, la ora la care s-a anuntat inceperea interviului (pe care o vom considera momentul {$0$}), fiecare candidat are un nivel de agitatie initial. Pentru fiecare unitate de timp dupa momentul $0$ si pana in momentul in care candidatul este invitat pentru interviu (pana atunci el trebuind sa astepte), nivelul sau de agitatie se modifica cu {$1$}: pentru o parte din candidati nivelul creste cu $1$ unitate, iar pentru ceilalti nivelul scade cu $1$ unitate. Daca nivelul de agitatie a unui candidat ajunge la {$0$}, din acel moment, pentru fiecare unitate de timp urmatoare, nivelul de agitatie va creste cu $1$ (se schimba sensul de modificare a nivelului de agitatie).
Firma va invita candidatii la interviu in grupuri, in ordinea numerotarii (toti candidatii avand numere de ordine mai mici decat un candidat $K$ vor fi invitati intr-un grup anterior sau in acelasi grup cu candidatul {$K$}). Inainte de a invita un grup, comisia ce conduce interviul poate decide sa astepte un numar intreg de unitati de timp (zero sau mai multe). Pentru un grup, durata interviului se considera neglijabila (fiecare candidat trebuie doar sa raspunda la cateva intrebari de tip grila). Din momentul in care un candidat este invitat la interviu, nivelul de agitatie a acestuia ramane constant. Deoarece firma doreste ca, indiferent de rezultatul interviului, toti candidatii sa ramana cu o parere buna, comisia va forma grupurile si va alege timpii de asteptare in asa fel incat suma totala a nivelelor de agitatie a candidatilor la sfarsitul interviului sa fie minima.
h2. Cerinta
Sa se scrie un program care sa determine suma totala minima a nivelelor de agitatie a candidatilor la sfarsitul interviului.
h2. Date de intrare
...
Fisierul de intrare $agitatie.in$ are pe prima linie numarul natural {$N$}, reprezentand numarul de candidati. Pe urmatoarele $N$ linii se afla cate doua numere intregi $A$ si {$B$}, separate printr-un spatiu. $A$ reprezinta nivelul initial de agitatie a candidatului, iar $B$ reprezinta sensul de modificare a agitatiei pentru fiecare unitate de timp in care acesta asteapta (daca $B$ este {$1$}, atunci nivelul de agitatie creste, iar daca $B$ este {$-1$}, nivelul de agitatie scade). Linia $k+1$ din fisier va contine valorile corespunzatoare candidatului cu numarul {$k$}.
h2. Date de iesire
...
Fisierul de iesire $agitatie.out$ va contine pe prima (si singura) linie suma totala minima a nivelelor de agitatie a candidatilor la sfarsitul interviului.
h2. Restrictii
* $... ≤ ... ≤ ...$
* {$1 ≤ N ≤ 3000$}
* {$1 ≤ nivelul initial de agitatie a fiecarui candidat ≤ 3000$}
h2. Exemplu
table(example). |_. agitatie.in |_. agitatie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
10 1
3 -1
2 -1
1 -1
9 1
6 -1
| 23
|
h3. Explicatie
...
Suma totala minima este {$23$}. O posibila solutie este urmatoarea: Se formeaza $3$ grupuri. Primul grup este format doar din candidatul $1$ si asteapta $0$ unitati de timp. Prin urmare, nivelul final de agitatie a candidatului $1$ va fi {$10$}. Al doilea grup va astepta $2$ unitati de timp din momentul in care a terminat interviul primul grup (deci va incepe interviul la momentul {$2$}), iar din grup vor face parte candidatii {$2$}, {$3$}, {$4$} si {$5$}. Nivelele finale de agitatie a acestor candidati vor fi: {$1$}, {$0$}, {$1$} si {$11$}. Observati ca nivelul de agitatie a candidatului $4$ a scazut intai pana la {$0$}, apoi a crescut la {$1$}. Al {$3$}-lea grup va mai astepta $4$ unitati de timp (deci va incepe interviul la momentul {$6$}), iar din grup va face parte doar candidatul {$6$}. Nivelul final de agitatie a acestuia va fi {$0$}.
== include(page="template/taskfooter" task_id="agitatie") ==
== SmfTopic(topic_id="...") ==
