3575 - Br

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 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>