Diferențe pentru problema/bomboane4 între reviziile #23 si #11

== include(page="template/taskheader" task_id="bomboane4") ==

Avem *N* coșuri cu bomboane, al [*i*]-lea coș conține *b[~i~]* bomboane. Coșurile sunt numerotate de la *1* la *n*. Poți aplica următoare operație: alegi un interval [*st*, *dr*] și redistribui bomboanele după următoarea regulă:

Avem *N* coșuri cu bomboane, al *i*-lea coș conține *b[~i~]* bomboane. Coșurile sunt numerotate de la *1* la *n*. Poți aplica următoare operatie: alegi un interval [*st*, *dr*] și redistribui bomboanele după următoarea regulă:

* Fiecare element din șirul *b[~st~]*, *b[~st + 1~]*, ..., *b[~dr~]* devine egal cu *(b[~st~] + b[~st + 1~] + ... + b[~dr~]) / (dr - st + 1)* (adică fiecare elemente din subșir devine egal cu media elementelor din subșir).

Dorel vrea să afle care este cel mai mic șir in ordine lexicografică la care se poate ajunge după aplicarea operațiilor.

_Notă: prin ordine lexicografică înțelegem sensul obișnuit, în care în loc de caractere avem numere raționale._
 

h2. Date de intrare

Fișierul de intrare $bomboane4.in$ conține pe prima linie *N*, numărul de coșuri. Pe următoarea linie avem cele *N* coșuri.

Fișierul de intrare bomboane4.in conține pe prima linie *N*, numărul de coșuri. Pe urmatoarea linie avem cele *N* coșuri.

h2. Date de ieșire

În fișierul de ieșire $bomboane4.out$ vom avea șirul dorit de Dorel. Deoarece elementele vor fi numere raționale fiecare element va fi scris ca o fracție ireductibilă. Fracțiile vor fi scrise pe linii separate, fiecare linie conținînd două numere întregi separate printr-un spațiu, anume numărătorul și numitorul fracției.

În fișierul de ieșire bomboane4.out vom avea șirul dorit de Dorel doar că fiecare element va fi scris ca o fracție ireductibiliă, fracțiile vor fi scrise pe linii separate.

h2. Restricții

* 1 ≤ *n* ≤ 100 000
* 1 ≤ *b[~i~]* ≤ 40 000
* *b[~i~]* sunt numere întregi
* Pentru 40p *n* ≤ 6000

* $1 ≤ *n* ≤ 100000$
* $1 ≤ *b[~i~]* ≤ 4000$
* $Pentru 20% din teste *n* ≤ 5000$

h2. Exemplu

table(example).
|_. bomboane4.in |_. bomboane4.out |_. Explicație |

table(example).
|_. bomboane4.in |_. bomboane4.out |

| 4

7 5 5 7

  7 5 5 7

| 17 3

17 3
17 3
7 1
| Vom aplica operația [1 3] în urma căreia șirul devine 5.(6)  5.(6)  5.(6)  7
Acesta este șirul minim lexicografic. Numerele sînt scrise în formă de fracție
ireductibilă.
|

  17 3
  17 3
  7 1
|

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