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 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
# 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.")
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.