Fişierul intrare/ieşire:hotdogs.in, hotdogs.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Hot Dogs (clasele 9-10)

Pe o stradă sunt N clădiri aşezate în linie, numerotate de la 1 la N. Iniţial, toate clădirile sunt nelocuite. În fiecare zi pe stradă se mută cineva: fie într-o clădire se mută oameni noi, fie unii dintre oamenii dintr-o clădire pleacă.

Un vânzător de hot dogs vine în fiecare zi la muncă, aducând cu el toneta mobilă cu hot dogs delicioşi. Pentru a avea vad, el doreşte să plaseze toneta cât mai aproape de centrul demografic al străzii. Mai exact, dacă p(i) este populaţia curentă a clădirii cu numărul i, vânzătorul vrea să plaseze toneta în dreptul unei clădiri k, cu k minim astfel încât p(1) + p(2) + ... + p(k) ≥ p(k + 1) + p(k + 2) + ... + p(n).

Vânzătorul vă roagă să-i spuneţi, la sfârşitul fiecărei zile, unde să se posteze a doua zi dimineaţă.

Date de intrare

Fişierul de intrare hotdogs.in conţine pe prima linie numerele N Z, unde N este numărul de clădiri, iar Z este numărul de zile în care vânzătorul vine pe stradă. Pe următoarele Z linii apar perechi de numere K V, cu semnificaţia că în/din clădirea K se mută V oameni. Când V este pozitiv, oamenii se mută în clădire, iar când V este negativ, oamenii pleacă din clădire.

Date de ieşire

În fişierul de ieşire hotdogs.out se vor scrie Z numere, câte unul pe linie. Al i-lea număr reprezintă poziţia centrului demografic la sfârşitul zilei i.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ Z ≤ 100.000
  • V ≠ 0
  • Prin plecarea locatarilor, o clădire poate deveni nelocuită, dar (evident) nu poate avea populaţie negativă.
  • Populaţia totală a străzii (suma populaţiei clădirilor) va varia între 1 şi 1.000.000.000.

Exemplu

hotdogs.inhotdogs.out
10 4
4 5
2 10
7 6
4 -1
4
2
4
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici