2789 - Cb3

Se consideră un șir de numere naturale nenule a[1], a[2], ..., a[n]. Asupra șirului se efectuează Q interogări de forma: care este numărul maxim de elemente ale șirului a căror sumă nu depășește valoarea S ?

Cerinţa

Trebuie să răspundeți la cele Q interogări.

Date de intrare

Fișierul de intrare cb3in.txt conține pe prima linie numerele n și Q. Pe a doua linie n numere naturale nenule, separate prin spații, ce reprezintă elementele șirului. Pe următoarele Q linii se află sumele aferente celor Q interogări.

Date de ieşire

Fișierul de ieșire cb3out.txt va conține pe câte o linie răspunsurile la cele Q interogări.

Restricții și precizări

• 1 ⩽ n ⩽ 10.000
• 1 ⩽ Q ⩽ 100.000
• 1 ⩽ S ⩽ 2.000.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplul 1

cb3in.txt

5 3
1 2 3 4 5
6
17
5

cb3out.txt

Datele de intrare corespund restrictiilor impuse
3
5
2

Exemplul 2

cb3in.txt

fhfthtfhft

cb3out.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat

def validare(n_validare, q_validare, numere_validare, sume_validare):

   # Verificăm dacă n este în intervalul 1-10000
   if n_validare < 1 or n_validare > 10000:
       raise ValueError  # Ridicăm o eroare dacă n nu este în intervalul 1-10000
   # Verificăm dacă Q este în intervalul 1-100000
   if q_validare < 1 or q_validare > 100000:
       raise ValueError  # Ridicăm o eroare dacă Q nu este în intervalul 1-100000
   for numar in numere_validare:    # Parcurgem lista de numere
       # Verificăm dacă numărul este mai mic decât 1000000
       if numar >= 1000000:
           raise ValueError
   for suma in sume_validare:  # Parcurgem lista de sume
       # Verificăm dacă suma este în intervalul 1-2000000000
       if suma < 1 or suma > 2000000000:
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse\n")

1. Funcția max_elemente calculează numărul maxim de elemente ale șirului a căror sumă nu depășește valoarea S

def max_elemente(numere, sume):

   numere.sort()  # Sortăm numerele în ordine crescătoare
   raspunsuri_elemente = []  # Inițializăm lista de răspunsuri
   for S in sume:  # Pentru fiecare sumă S
       suma = 0
       nr_elemente = 0
       for numar in numere:  # Pentru fiecare număr din șir
           if suma + numar <= S:  # Dacă suma curentă plus numărul curent nu depășește S
               suma += numar  # Adăugăm numărul la sumă
               nr_elemente += 1  # Creștem numărul de elemente
           else:  # Dacă suma curentă plus numărul curent depășește S
               break  # Întrerupem bucla
       raspunsuri_elemente.append(nr_elemente)  # Adăugăm numărul de elemente la lista de răspunsuri
   return raspunsuri_elemente

if __name__ == '__main__':

   file_in = open("cb3in.txt", "r")
   file_out = open("cb3out.txt", "w")

   try:
       # Citim numărul de numere și numărul de interogări
       n_main, Q_main = map(int, file_in.readline().split())
       # Citim numerele
       numere_main = list(map(int, file_in.readline().split()))
       # Citim sumele
       sume_main = [int(file_in.readline()) for _ in range(Q_main)]
       # Validăm datele de intrare
       validare(n_main, Q_main, numere_main, sume_main)
       # Calculăm numărul maxim de elemente ale șirului a căror sumă nu depășește valoarea S pentru fiecare interogare
       raspunsuri = max_elemente(numere_main, sume_main)
       # Scriem răspunsurile în fișierul de ieșire
       for raspuns in raspunsuri:
           file_out.write(str(raspuns) + '\n')

   # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>