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

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): Aceasta este funcția principală care primește ca parametri numărul de elemente din vector (n), suma dorită (S) și vectorul de elemente (v). Ea folosește o matrice dp pentru a calcula suma de la indicele i la j și o variabilă lmax pentru a păstra lungimea maximă a unei secvențe care are suma S. Dacă există mai multe secvențe cu aceeași lungime maximă, variabila c este folosită pentru a număra aceste secvențe. Rezultatul final este afișat pe ecran. validare(n, S, v): Aceasta este o funcție ajutătoare care primește aceleași parametri ca și funcția principală și verifică dacă acestea respectă restricțiile date în cerință. Dacă există o problemă, se aruncă o excepție cu un mesaj corespunzător. Dacă nu există probleme, funcția nu returnează nimic. main(): Aceasta este o funcție ajutătoare care citeste datele din fișierul de intrare și le returnează sub formă de tuplu format din n, S și vectorul v. Dacă există o problemă în citire, se aruncă o excepție cu un mesaj corespunzător.