Fişierul intrare/ieşire:bomboane4.in, bomboane4.outSursăCodeforces
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.2 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Bomboane4

Avem N coşuri cu bomboane, al i-lea coş conţine bi 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 bst, bst + 1, ..., bdr devine egal cu (bst + bst + 1 + ... + bdr) / (dr - st + 1) (adică fiecare elemente din subşir devine egal cu media elementelor din subşir).

Poţi aplica această operaţie de oricâte ori vrei.

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.

Date de intrare

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.

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

Restricţii

  • 1 ≤ n ≤ 100 000
  • 1 ≤ bi ≤ 40 000
  • bi sunt numere întregi
  • Pentru 40p n ≤ 6000

Exemplu

bomboane4.inbomboane4.outExplicaţie
4
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ă.
Trebuie sa te autentifici pentru a trimite solutii. Click aici