2142 - easy sum - Revision history

Monica Dragos: /* Date de ieșire */

2023-05-14T22:27:14Z

Date de ieșire

← Older revision		Revision as of 22:27, 14 May 2023
Line 12:		Line 12:
	Fișierul de ieșire easy_sum.out va conține:		Fișierul de ieșire easy_sum.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 S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''' fișierul de ieșire easy_sum.out va conține numărul S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007''', 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 ==

Flaviu at 21:25, 14 May 2023

2023-05-14T21:25:30Z

← Older revision		Revision as of 21:25, 14 May 2023
Line 24:		Line 24:
	: 1 2 3		: 1 2 3
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: easy_sum.out		: easy_sum.out
	~~: Datele nu corespund restricțiilor impuse.~~
	~~: Datele sunt introduse correct.~~
	: 20		: 20
	== Exemplu 1 ==
			== Exemplu 2 ==
	; Intrare		; Intrare
	: easy_sum.in		: easy_sum.in
Line 34:		Line 34:
	: 1 2 3 4 2 7 -8		: 1 2 3 4 2 7 -8
	; Ieșire		; Ieșire
	~~: easy_sum.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 45:		Line 44:
	MOD = 1000000007		MOD = 1000000007

	def ~~read_input~~():		def validate_input(n, arr):
	n = ~~int~~(~~input~~())		if not (1 <= n <= 100000):
	~~nums = list~~(~~map(int~~, ~~input(~~)~~.split~~()))		return False
	return ~~n, nums~~		if len(arr) != n:
			return False
			if any(num < 1 or num > 1000000 for num in arr):
			return False
			return True


			def calculate_subsequence_sum(n, arr):
			if not validate_input(n, arr):
			return "Datele nu corespund restricțiilor impuse."

	~~def solve(n, nums):~~		MOD = 1000000007
	~~total_sum~~ = ~~sum(nums)~~		total_sum = 0
	~~partial_sums~~ = [0]
	~~for num in nums:~~
	~~partial_sums.append((partial_sums[-1] + num) % MOD)~~

	~~subseq_sum = 0~~
	for i in range(n):		for i in range(n):
	~~left_sum~~ = ~~partial_sums[i~~+1]		total_sum = (total_sum + (arr[i] * (i + 1) * (n - i)) % MOD) % MOD
	~~right_sum =~~ (~~total_sum - partial_sums~~[i+1] ~~+ MOD) % MOD~~
			return total_sum
	~~subseq_sum +=~~ (i+1) * ~~left_sum~~
	~~subseq_sum %= MOD~~

	~~subseq_sum +=~~ (n-i) * right_sum
	~~subseq_sum~~ %= MOD

	~~subseq_sum += left_sum * right_sum~~
	~~subseq_sum~~ %= MOD

	return ~~subseq_sum~~

	~~def validate_output(expected_output, output):~~		if __name__ == "__main__":
	if ~~int(expected_output)~~ == ~~int(output)~~:		file_name = "easy_sum.in"
	~~print(~~"~~Datele sunt introduse corect~~.")		with open(file_name, "r") as file:
	~~else~~:		n = int(file.readline())
	~~print~~(~~"Datele nu corespund restricțiilor impuse~~.")		arr = list(map(int, file.readline().split()))
	~~print~~(~~output~~)

	~~if __name__ == '__main__':~~		result = calculate_subsequence_sum(n, arr)
	~~n, nums = read_input()~~
	result = ~~solve~~(n, ~~nums~~)
	print(result)		print(result)
	~~validate_output(input(), result)~~


	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția ~~read_input citește~~ datele de intrare ~~din stdin și le~~ returnează ~~ca o tuplă~~ (n, ~~nums~~).		Funcția validate_input(n, arr):
	~~Funcția solve~~ primește n și ~~nums și calculează~~ suma ~~tuturor~~ subsecvențelor ~~ca descris~~ în ~~comentarii~~. ~~În loc să calculeze~~ suma ~~tuturor~~ subsecvențelor ~~direct, calculează sume parțiale și le combină ulterior~~.
	~~Funcția validate_output primește ieșirea așteptată și ieșirea obținută și~~ returnează ~~True dacă acestea sunt egale (ignorând spațiile suplimentare)~~.		Această funcție primește doi parametri: n - numărul de elemente din vector și arr - lista de numere.
	În if __name__ == '__main__', se ~~citesc datele~~ de intrare~~, se rezolvă~~		Verifică dacă valoarea n se încadrează în intervalul specificat în cerință și dacă lungimea listei arr este egală cu n.
			Verifică, de asemenea, dacă există vreun număr din lista arr care este mai mic decât 1 sau mai mare decât 1000000. Dacă da, se returnează False, semnalând că datele nu corespund restricțiilor impuse.
			Dacă toate verificările sunt trecute cu succes, înseamnă că datele de intrare sunt valide, astfel că se returnează True.
			Funcția calculate_subsequence_sum(n, arr):

			Această funcție primește doi parametri: n - numărul de elemente din vector și arr - lista de numere.
			Verifică mai întâi validitatea datelor de intrare folosind funcția validate_input(n, arr). Dacă datele nu sunt valide, returnează un mesaj corespunzător.
			Inițializează variabila total_sum cu valoarea 0, care va fi utilizată pentru a calcula suma subsecvențelor.
			Parcurge lista arr și pentru fiecare element, adaugă la total_sum valoarea elementului înmulțită cu (i + 1) * (n - i). Aceasta reprezintă numărul de subsecvențe în care elementul curent apare.
			Se aplică modularitatea cu MOD pentru a menține suma subsecvențelor într-un interval valid.
			La final, se returnează total_sum calculat modulo MOD.
			În funcția if __name__ == "__main__", se realizează citirea datelor de intrare din fișierul

Flaviu at 07:59, 3 May 2023

2023-05-03T07:59:13Z

← Older revision		Revision as of 07:59, 3 May 2023
Line 12:		Line 12:
	Fișierul de ieșire easy_sum.out va conține:		Fișierul de ieșire easy_sum.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 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 S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007''', 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:
	* numerele de pe a doua linie a fișierului de intrare vor fi cuprinse în intervalul [1,1.000.000]		* numerele de pe a doua linie a fișierului de intrare vor fi cuprinse în intervalul [1,1.000.000]
	* prin subsecvență înțelegem orice înșiruire de elemente din vector aflate pe poziții consecutive.		* prin subsecvență înțelegem orice înșiruire de elemente din vector aflate pe poziții consecutive.
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: easy_sum.in
	: 3		: 3
	: 1 2 3		: 1 2 3
	; Ieșire		; Ieșire
			: easy_sum.out
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 20		: 20
			== Exemplu 1 ==
			; Intrare
			: easy_sum.in
			: 21
			: 1 2 3 4 2 7 -8
			; Ieșire
			: easy_sum.out
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:43, 28 April 2023

2023-04-28T14:43:37Z

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

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire easy_sum.out va conține pe ~~prima linie~~ numărul S, reprezentând ~~suma sumelor tuturor subsecvențelor modulo 1~~.~~000.000~~.~~007~~.		Fișierul de ieșire easy_sum.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 ==		== Restricţii şi precizări ==
Line 21:		Line 23:
	: 1 2 3		: 1 2 3
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 20		: 20

Line 36:		Line 40:

	def solve(n, nums):		def solve(n, nums):
	~~# suma tuturor subsecventelor va fi data de:~~
	~~# suma(sum[i:j]) pentru i in [0, n) si j in [i+1, n+1)~~
	~~# putem rescrie asta ca:~~
	~~# suma(sum[i:n]) + suma(sum[0:j]) - suma(sum[0:i]) pentru i in [0, n) si j in [i+1, n+1)~~
	~~# (primul termen este suma tuturor subsecventelor care incep cu i,~~
	~~# al doilea termen este suma tuturor subsecventelor care se termina cu j-1,~~
	~~# iar al treilea termen este suma tuturor subsecventelor care incep inainte de i)~~
	~~# putem calcula aceste sume partial pentru a reduce timpul de executie~~

	~~# calculam suma tuturor numerelor din nums si suma partiala a numerelor din nums~~
	total_sum = sum(nums)		total_sum = sum(nums)
	partial_sums = [0]		partial_sums = [0]
Line 51:		Line 45:
	partial_sums.append((partial_sums[-1] + num) % MOD)		partial_sums.append((partial_sums[-1] + num) % MOD)

	~~# calculam suma tuturor subsecventelor~~
	subseq_sum = 0		subseq_sum = 0
	for i in range(n):		for i in range(n):
	~~# calculam sum[0:i] si sum[i:n]~~
	left_sum = partial_sums[i+1]		left_sum = partial_sums[i+1]
	right_sum = (total_sum - partial_sums[i+1] + MOD) % MOD		right_sum = (total_sum - partial_sums[i+1] + MOD) % MOD

	~~# adaugam la suma totala suma tuturor subsecventelor care incep cu i~~
	subseq_sum += (i+1) * left_sum		subseq_sum += (i+1) * left_sum
	subseq_sum %= MOD		subseq_sum %= MOD

	~~# adaugam la suma totala suma tuturor subsecventelor care se termina cu j-1~~
	subseq_sum += (n-i) * right_sum		subseq_sum += (n-i) * right_sum
	subseq_sum %= MOD		subseq_sum %= MOD

	~~# adaugam la suma totala suma tuturor subsecventelor care incep inainte de i~~
	subseq_sum += left_sum * right_sum		subseq_sum += left_sum * right_sum
	subseq_sum %= MOD		subseq_sum %= MOD
Line 73:		Line 62:

	def validate_output(expected_output, output):		def validate_output(expected_output, output):
	~~return~~ int(expected_output) == int(output)		if int(expected_output) == int(output):
			print("Datele sunt introduse corect.")
			else:
			print("Datele nu corespund restricțiilor impuse.")
			print(output)

	if __name__ == '__main__':		if __name__ == '__main__':
Line 79:		Line 72:
	result = solve(n, nums)		result = solve(n, nums)
	print(result)		print(result)
			validate_output(input(), result)

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2142/easy-sum 2142 - easy sum] ---- == Cerinţa == Se consideră un vector cu n elemente numere naturale. Calculați suma sumelor tuturor subsecvențelor ce se pot forma cu elementele vectorului. Pentru că suma poate fi foarte mare, afișați suma modulo 1.000.000.007. == Date de intrare == Fișierul de intrare easy_sum.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații. == Date de ie...

2023-04-17T20:58:11Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2142/easy-sum 2142 - easy sum] ---- == Cerinţa == Se consideră un vector cu n elemente numere naturale. Calculați suma sumelor tuturor subsecvențelor ce se pot forma cu elementele vectorului. Pentru că suma poate fi foarte mare, afișați suma modulo 1.000.000.007. == Date de intrare == Fișierul de intrare easy_sum.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații. == Date de ie...

New page

Sursa: [https://www.pbinfo.ro/probleme/2142/easy-sum 2142 - easy sum]
----
== Cerinţa ==
Se consideră un vector cu n elemente numere naturale. Calculați suma sumelor tuturor subsecvențelor ce se pot forma cu elementele vectorului. Pentru că suma poate fi foarte mare, afișați suma modulo 1.000.000.007.

== Date de intrare ==
Fișierul de intrare easy_sum.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

== Date de ieșire ==
Fișierul de ieșire easy_sum.out va conține pe prima linie numărul S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000
* numerele de pe a doua linie a fișierului de intrare vor fi cuprinse în intervalul [1,1.000.000]
* prin subsecvență înțelegem orice înșiruire de elemente din vector aflate pe poziții consecutive.
== Exemplu ==
; Intrare
: 3
: 1 2 3
; Ieșire
: 20

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2142 - easy sum

MOD = 1000000007

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

def solve(n, nums):
# suma tuturor subsecventelor va fi data de:
# suma(sum[i:j]) pentru i in [0, n) si j in [i+1, n+1)
# putem rescrie asta ca:
# suma(sum[i:n]) + suma(sum[0:j]) - suma(sum[0:i]) pentru i in [0, n) si j in [i+1, n+1)
# (primul termen este suma tuturor subsecventelor care incep cu i,
# al doilea termen este suma tuturor subsecventelor care se termina cu j-1,
# iar al treilea termen este suma tuturor subsecventelor care incep inainte de i)
# putem calcula aceste sume partial pentru a reduce timpul de executie

# calculam suma tuturor numerelor din nums si suma partiala a numerelor din nums
total_sum = sum(nums)
partial_sums = [0]
for num in nums:
partial_sums.append((partial_sums[-1] + num) % MOD)

# calculam suma tuturor subsecventelor
subseq_sum = 0
for i in range(n):
# calculam sum[0:i] si sum[i:n]
left_sum = partial_sums[i+1]
right_sum = (total_sum - partial_sums[i+1] + MOD) % MOD

# adaugam la suma totala suma tuturor subsecventelor care incep cu i
subseq_sum += (i+1) * left_sum
subseq_sum %= MOD

# adaugam la suma totala suma tuturor subsecventelor care se termina cu j-1
subseq_sum += (n-i) * right_sum
subseq_sum %= MOD

# adaugam la suma totala suma tuturor subsecventelor care incep inainte de i
subseq_sum += left_sum * right_sum
subseq_sum %= MOD

return subseq_sum

def validate_output(expected_output, output):
return int(expected_output) == int(output)

if __name__ == '__main__':
n, nums = read_input()
result = solve(n, nums)
print(result)

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare din stdin și le returnează ca o tuplă (n, nums).
Funcția solve primește n și nums și calculează suma tuturor subsecvențelor ca descris în comentarii. În loc să calculeze suma tuturor subsecvențelor direct, calculează sume parțiale și le combină ulterior.
Funcția validate_output primește ieșirea așteptată și ieșirea obținută și returnează True dacă acestea sunt egale (ignorând spațiile suplimentare).
În if __name__ == '__main__', se citesc datele de intrare, se rezolvă