== include(page="template/taskheader" task_id="comp2") ==
Intr-o companie lucreaza $N$ persoane. Fiecare persoana face parte dintr-unul din departamentele companiei si are o funcţie de sef sau de simplu angajat. Fiecare sef dintr-un departament interactioneaza cu fiecare angajat din acelasi departament (dar nu si cu ceilalti sefi). Eficienta unui departament este egala cu numarul de interactiuni distincte (sef, angajat) ce au loc in departamentul respectiv. Eficienta ce caracterizeaza intreaga companie este egala cu suma gradelor de eficienţa ale fiecarui departament.
Intr-o companie lucreaza $N$ persoane. Fiecare persoana face parte dintr-unul din departamentele companiei si are o functie de sef sau de simplu angajat. Fiecare sef dintr-un departament interactioneaza cu fiecare angajat din acelasi departament (dar nu si cu ceilalti sefi). Eficienta unui departament este egala cu numarul de interactiuni distincte (sef, angajat) ce au loc in departamentul respectiv. Eficienta ce caracterizeaza intreaga companie este egala cu suma gradelor de eficienta ale fiecarui departament.
Directorul companiei stie ca eficienta firmei sale este egala cu E. Totusi, pentru ca aceasta sa reprezinte un indicator economic relevant, ea trebuie obtinuta cu un numar minim de persoane si, in cazul in care se poate obtine in mai multe feluri cu acelasi numar minim de persoane, cu cat mai puţini sefi (se stie ca sefii lucreaza mult mai putin decat angajatii simpli).
Directorul companiei stie ca eficienta firmei sale este egala cu $E$. Totusi, pentru ca aceasta sa reprezinte un indicator economic relevant, ea trebuie obtinuta cu un numar minim de persoane si, in cazul in care se poate obtine in mai multe feluri cu acelasi numar minim de persoane, cu cat mai putini sefi (se stie ca sefii lucreaza mult mai putin decat angajatii simpli).
Scrieti un program care determina numarul minim de persoane necesare, ÅŸi pentru acest numar, numarul minim de ÅŸefi, pentru ca eficienta companiei sa fie egala cu E. Determinati, de asemenea, structura companiei, pe departamente.
Scrieti un program care determina numarul minim de persoane necesare, si pentru acest numar, numarul minim de sefi, pentru ca eficienta companiei sa fie egala cu $E$. Determinati, de asemenea, structura companiei, pe departamente.
h2. Date de intrare
In fiÅŸierul $comp2.in$ se afla un singur numar intreg: $E$.
In fisierul $comp2.in$ se afla un singur numar intreg: $E$.
h2. Date de iesire
Pe prima linie a fisierului $comp2.out$ veti scrie 3 numere intregi: $N$ - numarul minim de persoane, $S$ - numarul minim total de sefi dintre cele $N$ persoane - ÅŸi $K$ – numarul de departamente ale companiei. Pe urmatoarele $K$ linii veti afisa cate $2$ numere întregi: $P{~i~}$, reprezentand numarul de persoane ce lucreaza in departamentul $i$ si $S{~i~}$, reprezentand numarul de sefi dintre cele $P{~i~}$ persoane {$(P{~i~}≥S{~i~})$}. Daca exista mai multe solutii cu aceleasi valori $N$ si $S$ minime, puteti afisa oricare dintre ele.
Pe prima linie a fisierului $comp2.out$ veti scrie 3 numere intregi: $N$ - numarul minim de persoane, $S$ - numarul minim total de sefi dintre cele $N$ persoane - si $K$ - numarul de departamente ale companiei. Pe urmatoarele $K$ linii veti afisa cate $2$ numere intregi: $P{~i~}$, reprezentand numarul de persoane ce lucreaza in departamentul $i$ si $S{~i~}$, reprezentand numarul de sefi dintre cele $P{~i~}$ persoane {$(P{~i~}≥S{~i~})$}. Daca exista mai multe solutii cu aceleasi valori $N$ si $S$ minime, puteti afisa oricare dintre ele.
h2. Restrictii
* $1 ≤ E ≤ 2000$
* Compania trebuie sa aiba cel putin un departament.
* $S{~1~}+S{~2~}+..+S{~K~}=S$
* $S{~1~} + S{~2~} + .. + S{~K~} = S$
* $P{~i~} ≥ 1$
* $1 ≤ S{~i~} ≤ P{~i~}$
