Siui

siui

== include(page="template/taskheader" task_id="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.

Poveste şi cerinţă...

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

Fişierul de intrare $siui.in$ ...

h2. 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ă.

În fişierul de ieşire $siui.out$ ...

h2. Restricţii

* 0<n<=10000;
* Numărul de cereri asociat iniţial fiecărui server p[i]<=9999;

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. siui.in |_. siui.out |

| 5
0 1 6 1 2
| 3

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

...
 

== include(page="template/taskfooter" task_id="siui") ==