0300 - SumaInSecv

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

secv10.out

Datele sunt introduse correct

2 4

Exemplu 2

Intrare

secv10.in

8 32

12 10 15 7 17 13 19 14

Ieșire

secv10.out

Datele nu corespund restricțiilor impuse.

5 1

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.