0300 - SumaInSecv: Diferență între versiuni
Fără descriere a modificării |
|||
Linia 35: | Linia 35: | ||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | : Datele nu corespund restricțiilor impuse. | ||
== Rezolvare == | == Rezolvare == | ||
=== Rezolvare ver. 1 === | === Rezolvare ver. 1 === | ||
Linia 63: | Linia 62: | ||
if lmax == 0: | if lmax == 0: | ||
return 0, 0 | |||
else: | else: | ||
return lmax, c | |||
def validate_input(n, S, v): | |||
if not (1 <= n <= 100): | |||
return False | |||
if len(v) != n: | |||
return False | |||
for i in range(n): | |||
if not (1 <= v[i] <= 9999): | |||
return False | |||
return True | |||
if __name__ == "__main__": | if __name__ == "__main__": | ||
Linia 77: | Linia 86: | ||
raise ValueError("Datele nu corespund restricțiilor impuse.") | raise ValueError("Datele nu corespund restricțiilor impuse.") | ||
v.append(int(row[0])) | v.append(int(row[0])) | ||
if | if not validate_input(n, S, v): | ||
raise ValueError("Datele nu corespund restricțiilor impuse.") | raise ValueError("Datele nu corespund restricțiilor impuse.") | ||
print("Datele sunt introduse corect.") | print("Datele sunt introduse corect.") | ||
secv_suma(n, S, v) | lmax, c = secv_suma(n, S, v) | ||
with open("secv10.out", "w") as f: | |||
f.write(f"{lmax} {c}") | |||
except Exception as e: | except Exception as e: | ||
print("Datele nu corespund restricțiilor impuse.") | print("Datele nu corespund restricțiilor impuse.") | ||
Linia 89: | Linia 100: | ||
== Explicatie Rezolvare == | == Explicatie Rezolvare == | ||
secv_suma(n, S, v): Aceasta este funcția principală care primește ca parametri numărul de elemente din vector (n), suma dorită (S) și vectorul de elemente (v). Ea folosește o matrice dp pentru a calcula suma de la indicele i la j și o variabilă lmax pentru a păstra lungimea maximă a unei secvențe care are suma S. Dacă există mai multe secvențe cu aceeași lungime maximă, variabila c este folosită pentru a număra aceste secvențe. Rezultatul final este afișat pe ecran. | |||
validare(n, S, v): Aceasta este o funcție ajutătoare care primește aceleași parametri ca și funcția principală și verifică dacă acestea respectă restricțiile date în cerință. Dacă există o problemă, se aruncă o excepție cu un mesaj corespunzător. Dacă nu există probleme, funcția nu returnează nimic. | |||
main(): Aceasta este o funcție ajutătoare care citeste datele din fișierul de intrare și le returnează sub formă de tuplu format din n, S și vectorul v. Dacă există o problemă în citire, se aruncă o excepție cu un mesaj corespunzător. | |||
Versiunea de la data 14 mai 2023 20:40
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
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect."și fișierul 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
- Datele sunt introduse correct
- secv10.out
- 2 4
Exemplu 2
- Intrare
- secv10.in
- 0 32
- Ieșire
- Datele nu corespund restricțiilor impuse.
Rezolvare
Rezolvare ver. 1
# 0300 - SumaInSecv
def secv_suma(n, S, v):
dp = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
dp[i][i] = v[i]
for j in range(i+1, n):
dp[i][j] = dp[i][j-1] + v[j]
lmax = c = 0
for i in range(n):
for j in range(i, n):
if dp[i][j] == S:
l = j-i+1
if l > lmax:
lmax = l
c = 1
elif l == lmax:
c += 1
if lmax == 0:
return 0, 0
else:
return lmax, c
def validate_input(n, S, v):
if not (1 <= n <= 100):
return False
if len(v) != n:
return False
for i in range(n):
if not (1 <= v[i] <= 9999):
return False
return True
if __name__ == "__main__":
try:
with open("sumainsecv.in") as f:
n, S = map(int, f.readline().split())
v = []
for i in range(n):
row = f.readline().split()
if len(row) != 1:
raise ValueError("Datele nu corespund restricțiilor impuse.")
v.append(int(row[0]))
if not validate_input(n, S, v):
raise ValueError("Datele nu corespund restricțiilor impuse.")
print("Datele sunt introduse corect.")
lmax, c = secv_suma(n, S, v)
with open("secv10.out", "w") as f:
f.write(f"{lmax} {c}")
except Exception as e:
print("Datele nu corespund restricțiilor impuse.")
print(e)
Explicatie Rezolvare
secv_suma(n, S, v): Aceasta este funcția principală care primește ca parametri numărul de elemente din vector (n), suma dorită (S) și vectorul de elemente (v). Ea folosește o matrice dp pentru a calcula suma de la indicele i la j și o variabilă lmax pentru a păstra lungimea maximă a unei secvențe care are suma S. Dacă există mai multe secvențe cu aceeași lungime maximă, variabila c este folosită pentru a număra aceste secvențe. Rezultatul final este afișat pe ecran. validare(n, S, v): Aceasta este o funcție ajutătoare care primește aceleași parametri ca și funcția principală și verifică dacă acestea respectă restricțiile date în cerință. Dacă există o problemă, se aruncă o excepție cu un mesaj corespunzător. Dacă nu există probleme, funcția nu returnează nimic. main(): Aceasta este o funcție ajutătoare care citeste datele din fișierul de intrare și le returnează sub formă de tuplu format din n, S și vectorul v. Dacă există o problemă în citire, se aruncă o excepție cu un mesaj corespunzător.