Diferente pentru problema/br intre reviziile #1 si #6

Diferente intre titluri:

br
Bere

Diferente intre continut:

== include(page="template/taskheader" task_id="br") ==
Poveste şi cerinţă...
$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 $C{~i~}$ – 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.
 
h2. 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.
h2. Date de intrare
Fişierul de intrare $br.in$ ...
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 $C{~1~}$, $C{~2~}$ ... $C{~N~}$, 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:
$k{~1~}$ $x{~1~}$
$k{~2~}$ $x{~2~}$
...
$k{~T~}$ $x{~T~}$
precizând indicele câte unui prieten care face cinste şi respectiv suma de bani de care acesta dispune..
h2. Date de ieşire
În fişierul de ieşire $br.out$ ...
Fişierul de ieşire $br.out$ va conţine $T$ linii, fiecare cu un singur număr $D{~i~}$ reprezentând numărul de beri pe care le va cumpăra prietenul $k{~i~}$ cu suma de bani $x{~i~}$ in condiţiile problemei.
h2. 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ă.
h2. Exemplu
table(example). |_. br.in |_. br.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 5 4
  10 5 15 22 13
  1 32
  4 50
  1 9
  4 200
| 3
  4
  0
  5
|
h3. 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$.
== include(page="template/taskfooter" task_id="br") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3945