0300 - SumaInSecv: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Line 35: Line 35:
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: secv10.out
 
: Datele nu sunt introduse correct
== Rezolvare ==  
== Rezolvare ==  
=== Rezolvare ver. 1 ===
=== Rezolvare ver. 1 ===
Line 63: Line 62:


     if lmax == 0:
     if lmax == 0:
         print("0 0")
         return 0, 0
     else:
     else:
         print(lmax, c)
         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__":
if __name__ == "__main__":
Line 77: Line 86:
                     raise ValueError("Datele nu corespund restricțiilor impuse.")
                     raise ValueError("Datele nu corespund restricțiilor impuse.")
                 v.append(int(row[0]))
                 v.append(int(row[0]))
             if i+1 != n:
             if not validate_input(n, S, v):
                 raise ValueError("Datele nu corespund restricțiilor impuse.")
                 raise ValueError("Datele nu corespund restricțiilor impuse.")
         print("Datele sunt introduse corect.")
         print("Datele sunt introduse corect.")
         secv_suma(n, S, v)
         lmax, c = secv_suma(n, S, v)
        with open("secv10.out", "w") as f:
            f.write(f"{lmax} {c}")
     except Exception as e:
     except Exception as e:
         print("Datele nu corespund restricțiilor impuse.")
         print("Datele nu corespund restricțiilor impuse.")
Line 89: Line 100:
== Explicatie Rezolvare ==
== 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.
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.
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.
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.
 
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.

Revision as of 20:40, 14 May 2023

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

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>

  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.