| Fişierul intrare/ieşire: | br.in, br.out | Sursă | ONI 2009 clasa a 9-a |
| Autor | Cristian George Strat | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | br.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.
