2789 - Cb3
De la Universitas MediaWiki
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
# 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")
# 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")