3206 - Nr Inversiuni - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T11:23:17Z

Rezolvare

← Older revision		Revision as of 11:23, 29 December 2023
Line 35:		Line 35:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def ~~count_inversions~~(arr):		def este_permutare_valida(n, permutare):
			if n != len(permutare):
			return False

			elemente_unice = set(permutare)
			return len(elemente_unice) == n and all(1 <= elem <= n for elem in elemente_unice)

			def numara_inversiuni(arr):
	if len(arr) <= 1:		if len(arr) <= 1:
	return arr, 0		return arr, 0

	~~mid~~ = len(arr) // 2		mijloc = len(arr) // 2
	~~left~~, ~~left_inversions~~ = ~~count_inversions~~(arr[:~~mid~~])		stanga, inversiuni_stanga = numara_inversiuni(arr[:mijloc])
	~~right~~, ~~right_inversions~~ = ~~count_inversions~~(arr[~~mid~~:])		dreapta, inversiuni_dreapta = numara_inversiuni(arr[mijloc:])

	~~merged, split_inversions = merge_and_count(left, right~~)

	~~total_inversions~~ = ~~left_inversions + right_inversions + split_inversions~~		concatenat, inversiuni_split = combina_si_numara(stanga, dreapta)

	~~return merged, total_inversions~~		inversiuni_totale = inversiuni_stanga + inversiuni_dreapta + inversiuni_split

			return concatenat, inversiuni_totale

	def ~~merge_and_count~~(~~left~~, ~~right~~):		def combina_si_numara(stanga, dreapta):
	~~merged~~ = []		concatenat = []
	~~split_inversions~~ = 0		inversiuni_split = 0
	i = j = 0		i = j = 0

	while i < len(~~left~~) and j < len(~~right~~):		while i < len(stanga) and j < len(dreapta):
	if ~~left~~[i] <= ~~right~~[j]:		if stanga[i] <= dreapta[j]:
	~~merged~~.append(~~left~~[i])		concatenat.append(stanga[i])
	i += 1		i += 1
	else:		else:
	~~merged~~.append(~~right~~[j])		concatenat.append(dreapta[j])
	~~split_inversions~~ += len(~~left~~) - i		inversiuni_split += len(stanga) - i
	j += 1		j += 1

	~~merged~~.extend(~~left~~[i:])		concatenat.extend(stanga[i:])
	~~merged~~.extend(~~right~~[j:])		concatenat.extend(dreapta[j:])

	~~return merged, split_inversions~~

			return concatenat, inversiuni_split

	if __name__ == "__main__":		if __name__ == "__main__":
	n = int(input("Introduceți numărul n: "))		n = int(input("Introduceți numărul n: "))
	~~permutation~~ = list(map(int, input("Introduceți permutarea: ").split()))		permutare = list(map(int, input("Introduceți permutarea: ").split()))

	_, ~~inversions~~ = ~~count_inversions~~(~~permutation~~)		if este_permutare_valida(n, permutare):
			_, inversiuni = numara_inversiuni(permutare)
			print("Numărul inversiunilor permutării:", inversiuni)
			else:
			print("Permutarea introdusă nu este validă.")

	~~print("Numărul inversiunilor permutării:", inversions)~~

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa: /* Rezolvare */

2023-12-27T09:13:24Z

Rezolvare

← Older revision		Revision as of 09:13, 27 December 2023
Line 35:		Line 35:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def ~~numar_inversiuni_permutare~~(~~n, permutare~~):		def count_inversions(arr):
	~~numar_inversiuni~~ = 0		if len(arr) <= 1:
			return arr, 0

	~~for i in range~~(~~n - 1~~):		mid = len(arr) // 2
	~~for j in range~~(~~i + 1, n~~):		left, left_inversions = count_inversions(arr[:mid])
	~~if permutare~~[i] ~~> permutare[j]:~~		right, right_inversions = count_inversions(arr[mid:])
	~~numar_inversiuni += 1~~

	~~return numar_inversiuni~~		merged, split_inversions = merge_and_count(left, right)

	~~def main():~~		total_inversions = left_inversions + right_inversions + split_inversions
	~~# Citirea datelor de intrare de la tastatură~~
	~~n = int(input("Introduceti numarul n: "))~~
	~~permutare~~ = ~~list(map(int, input(f"Introduceti permutarea de lungime {n}, separate prin spatiu: ").split()))~~

	~~# Calcularea numărului de inversiuni~~		return merged, total_inversions
	~~rezultat~~ = ~~numar_inversiuni_permutare~~(n, ~~permutare)~~

			def merge_and_count(left, right):
			merged = []
			split_inversions = 0
			i = j = 0

			while i < len(left) and j < len(right):
			if left[i] <= right[j]:
			merged.append(left[i])
			i += 1
			else:
			merged.append(right[j])
			split_inversions += len(left) - i
			j += 1

			merged.extend(left[i:])
			merged.extend(right[j:])

			return merged, split_inversions

	~~# Afișarea rezultatului~~
	~~print(f"Numarul de inversiuni in permutare este: {rezultat}")~~

	if __name__ == "__main__":		if __name__ == "__main__":
	~~main~~()		n = int(input("Introduceți numărul n: "))
			permutation = list(map(int, input("Introduceți permutarea: ").split()))

			_, inversions = count_inversions(permutation)

			print("Numărul inversiunilor permutării:", inversions)

	</syntaxhighlight>		</syntaxhighlight>

	== Explicatie ==		== Explicatie ==
	Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).		Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).

Mesarosdenisa: /* Exemplul 2 */

2023-12-27T08:23:47Z

Exemplul 2

← Older revision		Revision as of 08:23, 27 December 2023
Line 28:		Line 28:
	== Exemplul 2 ==		== Exemplul 2 ==
	;Intrare		;Intrare
	:4		:5
	:-2 8 0 3		:-2 8 0 3
	;Iesire		;Iesire

Mesarosdenisa at 08:21, 27 December 2023

2023-12-27T08:21:59Z

← Older revision		Revision as of 08:21, 27 December 2023
Line 1:		Line 1:
	Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j].		== Enunt ==
			Se dă șirul '''a1, a2, …, an''' care este o permutare a mulțimii '''{1, 2, ..., n}'''. O '''inversiune''' în permutare este o pereche '''(i, j)''' cu proprietatea că '''i < j''' și '''a[i] > a[j]'''.

	== Cerinta ==		== Cerinta ==
Line 7:		Line 8:
	== Date de intrare ==		== Date de intrare ==

	Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.		Programul citește de la tastatură numărul '''n''', iar apoi '''n''' numere naturale, separate prin spații, reprezentând permutarea.

	== Date de iesire ==		== Date de iesire ==

	Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.		Programul va afișa pe ecran numărul '''S''', reprezentând numărul inversiunilor permutării.

	== Restrictii si precizari ==		== Restrictii si precizari ==

	*1 ≤ n ≤ 100.000		*1 &les; n &les; 100.000

	== Exemplul 1 ==		== Exemplul 1 ==
Line 22:		Line 23:
	:4 2 5 1 3		:4 2 5 1 3
	;Iesire		;Iesire
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:6		:6

Line 30:		Line 31:
	:-2 8 0 3		:-2 8 0 3
	;Iesire		;Iesire
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse

	== Rezolvare ==		== Rezolvare ==

Mesarosdenisa at 10:08, 12 December 2023

2023-12-12T10:08:21Z

← Older revision		Revision as of 10:08, 12 December 2023
Line 19:		Line 19:
	== Exemplul 1 ==		== Exemplul 1 ==
	;Intrare		;Intrare
	;5		:5
	;4 2 5 1 3		:4 2 5 1 3
	;Iesire		;Iesire
	;Datele introduse corespund restrictiilor impuse		;Datele introduse corespund restrictiilor impuse
	;6		:6

	== Exemplul 2 ==		== Exemplul 2 ==
	;Intrare		;Intrare
	;4		:4
	;-2 8 0 3		:-2 8 0 3
	;Iesire		;Iesire
	;Datele introduse nu corespund restrictiilor impuse		;Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa at 09:07, 12 December 2023

2023-12-12T09:07:45Z

← Older revision		Revision as of 09:07, 12 December 2023
Line 9:		Line 9:
	Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.		Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.

	== Date de ~~iesie~~ ==		== Date de iesire ==

	Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.		Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.

Mesarosdenisa at 08:59, 12 December 2023

2023-12-12T08:59:10Z

← Older revision		Revision as of 08:59, 12 December 2023
Line 17:		Line 17:
	*1 ≤ n ≤ 100.000		*1 ≤ n ≤ 100.000

	== Exemplul 1		== Exemplul 1 ==
	;Intrare		;Intrare
	;5		;5
Line 25:		Line 25:
	;6		;6

	== Exemplul 2==		== Exemplul 2 ==
	;Intrare		;Intrare
	;4		;4

Mesarosdenisa: Pagină nouă: Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j]. == Cerinta == Să se determine numărul inversiunilor permutării. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea. == Date de iesie == Programul va afișa pe ecran numărul S, reprezentând numărul inve...

2023-12-12T08:58:31Z

Pagină nouă: Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j]. == Cerinta == Să se determine numărul inversiunilor permutării. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea. == Date de iesie == Programul va afișa pe ecran numărul S, reprezentând numărul inve...

New page

Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j].

== Cerinta ==

Să se determine numărul inversiunilor permutării.

== Date de intrare ==

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.

== Date de iesie ==

Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.

== Restrictii si precizari ==

*1 ≤ n ≤ 100.000

== Exemplul 1
;Intrare
;5
;4 2 5 1 3
;Iesire
;Datele introduse corespund restrictiilor impuse
;6

== Exemplul 2==
;Intrare
;4
;-2 8 0 3
;Iesire
;Datele introduse nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def numar_inversiuni_permutare(n, permutare):
numar_inversiuni = 0

for i in range(n - 1):
for j in range(i + 1, n):
if permutare[i] > permutare[j]:
numar_inversiuni += 1

return numar_inversiuni

def main():
# Citirea datelor de intrare de la tastatură
n = int(input("Introduceti numarul n: "))
permutare = list(map(int, input(f"Introduceti permutarea de lungime {n}, separate prin spatiu: ").split()))

# Calcularea numărului de inversiuni
rezultat = numar_inversiuni_permutare(n, permutare)

# Afișarea rezultatului
print(f"Numarul de inversiuni in permutare este: {rezultat}")

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).