0300 - SumaInSecv

Sursa: 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

Fişierul de ieşire sumainsecv.out va conţine: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou 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.

secv10.out

Datele nu sunt introduse correct

Rezolvare

Rezolvare ver. 1

# 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:
        print("0 0")
    else:
        print(lmax, c)

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 i+1 != n:
                raise ValueError("Datele nu corespund restricțiilor impuse.")
        print("Datele sunt introduse corect.")
        secv_suma(n, S, v)
    except Exception as e:
        print("Datele nu corespund restricțiilor impuse.")
        print(e)

Explicatie Rezolvare

Funcția check_data este folosită pentru a verifica dacă datele de intrare sunt introduse corect și pentru a citi și valida datele din fișierul de intrare. Ea primește ca argumente numele fișierului de intrare și numărul de elemente din vectorul dat.

Funcția find_seq primește ca argumente vectorul dat și suma S și are ca scop găsirea celei mai lungi secvențe de elemente divizibile cu 10 a cărei sumă este S, dar și numărul de astfel de secvențe. Ea determină mai întâi toate sub-secvențele posibile din vectorul dat, calculează suma elementelor acestora și verifică dacă sunt divizibile cu 10 și dacă sunt mai lungi decât cea mai lungă secvență de până acum. Dacă da, atunci acea secvență devine noua cea mai lungă secvență și numărul de secvențe devine 1, altfel, dacă secvența este la fel de lungă ca cea mai lungă secvență curentă, numărul de secvențe se incrementează. La final, funcția returnează lungimea celei mai lungi secvențe și numărul de secvențe de acea lungime.

Funcția main este utilizată pentru a apela cele două funcții și pentru a afișa rezultatul găsit în fișierul de ieșire. Ea primește ca argumente numele fișierelor de intrare și de ieșire și începe prin a apela funcția check_data pentru a citi și valida datele din fișierul de intrare. Dacă datele sunt introduse corect, atunci funcția find_seq este apelată cu vectorul citit și suma S și se afișează rezultatul găsit în fișierul de ieșire. Dacă datele nu sunt introduse corect, se afișează mesajul "Datele nu corespund restricțiilor impuse." în loc de a apela funcția find_seq.