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

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

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>