Fişierul intrare/ieşire:criza.in, criza.outSursăCCEX 2009
AutorAntoneta Lazarescu, Gabriela CoajaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.2 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Criza

Primăria localitaţii CCEX a construit o şosea in linie dreaptă. Fiecare familie din oraş şi-a stabilit de-a lungul şoselei o aşezare în care locuiesc toţi membrii familiei şi unde îşi păstrează şi proviziile. Cetăţenii oraşului sunt foarte harnici şi au adunat cantităţi de provizii impresionante, care depăşesc nevoile lor. Prin urmare, primarul a decis ca fiecare familie să invite în ziua de 6 iunie câţiva prieteni (acelaşi număr de prieteni pentru fiecare familie).
Se cunoaşte numărul de porţii adunate în plus (care pot fi oferite prietenilor) de fiecare familie şi faptul că fiecare prieten va fi servit cu exact o porţie.
Proviziile adunate de o familie pot fi consumate în familia respectivă, sau pot fi donate altor familii, caz în care proviziile trebuie transportate. Familiile care asigură transportul consumă o porţie pentru fiecare metru de drum pe şosea, indiferent de cantitatea transportată.
Scrieţi un program care să determine numărul maxim de prieteni care pot fi găzduiţi în fiecare familie (acelaşi pentru toate familiile).

Date de intrare

Fişierul de intrare criza.in conţine pe prima linie un număr natural N care reprezintă numărul de familii. Următoarele N linii conţin informaţii despre familiile din oraş. Mai exact, pe linia i+1 se află două numere naturale separate prin spaţiu Ai Bi, unde Ai reprezintă poziţia în care locuieşte familia i (exprimată în număr de metri faţă de intrarea pe şosea), iar Bi reprezintă numărul de porţii adunate în plus de familia i. Familiile sunt specificate în ordinea în care se află plasate pe şosea.

Date de ieşire

Fişierul de ieşire criza.out va conţine o singură linie pe care va fi scris numărul maxim de prieteni ce pot fi găzduiţi de fiecare familie.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ Ai ≤ 109, 0 ≤ Bi ≤ 109
  • Nu există două familii situate în aceeaşi poziţie

Exemplu

criza.incriza.out
4
20 300
40 400
340 700
360 600
415
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content