4233 - SecvDeSumaS - Revision history

Flaviu at 21:33, 14 May 2023

2023-05-14T21:33:47Z

@@ Line 38: / Line 38: @@
 # 4233 - SecvDeSumaS
-def read_input():
+def validate_input(n, S, arr):
      if not (1 <= n <= 1000000):
          return False
-     if not (-1000 <= s <= 1000):
+     if len(arr) != n:
          return False
-     if not (-1000 <= min(a) and max(a) <= 1000):
+     if not (-1000000000 <= S <= 1000000000):
          return False
      return True
 if __name__ == '__main__':
-     n, s, a = read_input()
+     n, S = map(int, input("Introduceti n si S: ").split())
-    if validate_input(n, s, a):
+    arr = list(map(int, input("Introduceti vectorul de numere întregi: ").split()))
 </syntaxhighlight>
 == Explicatie Rezolvare ==
-Funcția read_input citește datele de intrare de la tastatură și le returnează într-o tuplă.
+Funcția validate_input(n, S, arr) este responsabilă pentru validarea datelor de intrare. Aceasta verifică dacă valorile îndeplinesc restricțiile impuse în cerință. Verifică următoarele condiții:
-Funcția count_subarrays primește numărul n, suma s și vectorul a și returnează numărul de subșiruri (secvențe) cu suma egală cu s. Aceasta utilizează o metodă eficientă de calculare a numărului de subșiruri cu o anumită sumă, care se bazează pe utilizarea unui dicționar sum_count care stochează numărul de subșiruri cu suma curentă. Inițial, acest dicționar conține o singură valoare, anume 0, cu numărul de apariții 1, pentru că înainte de a începe să adunăm elementele din vector, suma este 0. Pe măsură ce iterăm prin elementele vectorului, actualizăm suma curentă și verificăm dacă diferența dintre suma curentă și s a mai apărut în vectorul a. Dacă da, atunci adăugăm numărul de subșiruri care au suma egală cu diferența respectivă. În plus, adăugăm și numărul de apariții curent al sumei în dicționarul sum_count. Dacă suma curentă a mai fost întâlnită, atunci incrementăm numărul de apariții al acesteia în dicționar, altfel adăugăm o intrare nouă cu numărul de apariții 1.
-Funcția validate_input validează datele de intrare conform restricțiilor din enunț.
+n trebuie să fie între 1 și 1.000.000
-În blocul if __name__ == '__main__': se apelează funcțiile în ordinea necesară și se afișează rezultatul.
+lungimea listei arr trebuie să fie n

Flaviu at 08:02, 3 May 2023

2023-05-03T08:02:21Z

← Older revision		Revision as of 08:02, 3 May 2023
Line 11:		Line 11:
	== Date de ieșire ==		== Date de ieșire ==
	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 c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul numărul secvențelor nevide care au suma egală cu S'', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
Line 18:		Line 18:
	* -1.000.000.000 ≤ S ≤ 1.000.000.000		* -1.000.000.000 ≤ S ≤ 1.000.000.000
	O secvență nevidă este formată din unul sau mai multe elemente ale șirului aflate pe poziții consecutive.nță cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător		O secvență nevidă este formată din unul sau mai multe elemente ale șirului aflate pe poziții consecutive.nță cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: 13 -10		: 13 -10
	: 2 3 -11 1 -11 4 -8 10 -14 10 -5 4 -17		: 2 3 -11 1 -11 4 -8 10 -14 10 -5 4 -17
	; Ieșire		; Ieșire
	~~: Datele nu corespund restricțiilor impuse.~~
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 4		: 4

			== Exemplu ==
			; Intrare
			: 22 3 5 9 2
			: 1 2 3 5 0 0 -1 0 2 -76 23
			; Ieșire
			: Datele nu corespund restricțiilor impuse.

	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:47, 28 April 2023

2023-04-28T14:47:17Z

← Older revision		Revision as of 14:47, 28 April 2023
Line 10:		Line 10:

	== Date de ieșire ==		== Date de ieșire ==
	~~Programul~~ va afișa pe ecran ~~numărul numărul secvențelor nevide care au suma egală cu S~~.		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 ==		== Restricţii şi precizări ==
Line 22:		Line 23:
	: 2 3 -11 1 -11 4 -8 10 -14 10 -5 4 -17		: 2 3 -11 1 -11 4 -8 10 -14 10 -5 4 -17
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 4		: 4

Line 49:		Line 52:

	def validate_input(n, s, a):		def validate_input(n, s, a):
	~~assert~~ 1 <= n <= 1000000		if not (1 <= n <= 1000000):
	~~assert~~ -1000 <= s <= 1000		return False
	~~assert~~ -1000 <= min(a) and max(a) <= 1000		if not (-1000 <= s <= 1000):
			return False
			if not (-1000 <= min(a) and max(a) <= 1000):
			return False
			return True

	if __name__ == '__main__':		if __name__ == '__main__':
	n, s, a = read_input()		n, s, a = read_input()
	validate_input(n, s, a)		if validate_input(n, s, a):
	print(count_subarrays(n, s, a))		print("Datele sunt introduse corect.")
			print(count_subarrays(n, s, a))
			else:
			print("Datele nu corespund restricțiilor impuse.")

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/4233/secvdesumas 4233 - SecvDeSumaS] ---- == Cerinţa == Se dă un șir a1, a2, …, an de numere întregi și un număr întreg S. Să se determine numărul secvențelor nevide care au suma egală cu S. == Date de intrare == Programul citește de la tastatură de pe prima linie numerele n, S, iar de pe a doua linie numerele separate prin spații a1, a2, …, an. == Date de ieșire == Programul va afișa pe ecran numărul numărul s...

2023-04-18T06:57:05Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/4233/secvdesumas 4233 - SecvDeSumaS] ---- == Cerinţa == Se dă un șir a1, a2, …, an de numere întregi și un număr întreg S. Să se determine numărul secvențelor nevide care au suma egală cu S. == Date de intrare == Programul citește de la tastatură de pe prima linie numerele n, S, iar de pe a doua linie numerele separate prin spații a1, a2, …, an. == Date de ieșire == Programul va afișa pe ecran numărul numărul s...

New page

Sursa: [https://www.pbinfo.ro/probleme/4233/secvdesumas 4233 - SecvDeSumaS]
----
== Cerinţa ==
Se dă un șir a1, a2, …, an de numere întregi și un număr întreg S. Să se determine numărul secvențelor nevide care au suma egală cu S.

== Date de intrare ==
Programul citește de la tastatură de pe prima linie numerele n, S, iar de pe a doua linie numerele separate prin spații a1, a2, …, an.

== Date de ieșire ==
Programul va afișa pe ecran numărul numărul secvențelor nevide care au suma egală cu S.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1.000.000
* -1000 ≤ ai ≤ 1000 pentru orice i=1..n
* -1.000.000.000 ≤ S ≤ 1.000.000.000
O secvență nevidă este formată din unul sau mai multe elemente ale șirului aflate pe poziții consecutive.nță cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător
== Exemplu ==
; Intrare
: 13 -10
: 2 3 -11 1 -11 4 -8 10 -14 10 -5 4 -17
; Ieșire
: 4

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 4233 - SecvDeSumaS

def read_input():
n, s = map(int, input().split())
a = list(map(int, input().split()))
return n, s, a

def count_subarrays(n, s, a):
sum_count = {0: 1}
current_sum = 0
subarrays = 0
for i in range(n):
current_sum += a[i]
if current_sum - s in sum_count:
subarrays += sum_count[current_sum - s]
if current_sum in sum_count:
sum_count[current_sum] += 1
else:
sum_count[current_sum] = 1
return subarrays

def validate_input(n, s, a):
assert 1 <= n <= 1000000
assert -1000 <= s <= 1000
assert -1000 <= min(a) and max(a) <= 1000

if __name__ == '__main__':
n, s, a = read_input()
validate_input(n, s, a)
print(count_subarrays(n, s, a))

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare de la tastatură și le returnează într-o tuplă.
Funcția count_subarrays primește numărul n, suma s și vectorul a și returnează numărul de subșiruri (secvențe) cu suma egală cu s. Aceasta utilizează o metodă eficientă de calculare a numărului de subșiruri cu o anumită sumă, care se bazează pe utilizarea unui dicționar sum_count care stochează numărul de subșiruri cu suma curentă. Inițial, acest dicționar conține o singură valoare, anume 0, cu numărul de apariții 1, pentru că înainte de a începe să adunăm elementele din vector, suma este 0. Pe măsură ce iterăm prin elementele vectorului, actualizăm suma curentă și verificăm dacă diferența dintre suma curentă și s a mai apărut în vectorul a. Dacă da, atunci adăugăm numărul de subșiruri care au suma egală cu diferența respectivă. În plus, adăugăm și numărul de apariții curent al sumei în dicționarul sum_count. Dacă suma curentă a mai fost întâlnită, atunci incrementăm numărul de apariții al acesteia în dicționar, altfel adăugăm o intrare nouă cu numărul de apariții 1.
Funcția validate_input validează datele de intrare conform restricțiilor din enunț.
În blocul if __name__ == '__main__': se apelează funcțiile în ordinea necesară și se afișează rezultatul.