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

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: 2 4

Rezolvare

Rezolvare ver. 1

0300 - SumaInSecv

def citire():

   with open("sumainsecv.in", "r") as f:
       n, s = map(int, f.readline().split())
       a = [int(x) for line in f for x in line.split()]
   return n, s, a

def suma_in_secventa(n, s, a):

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

def validare(n, s, a, p, u):

   if p == 0 and u == 0:
       return "Nu exista secventa cu suma " + str(s)
   suma = 0
   for i in range(p-1, u):
       suma += a[i]
   if suma != s:
       return "Suma nu este corecta"
   return "Secventa gasita"

if __name__ == '__main__':

   n, s, a = citire()
   p, u = suma_in_secventa(n, s, a)
   with open("sumainsecv.out", "w") as f:
       f.write(str(p) + " " + str(u) + "\n")
       f.write(validare(n, s, a, p, u))

</syntaxhighlight>

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