Vizualizare sursă pentru „0300 - SumaInSecv”

Sursa: [https://www.pbinfo.ro/probleme/4148/secv10 0300 - SumaInSecv]
----
== Cerinţa ==
Se dă un vector format din n elemente, numere naturale nenule, şi un număr natural S. Determinaţi, dacă există o secvenţă de elemente din şir cu suma elementelor egală cu S.


== Date de intrare ==
Fişierul de intrare sumainsecv.in conţine pe prima linie numerele n şi S; urmează cele n elemente ale vectorului, dispuse pe mai multe linii şi separate prin spaţii.


== Date de ieșire == 

Dacă datele sunt introduse corect, pe ecran se va afișa: 
'''"Datele sunt introduse corect."''și fișierul secv10.out va conține pe prima linie numerele lmax și c, reprezentând lungimea maximă a unei secvențe de elemente divizibile cu 10, respectiv numărul de secvențe de lungime maximă cu elemente divizibile cu 10''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100
* elementele vectorului vor avea cel mult 4 cifre şi sunt numerotate de la 1 la n
* dacă vectorul nu conţine nici o secvenţă cu suma elementelor S, se va afişa 0 0
* dacă şirul conţine mai multe secvenţe cu suma elementelor egală cu S, se va determina cea mai din stânga
== Exemplu 1 ==
; Intrare
: secv10.in
: 8 32  
: 12 10 15 7 17 13 19 14
; Ieșire
: Datele sunt introduse correct
: secv10.out
: 2 4 
== Exemplu 2 ==
; Intrare
: secv10.in
: 0 32 
: 
; Ieșire
: Datele nu corespund restricțiilor impuse.

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0300 - SumaInSecv

def secv_suma(n, S, v):
    dp = [[0 for j in range(n)] for i in range(n)]

    for i in range(n):
        dp[i][i] = v[i]
        for j in range(i+1, n):
            dp[i][j] = dp[i][j-1] + v[j]

    lmax = c = 0

    for i in range(n):
        for j in range(i, n):
            if dp[i][j] == S:
                l = j-i+1
                if l > lmax:
                    lmax = l
                    c = 1
                elif l == lmax:
                    c += 1

    if lmax == 0:
        return 0, 0
    else:
        return lmax, c

def validate_input(n, S, v):
    if not (1 <= n <= 100):
        return False
    if len(v) != n:
        return False
    for i in range(n):
        if not (1 <= v[i] <= 9999):
            return False
    return True

if __name__ == "__main__":
    try:
        with open("sumainsecv.in") as f:
            n, S = map(int, f.readline().split())
            v = []
            for i in range(n):
                row = f.readline().split()
                if len(row) != 1:
                    raise ValueError("Datele nu corespund restricțiilor impuse.")
                v.append(int(row[0]))
            if not validate_input(n, S, v):
                raise ValueError("Datele nu corespund restricțiilor impuse.")
        print("Datele sunt introduse corect.")
        lmax, c = secv_suma(n, S, v)
        with open("secv10.out", "w") as f:
            f.write(f"{lmax} {c}")
    except Exception as e:
        print("Datele nu corespund restricțiilor impuse.")
        print(e)


</syntaxhighlight>
== Explicatie Rezolvare ==

`secv_suma(n, S, v)`: Această funcție primește trei argumente: `n` - lungimea listei `v`, `S` - suma căutată și `v` - lista de numere întregi. Scopul funcției este să găsească cea mai lungă subsecvență continuă a listei `v` a cărei sumă este egală cu `S`. Funcția utilizează o abordare dinamică pentru a calcula matricea `dp` care stochează sumele parțiale ale subsecvențelor. Apoi, se verifică fiecare subsecvență pentru a determina cea mai lungă subsecvență cu suma `S`. Funcția returnează un tuplu `(lmax, c)` unde `lmax` este lungimea celei mai lungi subsecvențe și `c` este numărul de subsecvențe cu aceeași lungime maximă.

 `validate_input(n, S, v)`: Această funcție primește trei argumente: `n` - lungimea listei `v`, `S` - suma căutată și `v` - lista de numere întregi. Scopul funcției este să valideze datele de intrare conform restricțiilor impuse. Verifică dacă lungimea listei `v` este `n`, dacă `n` se încadrează în intervalul permis și dacă fiecare element din `v` se încadrează în intervalul permis. Returnează `True` dacă datele sunt valide și `False` în caz contrar.

Funcția principală `if __name__ == "__main__"` citeste datele de intrare din fișierul "sumainsecv.in", validează datele folosind funcția `validate_input()`, apoi apelează funcția `secv_suma()` pentru a obține rezultatul dorit. Rezultatul este scris în fișierul "secv10.out". Dacă apar erori în citirea sau validarea datelor, se afișează un mesaj corespunzător pe ecran.