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

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

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 1cumpă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.