0300 - SumaInSecv: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 26: Line 26:
: 12 10 15 7 17 13 19 14
: 12 10 15 7 17 13 19 14
; Ieșire
; Ieșire
: Datele sunt introduse correct
: secv10.out
: secv10.out
: Datele sunt introduse correct
: 2 4  
: 2 4  
== Exemplu 2 ==
== Exemplu 2 ==
; Intrare
; Intrare
: secv10.in
: secv10.in
: 8 32
: 0 32  
: 12 10 15 7 17 13 19 14
:  
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: secv10.out
: secv10.out
: Datele nu corespund restricțiilor impuse.
: Datele nu sunt introduse correct
: 5 1
== Rezolvare ==  
== Rezolvare ==  
=== Rezolvare ver. 1 ===
=== Rezolvare ver. 1 ===
Line 43: Line 43:
# 0300 - SumaInSecv
# 0300 - SumaInSecv


def citire_date():
def secv_suma(n, S, v):
     n, s = map(int, input().split())
     dp = [[0 for j in range(n)] for i in range(n)]
    v = []
 
     for i in range(n):
     for i in range(n):
         v.extend(map(int, input().split()))
         dp[i][i] = v[i]
     return n, s, v
        for j in range(i+1, n):
            dp[i][j] = dp[i][j-1] + v[j]
 
     lmax = c = 0


def suma_in_secventa(n, s, v):
    suma = 0
    st = 0
    dr = 0
     for i in range(n):
     for i in range(n):
         suma += v[i]
         for j in range(i, n):
        dr += 1
            if dp[i][j] == S:
        while suma > s:
                l = j-i+1
            suma -= v[st]
                if l > lmax:
            st += 1
                    lmax = l
        if suma == s:
                    c = 1
            return st + 1, dr
                elif l == lmax:
    return 0, 0
                    c += 1


def validare(n, s, v):
     if lmax == 0:
     if len(v) != n:
         print("0 0")
         return False
     else:
     for x in v:
         print(lmax, c)
         if x < 1 or x > 9999:
            return False
    return True


if __name__ == '__main__':
if __name__ == "__main__":
     n, s, v = citire_date()
     try:
    if validare(n, s, v):
        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.")
         print("Datele sunt introduse corect.")
         st, dr = suma_in_secventa(n, s, v)
         secv_suma(n, S, v)
        if st == 0 and dr == 0:
     except Exception as e:
            print("0 0")
        else:
            print(st, dr)
     else:
         print("Datele nu corespund restricțiilor impuse.")
         print("Datele nu corespund restricțiilor impuse.")
        print(e)




Line 88: Line 90:
== 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.
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.


citire_date() primeste de la input n si s, urmate de n numerele ale vectorului v. Folosind extend, toate numerele vectorului sunt citite intr-o singura lista.
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.
suma_in_secventa() cauta o secventa a vectorului v cu suma elementelor egala cu s, folosind un algoritm de tip sliding window, care tine minte in st si dr indecsii de start si sfarsit ai secventei. Daca gaseste o astfel de secventa, returneaza indecsii acesteia. Daca nu exista o astfel de secventa, returneaza 0 0.
validare() verifica daca datele de intrare sunt corecte, adica vectorul sa aiba n elemente si toate elementele sa fie intre 1 si 9999.
In functia principala, mai intai se verifica daca datele de intrare sunt corecte folosind validare(). Daca da, se afiseaza un mesaj de confirmare si se apeleaza suma_in_secventa() pentru a determina indecsii secventei cu suma egala cu s. Daca nu exista o astfel de secventa, se afiseaza "0 0". Daca exista, se afiseaza indecsii acesteia. Daca datele de intrare nu sunt corecte, se afiseaza un mesaj corespunzator.

Revision as of 22:05, 13 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

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

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


</syntaxhighlight>

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.