3575 - Br: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: ==Enunt== '''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ă, începand 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 posib...
 
Line 1: Line 1:
==Enunt==
==Enunț==


'''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ă, începand 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.
'''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ă, începand 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ță==
==Cerință==

Revision as of 12:13, 27 March 2023

Enunț

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 Cicostul 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ă, începand 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:

k1x1
k2x2
kTxT

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 de precizări

  • 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

Exemplul 1

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

Explicatie

Prietenul 1 cumpără câte o bere pentru el şi pentru prietenii 2, 3. Costul celor 3 beri este 30. Prietenul 4cumpă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.



Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1">

  1. functie care calculeaza numarul maxim de beri ce pot fi cumparate cu o anumita suma

def numar_maxim_beri(costuri, x, k):

   n = len(costuri)
   # daca x este mai mare decat costul tuturor berilor, se vor cumpara maxim N beri
   if x >= sum(costuri):
       return n
   # initializare variabile
   i = k
   j = (k + 1) % n
   cost_total = costuri[k]
   numar_beri = 1
   numar_maxim = 1
   # algoritmul lui Kadane pentru secvente maxime de suma
   while i != j:
       # daca se depaseste suma x, se decrementeaza variabilele pana la atingerea sumei x
       while cost_total + costuri[j] > x and i != j:
           cost_total -= costuri[i]
           numar_beri -= 1
           i = (i + 1) % n
       # se adauga costul berii si se incrementeaza numarul de beri
       cost_total += costuri[j]
       numar_beri += 1
       j = (j + 1) % n
       # se actualizeaza numarul maxim de beri si se pastreaza secventa maxima
       if numar_beri > numar_maxim:
           numar_maxim = numar_beri
   return numar_maxim

if __name__ == '__main__':

   # citire date de intrare
   with open('br.in', 'r') as f:
       n, t = map(int, f.readline().split())
       costuri = list(map(int, f.readline().split()))
       for _ in range(t):
           k, x = map(int, f.readline().split())
           # apelare functie si afisare rezultat
           print(numar_maxim_beri(costuri, x, k-1))

</syntaxhighlight>