Editing 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 &les; n &les; 10.000
* 1 &les; Q &les; 100.000
* 1 &les; S &les; 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
<br>
== Exemplul 2 ==
; cb3in.txt
 fhfthtfhft
; cb3out.txt
 Datele de intrare nu corespund restrictiilor impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
# 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")

</syntaxhighlight>