0300 - SumaInSecv: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 10: Line 10:


== Date de ieșire ==  
== Date de ieșire ==  
Fişierul de ieşire sumainsecv.out va conţine pe prima linie numerele p şi u, separate printr-un spaţiu, reprezentând indicele de început şi de sfârşit al secvenţei determinate.
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 '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
 


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Line 22: Line 25:
: 12 10 15 7 17 13 19 14
: 12 10 15 7 17 13 19 14
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse./
: Datele sunt introduse correct
: 2 4  
: 2 4  


Line 29: Line 34:
# 0300 - SumaInSecv
# 0300 - SumaInSecv


def citire():
def citire_date():
     with open("sumainsecv.in", "r") as f:
     n, s = map(int, input().split())
        n, s = map(int, f.readline().split())
    v = []
        a = [int(x) for line in f for x in line.split()]
    for i in range(n):
     return n, s, a
        v.extend(map(int, input().split()))
     return n, s, v


def suma_in_secventa(n, s, a):
def suma_in_secventa(n, s, v):
    p = 0
     suma = 0
     suma = 0
    st = 0
    dr = 0
     for i in range(n):
     for i in range(n):
         suma += a[i]
         suma += v[i]
        dr += 1
         while suma > s:
         while suma > s:
             suma -= a[p]
             suma -= v[st]
             p += 1
             st += 1
         if suma == s:
         if suma == s:
             return p+1, i+1
             return st + 1, dr
     return 0, 0
     return 0, 0


def validare(n, s, a, p, u):
def validare(n, s, v):
     if p == 0 and u == 0:
     if len(v) != n:
         return "Nu exista secventa cu suma " + str(s)
         return False
    suma = 0
     for x in v:
     for i in range(p-1, u):
         if x < 1 or x > 9999:
         suma += a[i]
            return False
    if suma != s:
     return True
        return "Suma nu este corecta"
     return "Secventa gasita"


if __name__ == '__main__':
if __name__ == '__main__':
     n, s, a = citire()
     n, s, v = citire_date()
     p, u = suma_in_secventa(n, s, a)
     if validare(n, s, v):
    with open("sumainsecv.out", "w") as f:
        print("Datele sunt introduse corect.")
         f.write(str(p) + " " + str(u) + "\n")
         st, dr = suma_in_secventa(n, s, v)
         f.write(validare(n, s, a, p, u))
        if st == 0 and dr == 0:
            print("0 0")
         else:
            print(st, dr)
    else:
        print("Datele nu corespund restricțiilor impuse.")
 


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Pentru rezolvarea acestei probleme putem folosi o metodă de tip sliding window (fereastră glisantă), în care păstrăm două indici care definesc începutul și sfârșitul secvenței, iar între aceștia vom aduna elementele și le vom compara cu suma dată S. Dacă suma este mai mică decât S, mutăm indicii spre dreapta, adăugând un nou element în fereastră. Dacă suma este mai mare decât S, mutăm indicele de început spre dreapta, eliminând un element din fereastră.
 
 
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.
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 18:36, 27 April 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 numărul c, 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

Intrare
8 32
12 10 15 7 17 13 19 14
Ieșire
Datele nu corespund restricțiilor impuse./
Datele sunt introduse correct
2 4

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0300 - SumaInSecv

def citire_date():

   n, s = map(int, input().split())
   v = []
   for i in range(n):
       v.extend(map(int, input().split()))
   return n, s, v

def suma_in_secventa(n, s, v):

   suma = 0
   st = 0
   dr = 0
   for i in range(n):
       suma += v[i]
       dr += 1
       while suma > s:
           suma -= v[st]
           st += 1
       if suma == s:
           return st + 1, dr
   return 0, 0

def validare(n, s, v):

   if len(v) != n:
       return False
   for x in v:
       if x < 1 or x > 9999:
           return False
   return True

if __name__ == '__main__':

   n, s, v = citire_date()
   if validare(n, s, v):
       print("Datele sunt introduse corect.")
       st, dr = suma_in_secventa(n, s, v)
       if st == 0 and dr == 0:
           print("0 0")
       else:
           print(st, dr)
   else:
       print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>

Explicatie Rezolvare

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. 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.