| Fişierul intrare/ieşire: | siui.in, siui.out | Sursă | ad-hoc |
| Autor | Adăugată de |  CCEX2015 •CCEX2015 | |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 8096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Siui
În sistemul informatic unic integrat al asigurărilor de sănătate, recent implementat, cererile de acces de la medici sunt prelucrate de n servere conectate într-o reţea de tip magistrală. Fiecare cerere este atribuită aleatoriu unui server, astfel încât unele dintre servere sunt supraîncărcate în timp ce altele stau. Se impune necesitatea redistribuirii cererilor de acces astfel incât sistemul să fie echilibrat. Echilibrarea are loc în reprize, la fiecare repriză fiecare server din sistem poate să cedeze sau să primească o cerere de acces de la vecinii săi direcţi(de exemplu, serverul i are ca vecini serverul i-1 şi serverul i+1, excepţie făcând serverul 1 care îl are ca vecin doar pe 2 şi serverul n care îl are ca vecin doar pe serverul n-1). Scopul echilibrării este să se atribuie fiecărui server exact acelaşi număr de cereri de acces. Având date numărul de severe şi numărul de cereri de acces asociate iniţial fiecărui server se cere să se afişeze numărul minim de reprize în care se echilibrează sistemul, dacă este posibil.
Date de intrare
Fişierul de intrare siui.in conţine pe prima linie valoarea lui n reprezentând numărul de servere, iar pe linia a doua numărul de cereri asociate iniţial fiecărui server.
Date de ieşire
Fişierul de ieşire siui.out va conţine numărul minim de reprize de schimb reciproc între servere necesare pentru echilibrarea sistemului, dacă acest lucru este posibil, respectiv valoarea -1 dacă echilibrarea nu este posibilă.
Restricţii
- 0<n<=10000;
- Numărul de cereri asociat iniţial fiecărui server p[i]<=9999;
Exemplu
| siui.in | siui.out |
|---|---|
| 5 0 1 6 1 2 | 3 |
Explicaţie
Prima repriză
1 1 4 2 2
Serverul 2 cedează serverului 1 o cerere şi primeşte de la serverul 3 o cerere, serverul 3 cedează şi serverului 4 o cerere şi serverului 2 o cerere iar serverul 4 primeşte de la serverul 3 o cerere.
A doua repriză
2 1 3 2 2
A treia repriză
2 2 2 2 2
