2236 - swap01 - Revision history

Flaviu at 21:20, 14 May 2023

2023-05-14T21:20:01Z

← Older revision		Revision as of 21:20, 14 May 2023
Line 40:		Line 40:
	# 2236 - swap01		# 2236 - swap01

	def ~~citire_lista~~():		def validate_input(n, arr):
	n = ~~int~~(~~input~~())		if not (1 <= n <= 100000):
	~~lista = input~~().~~split()~~		return False
	~~lista~~ = ~~[int~~(x) ~~for x in lista]~~		if len(arr) != n:
	~~return lista~~		return False
			return True


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

			# Determinăm numărul de valori de 1 din șir
			count_ones = arr.count(1)

			# Numărul minim de operații swap este diferența dintre lungimea șirului și numărul de valori de 1
			min_swaps = n - count_ones

	~~def numara_unu(lista):~~		return min_swaps
	~~pozitii_unu = []~~
	~~for i in range(len(lista)):~~
	~~if lista[i] == 1:~~
	~~pozitii_unu.append(i)~~
	return ~~len(pozitii_unu), pozitii_unu~~

	~~def calculeaza_swap(lista, pozitii_unu):~~
	~~nr_unu, pozitii_unu = numara_unu(lista)~~
	~~nr_grupuri = len(pozitii_unu)~~
	~~start = pozitii_unu[0]~~
	~~end = pozitii_unu[-1]~~
	~~for i in range(nr_grupuri):~~
	~~if pozitii_unu[i] - i != start:~~
	~~start = pozitii_unu[i]~~
	~~if end - pozitii_unu[-i-1] != i:~~
	~~end = pozitii_unu[-i-1]~~
	~~return nr_grupuri - (end - start + 1)~~

	if __name__ == "__main__":		if __name__ == "__main__":
	~~try:~~		n = int(input())
	~~lista~~ = ~~citire_lista~~()		arr = list(map(int, input().split()))
	~~nr_unu, pozitii_unu~~ = ~~numara_unu~~(~~lista)~~
	~~rezultat = calculeaza_swap~~(~~lista~~, ~~pozitii_unu~~)		result = count_swaps(n, arr)
	~~print~~(~~"Datele sunt introduse corect."~~)		print(result)
	~~print~~(~~rezultat~~)
	~~except:~~
	print(~~"Datele nu corespund restricțiilor impuse."~~)

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Pentru a rezolva această problemă, putem parcurge șirul și să numărăm câte elemente~~ de 1 sunt ~~și unde~~ se află ~~acestea. După aceea, putem verifica~~ în ~~câte părți separate trebuie împărțit șirul (adică câte grupuri separate de~~ 1 ~~sunt)~~ și ~~putem calcula numărul de operații swap necesare pentru a muta fiecare grup la poziția corectă~~.		Avem funcția validate_input care verifică dacă datele de intrare sunt valide. Verificăm dacă n se află în intervalul [1, 100000] și dacă lungimea listei arr este egală cu n.

	~~Pentru~~ a ~~implementa această soluție, vom crea trei funcții:~~		Funcția principală count_swaps primește numărul de elemente n și lista arr ca argumente. În primul rând, verificăm validitatea datelor de intrare folosind funcția validate_input. Apoi, numărăm numărul de valori de 1 din șir utilizând metoda count a listei. Numărul minim de operații swap este diferența dintre lungimea șirului n și numărul de valori de 1 count_ones.

	~~citire_lista(): Această funcție va citi de la tastatură numărul de elemente din șir și apoi elementele șirului. Funcția va returna lista citită.~~		În blocul if __name__ == "__main__":, citim valorile de intrare n și arr folosind funcția input(). Apoi apelăm funcția count_swaps și afișăm rezultatul.
	~~numara_unu(lista): Această funcție va primi lista citită ca parametru și va returna un tuplu cu numărul de elemente de 1 din listă și o listă cu pozițiile acestora.~~
	calculeaza_swap(lista, pozitii_unu): Această funcție va primi lista citită și lista cu pozițiile elementelor de 1. Funcția va determina în câte grupuri trebuie împărțit șirul și va calcula numărul de operații swap necesare pentru a muta fiecare grup la poziția corectă. Funcția va returna numărul total de operații swap necesare.
	~~La final, vom avea un bloc~~ if __name__ == "__main__": ~~în care vom apela cele trei funcții~~ și ~~vom afișa~~ rezultatul.

Flaviu at 07:55, 3 May 2023

2023-05-03T07:55:58Z

← Older revision		Revision as of 07:55, 3 May 2023
Line 14:		Line 14:
	== 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 '''umărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir''', 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 ==
	* 1 ≤ n ≤ 100.000		* 1 ≤ n ≤ 100.000
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: 14		: 14
	: 1 0 0 1 0 1 1 0 1 0 0 0 1 0		: 1 0 0 1 0 1 1 0 1 0 0 0 1 0
	; Ieșire		; Ieșire
	~~: Datele nu corespund restricțiilor impuse.~~
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 2		: 2


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


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:37, 28 April 2023

2023-04-28T14:37:07Z

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

	== Date de ieșire ==		== Date de ieșire ==
	~~Programul~~ va afișa pe ~~ecran~~ numărul ~~minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară~~ pe ~~poziții consecutive în șir~~.		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:
	: 1 0 0 1 0 1 1 0 1 0 0 0 1 0		: 1 0 0 1 0 1 1 0 1 0 0 0 1 0
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 2		: 2

Line 55:		Line 58:

	if __name__ == "__main__":		if __name__ == "__main__":
	lista = citire_lista()		try:
	nr_unu, pozitii_unu = numara_unu(lista)		lista = citire_lista()
	~~print(~~calculeaza_swap(lista, pozitii_unu))		nr_unu, pozitii_unu = numara_unu(lista)
			rezultat = calculeaza_swap(lista, pozitii_unu)
			print("Datele sunt introduse corect.")
			print(rezultat)
			except:
			print("Datele nu corespund restricțiilor impuse.")

	</syntaxhighlight>		</syntaxhighlight>

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2236/swap01 2236 - swap01] ---- Se consideră un șir binar a[1], a[2], …, a[n]. Asupra șirului se poate efectua operația swap(i, j) prin care se interschimbă valorile a[i] și a[j]. == Cerinţa == Să se determine numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n n...

2023-04-17T20:52:05Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2236/swap01 2236 - swap01] ---- Se consideră un șir binar a[1], a[2], …, a[n]. Asupra șirului se poate efectua operația swap(i, j) prin care se interschimbă valorile a[i] și a[j]. == Cerinţa == Să se determine numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n n...

New page

Sursa: [https://www.pbinfo.ro/probleme/2236/swap01 2236 - swap01]
----
Se consideră un șir binar a[1], a[2], …, a[n]. Asupra șirului se poate efectua operația swap(i, j) prin care se interschimbă valorile a[i] și a[j].

== Cerinţa ==
Să se determine numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir.

== Date de intrare ==
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații reprezentând elementele șirului binar.

== Date de ieșire ==
Programul va afișa pe ecran numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000
== Exemplu ==
; Intrare
: 14
: 1 0 0 1 0 1 1 0 1 0 0 0 1 0
; Ieșire
: 2

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2236 - swap01

def citire_lista():
n = int(input())
lista = input().split()
lista = [int(x) for x in lista]
return lista

def numara_unu(lista):
pozitii_unu = []
for i in range(len(lista)):
if lista[i] == 1:
pozitii_unu.append(i)
return len(pozitii_unu), pozitii_unu

def calculeaza_swap(lista, pozitii_unu):
nr_unu, pozitii_unu = numara_unu(lista)
nr_grupuri = len(pozitii_unu)
start = pozitii_unu[0]
end = pozitii_unu[-1]
for i in range(nr_grupuri):
if pozitii_unu[i] - i != start:
start = pozitii_unu[i]
if end - pozitii_unu[-i-1] != i:
end = pozitii_unu[-i-1]
return nr_grupuri - (end - start + 1)

if __name__ == "__main__":
lista = citire_lista()
nr_unu, pozitii_unu = numara_unu(lista)
print(calculeaza_swap(lista, pozitii_unu))

</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru a rezolva această problemă, putem parcurge șirul și să numărăm câte elemente de 1 sunt și unde se află acestea. După aceea, putem verifica în câte părți separate trebuie împărțit șirul (adică câte grupuri separate de 1 sunt) și putem calcula numărul de operații swap necesare pentru a muta fiecare grup la poziția corectă.

Pentru a implementa această soluție, vom crea trei funcții:

citire_lista(): Această funcție va citi de la tastatură numărul de elemente din șir și apoi elementele șirului. Funcția va returna lista citită.
numara_unu(lista): Această funcție va primi lista citită ca parametru și va returna un tuplu cu numărul de elemente de 1 din listă și o listă cu pozițiile acestora.
calculeaza_swap(lista, pozitii_unu): Această funcție va primi lista citită și lista cu pozițiile elementelor de 1. Funcția va determina în câte grupuri trebuie împărțit șirul și va calcula numărul de operații swap necesare pentru a muta fiecare grup la poziția corectă. Funcția va returna numărul total de operații swap necesare.
La final, vom avea un bloc if __name__ == "__main__": în care vom apela cele trei funcții și vom afișa rezultatul.