Fişierul intrare/ieşire:br.in, br.outSursăONI 2009 clasa a 9-a
AutorCristian George StratAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.05 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bere

N prieteni, numerotaţi de la 1 la N, beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte Ci – costul berii lui preferate. Din când în când, câte un prieten, fie el k, cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, incepand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni.

Cerinţă

Se cere numărul de beri pe care le va cumpăra fiecare prieten k în limita sumei x de bani de care dispune. În caz că x este mai mare decât costul berilor pentru toţi prietenii de la masă, se vor achiziţiona maxim N beri.

Date de intrare

Prima linie a fişierului de intrare br.in conţine două numere naturale N şi T separate printr-un spaţiu reprezentând numărul de prieteni şi respectiv numărul de prieteni care doresc să facă cinste prietenilor săi.
A doua linie a fişierului de intrare conţine N numere naturale C1, C2 ... CN, separate prin câte un spaţiu, reprezentând costurile berilor preferate de fiecare prieten. Berea pentru prietenul i are costul Ci.
Fiecare din următoarele T linii conţine câte două numere separate printr-un spaţiu:
k1 x1
k2 x2
...
kT xT
precizând indicele câte unui prieten care face cinste şi respectiv suma de bani de care acesta dispune..

Date de ieşire

Fişierul de ieşire br.out va conţine T linii, fiecare cu un singur număr Di reprezentând numărul de beri pe care le va cumpăra prietenul ki cu suma de bani xi in condiţiile problemei.

Restricţii

  • 1 ≤ N ≤ 15.000
  • 1 ≤ T ≤ 10.000
  • 1 ≤ Ci ≤ 100
  • 1 ≤ ki ≤ N
  • 1 ≤ xi ≤ 3.000.000
  • Un program corect, care se încadrează în timp pentru T ≤ 4000, va obţine cel puţin 30 de puncte
  • Un program corect, care se încadrează în timp pentru N ≤ 2000, va obţine cel puţin 60 de puncte
  • Prietenii beau numai berea lor preferată.

Exemplu

br.inbr.out
5 4
10 5 15 22 13
1 32
4 50
1 9
4 200
3
4
0
5

Explicaţie

Prietenul 1 cumpără câte o bere pentru el şi pentru prietenii 2, 3. Costul celor 3 beri este 30.
Prietenul 4 cumpără 4 beri: câte una pentru el şi pentru prietenii 5, 1, 2. Costul celor 4 beri este 50.
Cu 9 bani prietenul 1 nu poate cumpăra nici măcar berea lui.
Prietenul 4 cumpără 5 beri. Costul celor 5 beri este sub limita de cost 200.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content