Editing 3575 - Br

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

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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse."
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.
În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

==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
:1
:5

;Ieșire
:Datele de intrare corespund restricțiilor impuse.

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


def validate_input(n, t, c_values, rounds):
    if n < 1 or n > 15000:
        raise ValueError("Invalid number of friends")
    if t < 1 or t > 10000:
        raise ValueError("Invalid number of rounds")
    if len(c_values) != n:
        raise ValueError("Invalid number of beer costs")
    if any(ci < 1 or ci > 100 for ci in c_values):
        raise ValueError("Invalid beer cost")
    for k, x in rounds:
        if k < 1 or k > n:
            raise ValueError("Invalid friend index")
        if x < 1 or x > 3000000:
            raise ValueError("Invalid amount of money")


def calculate_round_buying(n, c_values, k, x):
    beers_to_buy = [0] * n
    max_beers_bought = 0
    total_cost = 0

    for i in range(n):
        j = (k + i - 1) % n
        if total_cost + c_values[j] <= x:
            beers_to_buy[j] = 1
            total_cost += c_values[j]
            max_beers_bought += 1
        else:
            break

    if total_cost < x:
        for i in range(n):
            j = (k + i - 1) % n
            if beers_to_buy[j] == 0 and total_cost + c_values[j] <= x:
                beers_to_buy[j] = 1
                total_cost += c_values[j]
                max_beers_bought += 1
                if total_cost == x:
                    break
    return max_beers_bought


if __name__ == "__main__":
    try:
        with open("br.in") as f:
            n, t = map(int, f.readline().split())
            c_values = list(map(int, f.readline().split()))
            rounds = [tuple(map(int, line.split())) for line in f]
        print("Datele introduse corespund restricțiilor impuse.")
        validate_input(n, t, c_values, rounds)

        with open("br.out", "w") as f:
            for k, x in rounds:
                f.write(str(calculate_round_buying(n, c_values, k, x)) + "\n")
    except Exception as e:
        print("Datele introduse nu corespund restricțiilor impuse.")
</syntaxhighlight>

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