3281 - sminus - Revision history

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

2023-05-14T22:31:28Z

Date de ieșire

← Older revision		Revision as of 22:31, 14 May 2023
Line 16:		Line 16:

	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."''' fișierul de ieșire sminus.out va conține . Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.''', 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 sminus.out va conține 2 numere x și y separate printr - un spațiu . Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.''', 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 ==

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

2023-05-14T22:30:48Z

Date de ieșire

← Older revision		Revision as of 22:30, 14 May 2023
Line 14:		Line 14:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire sminus.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 '''Pe prima linie se vor găsi două numere naturale x și y separate printr-un spațiu reprezentând perechea~~ de ~~indici~~. Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.''', 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 sminus.out va conține . Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.''', 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:43, 14 May 2023

2023-05-14T21:43:25Z

← Older revision		Revision as of 21:43, 14 May 2023
Line 30:		Line 30:
	: 3 -5 4 -1 6 -8 -5		: 3 -5 4 -1 6 -8 -5
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: sminus.out		: sminus.out
	~~: Datele sunt introduse correct.~~
	: 3 5		: 3 5
	: -24		: -24
Line 41:		Line 41:
	: 3 -5 4 -1 6 -8 -5		: 3 -5 4 -1 6 -8 -5
	; Ieșire		; Ieșire
	~~: sminus.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 50:		Line 49:
	# 3281 - sminus		# 3281 - sminus

	def ~~read_input~~():		def find_min_sum_sequence(n, arr):
	n = ~~int(input~~())		min_sum = float('inf')
	a = ~~list~~(~~map~~(~~int~~, ~~input(~~)~~.split~~()))		start_index = 0
	return n, a		end_index = 0
			current_sum = 0
			for i in range(n):
			for j in range(i, n):
			current_sum = sum(arr[i:j+1])
			if current_sum < min_sum:
			min_sum = current_sum
			start_index = i
			end_index = j
			return start_index, end_index, min_sum

	~~def solve(n, a):~~
	~~best_sum = sum(a)~~
	~~best_x, best_y = 1, n~~
	~~cur_sum = 0~~
	~~cur_x = 1~~
	~~for i in range(n):~~
	~~cur_sum += a[i]~~
	~~if cur_sum < best_sum:~~
	~~best_sum = cur_sum~~
	~~best_x, best_y = cur_x, i+1~~
	~~if cur_sum > 0:~~
	~~cur_sum = 0~~
	~~cur_x = i+2~~
	~~return best_x, best_y, best_sum~~

	def ~~validate~~(n, ~~a, x, y, s~~):		def validate_input(n, arr):
	~~assert 1~~ <= x <= y <= n		if not (2 <= n <= 100000):
	for i in ~~range(x-1, y~~):		return False
	~~a[i] *= -1~~		if not all(-1000 <= num <= 1000 for num in arr):
	~~assert sum(a) == s~~		return False
			return True

	~~if __name__ == '__main__':~~
	~~n, a = read_input()~~
	~~x, y, s = solve(n, a)~~
	~~try:~~
	~~validate(n, a, x, y, s)~~
	~~print("Datele sunt introduse corect.")~~
	~~print(x, y)~~
	~~print(s)~~
	~~except AssertionError:~~
	~~print("Datele nu corespund restricțiilor impuse.")~~

			if __name__ == "__main__":
			with open("sminus.in", "r") as input_file, open("sminus.out", "w") as output_file:
			n = int(input_file.readline().strip())
			arr = list(map(int, input_file.readline().strip().split()))

			if not validate_input(n, arr):
			output_file.write("Datele nu corespund restricțiilor impuse.")
			else:
			start_index, end_index, min_sum = find_min_sum_sequence(n, arr)
			output_file.write("Datele sunt introduse correct.\n")
			output_file.write(f"{start_index + 1} {end_index + 1}\n")
			output_file.write(f"{min_sum}")

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Funcția~~ read_input ~~citește datele~~ de intrare și le returnează ~~sub formă~~ de ~~tuple~~ (n, a).		read_input(): Această funcție este responsabilă de citirea datelor de intrare. Ea citește valorile din fișierul "sminus.in" și returnează acele valori necesare pentru rezolvarea problemei. În acest caz, citim mai întâi numărul N, apoi citim secvența a1, a2, ..., aN.

			solve_problem(N, seq): Această funcție primește ca parametri numărul N și secvența seq. Ea rezolvă problema și returnează o tuplă conținând perechea de indici (x, y) și suma minimă obținută prin inversarea semnului componentelor secvenței. Pentru a rezolva problema, funcția parcurge secvența și calculează suma parțială pe măsură ce inversăm semnul. Pentru a găsi perechea optimă, se țin cont de cerințele enunțului referitoare la ordinea și valoarea minimă/maximă.

	~~Funcția solve~~ primește n și a și ~~determină o pereche~~ de ~~indici x și y astfel încât după inversarea semnului componentelor~~ secvenței ax, ~~ax+1~~, ~~…, ay suma elementelor din vector să fie minimă. Pentru a face acest lucru, parcurgem șirul~~ și ~~ținem minte cea mai mică sumă~~ și ~~indicii corespunzători până la fiecare poziție. Dacă suma curentă depășește 0, înseamnă că trebuie să începem o nouă secvență de la următoarea poziție~~.		validate_input(N, seq): Această funcție primește numărul N și secvența seq și verifică dacă datele de intrare respectă restricțiile impuse. Ea efectuează diverse verificări, cum ar fi verificarea dimensiunii secvenței, verificarea valorilor și formatei acestora, și returnează True dacă datele sunt valide și False în caz contrar.

	~~Funcția validate~~ primește ~~datele de intrare n și a,~~ perechea de indici x și y și ~~suma s~~ și ~~verifică că inversarea semnului componentelor din secvența ax, ax+1, …, ay duce la suma s~~.		write_output(indices, min_sum): Această funcție primește perechea de indici indices și suma minimă min_sum și se ocupă de scrierea rezultatelor în fișierul "sminus.out". Ea formatează rezultatele conform cerințelor și le scrie în fișierul de ieșire.

	În funcția ~~main~~, ~~apelăm funcțiile~~ în ~~ordinea corespunzătoare~~ și ~~afișăm rezultatele~~.		main(): Aceasta este funcția principală a programului. Ea verifică dacă codul este rulat ca un script principal și, în caz afirmativ, gestionează citirea datelor de intrare, validarea acestora, rezolvarea problemei și scrierea rezultatelor. Ea folosește celelalte funcții menționate mai sus pentru a realiza aceste operaț

Flaviu at 08:04, 3 May 2023

2023-05-03T08:04:33Z

← Older revision		Revision as of 08:04, 3 May 2023
Line 16:		Line 16:
	Fișierul de ieșire sminus.out va conține:		Fișierul de ieșire sminus.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 '''Pe prima linie se vor găsi două numere naturale x și y separate printr-un spațiu reprezentând perechea de indici. Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.''', 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 24:		Line 24:
	* Dacă există mai multe soluții pentru perechea (x, y), atunci se va alegea aceea care are indicele x minim, iar dacă sunt mai multe secvențe posibile care încep la poziția x, se va alege aceea care are valoarea y maximă.		* Dacă există mai multe soluții pentru perechea (x, y), atunci se va alegea aceea care are indicele x minim, iar dacă sunt mai multe secvențe posibile care încep la poziția x, se va alege aceea care are valoarea y maximă.
	* Pentru teste valorând 50 de puncte, N ≤ 2000.		* Pentru teste valorând 50 de puncte, N ≤ 2000.
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: sminus.in
	: 7		: 7
	: 3 -5 4 -1 6 -8 -5		: 3 -5 4 -1 6 -8 -5
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: sminus.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 3 5		: 3 5
	: -24		: -24

			== Exemplu 2 ==
			; Intrare
			: sminus.in
			: 7 2 3 5 0.67
			: 3 -5 4 -1 6 -8 -5
			; Ieșire
			: sminus.out
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:50, 28 April 2023

2023-04-28T14:50:07Z

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

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire sminus.out va conține ~~două linii~~. ~~Pe prima linie se vor găsi două numere naturale x și y separate printr-~~un ~~spațiu~~ reprezentând ~~perechea de indici~~. ~~Pe linia a doua~~ se va ~~găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay~~.		Fișierul de ieșire sminus.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 27:		Line 29:
	: 3 -5 4 -1 6 -8 -5		: 3 -5 4 -1 6 -8 -5
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 3 5		: 3 5
	: -24		: -24
Line 64:		Line 68:
	n, a = read_input()		n, a = read_input()
	x, y, s = solve(n, a)		x, y, s = solve(n, a)
	validate(n, a, x, y, s)		try:
	print(x, y)		validate(n, a, x, y, s)
	print(s)		print("Datele sunt introduse corect.")
			print(x, y)
			print(s)
			except AssertionError:
			print("Datele nu corespund restricțiilor impuse.")

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3281/sminus 3281 - sminus] ---- Fie un șir a1, a2, …, aN de numere întregi. În acest șir se alege o pereche de indici (x, y), 1 ≤ x ≤ y ≤ N și se inversează semnul tuturor componentelor secvenței ax, ax+1, …, ay. De exemplu, pentru șirul 3, -5, 4, -1, 6, -8, -5, dacă se alege perechea (3, 5), atunci șirul va deveni 3, -5, -4, 1, -6, -8, -5. == Cerinţa == Să se determine o pereche de indici x y astfel încât dup...

2023-04-18T07:03:20Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3281/sminus 3281 - sminus] ---- Fie un șir a1, a2, …, aN de numere întregi. În acest șir se alege o pereche de indici (x, y), 1 ≤ x ≤ y ≤ N și se inversează semnul tuturor componentelor secvenței ax, ax+1, …, ay. De exemplu, pentru șirul 3, -5, 4, -1, 6, -8, -5, dacă se alege perechea (3, 5), atunci șirul va deveni 3, -5, -4, 1, -6, -8, -5. == Cerinţa == Să se determine o pereche de indici x y astfel încât dup...

New page

Sursa: [https://www.pbinfo.ro/probleme/3281/sminus 3281 - sminus]
----

Fie un șir a1, a2, …, aN de numere întregi. În acest șir se alege o pereche de indici (x, y), 1 ≤ x ≤ y ≤ N și se inversează semnul tuturor componentelor secvenței ax, ax+1, …, ay. De exemplu, pentru șirul 3, -5, 4, -1, 6, -8, -5, dacă se alege perechea (3, 5), atunci șirul va deveni 3, -5, -4, 1, -6, -8, -5.

== Cerinţa ==
Să se determine o pereche de indici x y astfel încât după inversarea semnului componentelor secvenței ax, ax+1, …, ay suma elementelor din vector să fie minimă.

== Date de intrare ==
Fișierul de intrare sminus.in conține pe prima linie numărul N. Pe a doua linie, separate prin câte un spațiu, se găsesc numerele întregi a1, a2, …, aN.

== Date de ieșire ==
Fișierul de ieșire sminus.out va conține două linii. Pe prima linie se vor găsi două numere naturale x și y separate printr-un spațiu reprezentând perechea de indici. Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.

== Restricţii şi precizări ==
* 2 ≤ N ≤ 100.000
* -1000 ≤ ai ≤ 1000 pentru orice i = 1..N
* Secvența ax, ax+1, …, ay trebuie să conțină cel puțin un element.
* Dacă există mai multe soluții pentru perechea (x, y), atunci se va alegea aceea care are indicele x minim, iar dacă sunt mai multe secvențe posibile care încep la poziția x, se va alege aceea care are valoarea y maximă.
* Pentru teste valorând 50 de puncte, N ≤ 2000.
== Exemplu ==
; Intrare
: 7
: 3 -5 4 -1 6 -8 -5
; Ieșire
: 3 5
: -24

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3281 - sminus

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

def solve(n, a):
best_sum = sum(a)
best_x, best_y = 1, n
cur_sum = 0
cur_x = 1
for i in range(n):
cur_sum += a[i]
if cur_sum < best_sum:
best_sum = cur_sum
best_x, best_y = cur_x, i+1
if cur_sum > 0:
cur_sum = 0
cur_x = i+2
return best_x, best_y, best_sum

def validate(n, a, x, y, s):
assert 1 <= x <= y <= n
for i in range(x-1, y):
a[i] *= -1
assert sum(a) == s

if __name__ == '__main__':
n, a = read_input()
x, y, s = solve(n, a)
validate(n, a, x, y, s)
print(x, y)
print(s)

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare și le returnează sub formă de tuple (n, a).

Funcția solve primește n și a și determină o pereche de indici x și y astfel încât după inversarea semnului componentelor secvenței ax, ax+1, …, ay suma elementelor din vector să fie minimă. Pentru a face acest lucru, parcurgem șirul și ținem minte cea mai mică sumă și indicii corespunzători până la fiecare poziție. Dacă suma curentă depășește 0, înseamnă că trebuie să începem o nouă secvență de la următoarea poziție.

Funcția validate primește datele de intrare n și a, perechea de indici x și y și suma s și verifică că inversarea semnului componentelor din secvența ax, ax+1, …, ay duce la suma s.

În funcția main, apelăm funcțiile în ordinea corespunzătoare și afișăm rezultatele.