0300 - SumaInSecv: Diferență între versiuni
Fără descriere a modificării |
Fără descriere a modificării |
||
Linia 12: | Linia 12: | ||
Fişierul de ieşire sumainsecv.out va conţine: | Fişierul de ieşire sumainsecv.out va conţine: | ||
Dacă datele sunt introduse corect, pe ecran se va afișa: | Dacă datele sunt introduse corect, pe ecran se va afișa: | ||
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul | '''"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."'''. | ||
Linia 20: | Linia 20: | ||
* dacă vectorul nu conţine nici o secvenţă cu suma elementelor S, se va afişa 0 0 | * 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 | * dacă şirul conţine mai multe secvenţe cu suma elementelor egală cu S, se va determina cea mai din stânga | ||
== Exemplu == | == Exemplu 1 == | ||
; Intrare | ; Intrare | ||
: secv10.in | |||
: 8 32 | : 8 32 | ||
: 12 10 15 7 17 13 19 14 | : 12 10 15 7 17 13 19 14 | ||
; Ieșire | ; Ieșire | ||
: | : secv10.out | ||
: Datele sunt introduse correct | : Datele sunt introduse correct | ||
: 2 4 | : 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 == | ||
=== Rezolvare ver. 1 === | === Rezolvare ver. 1 === |
Versiunea de la data 3 mai 2023 07:33
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
# 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.