Editing 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 '''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ță==

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




==Rezolvare==
===Rezolvare ver. 1===
<syntaxhighlight lang="python" line="1" start="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>