3490 - Permutari AB - Revision history

Andrada378: /* Rezolvare */

2024-01-08T17:40:18Z

Rezolvare

← Older revision		Revision as of 17:40, 8 January 2024
Line 12:		Line 12:

	== Restricții și precizări ==		== Restricții și precizări ==
	~~1 ≤ N ≤ 100.000~~

	Pentru 70% din teste, 1 ≤ N ≤ 1000		* 1 ≤ N ≤ 100.000
			* Pentru 70% din teste, 1 ≤ N ≤ 1000

	=== Exemplu 1 ===		=== Exemplu 1 ===
Line 51:		Line 51:
	with open(nume_fisier, 'r') as file:		with open(nume_fisier, 'r') as file:
	n = int(file.readline())		n = int(file.readline())

			# Adaugăm verificarea pentru intervalul specificat
			if not (1 <= n <= 100000):
			print("Numarul N nu se afla in intervalul permis.")
			return

	permutare_A = list(map(int, file.readline().split()))		permutare_A = list(map(int, file.readline().split()))
	permutare_B = list(map(int, file.readline().split()))		permutare_B = list(map(int, file.readline().split()))
Line 71:		Line 77:
	file_out.write(f"{numar_operatii}\n")		file_out.write(f"{numar_operatii}\n")

	if '__name__' == "~~_main_~~":		if __name__ == "__main__":
	main()		main()

	</syntaxhighlight>		</syntaxhighlight>

Andrada378 at 11:51, 2 January 2024

2024-01-02T11:51:06Z

← Older revision		Revision as of 11:51, 2 January 2024
Line 1:		Line 1:
	~~Cerinta~~		== Enunț ==
			Se consideră 2 permutări A şi B ale mulţimii {1, 2, ..., N}. Printr-o operaţie se pot selecta două elemente adiacente din B şi să se interschimbe (i.e. swap(B[i], B[i + 1]) pentru 1 ≤ i < N).

			== Cerința ==
	Să se determine numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.		Să se determine numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.

	Date de intrare		== Date de intrare ==

	Fişierul de intrare permutariab.in conţine pe prima linie numărul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând permutarea A. Pe a treia linie se află de asemenea N numere naturale, separate prin câte un spaţiu, reprezentând permutarea B.		Fişierul de intrare permutariab.in conţine pe prima linie numărul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând permutarea A. Pe a treia linie se află de asemenea N numere naturale, separate prin câte un spaţiu, reprezentând permutarea B.

	Date de iesire		== Date de iesire ==

	Fişierul de ieşire permutariab.out conţine pe prima linie numărul natural X, reprezentând numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.		Fişierul de ieşire permutariab.out conţine pe prima linie numărul natural X, reprezentând numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.

			== Restricții și precizări ==
			1 ≤ N ≤ 100.000

	~~Rezolvare~~		Pentru 70% din teste, 1 ≤ N ≤ 1000

			=== Exemplu 1 ===
			permutariabin.txt

	~~<nowiki>#</nowiki> Funcție pentru citirea permutărilor din fișier text~~		6

	~~def citeste_permutari(nume_fisier):~~		2 1 3 4 5 6

	~~with open(nume_fisier, 'r') as file:~~		1 3 4 5 6 2

	~~n = int(file~~.~~readline())~~		permutariabout.txt

	~~permutare_A = list(map(int, file.readline().split()))~~		5

	~~permutare_B~~ = ~~list(map(int, file.readline()~~.~~split()))~~		=== Exemplu 2: ===
			permutariabin.txt

	~~return n, permutare_A, permutare_B~~		10

	~~<nowiki>#</nowiki> Funcție pentru determinarea numărului minim de operații~~		1 5 2 3 4 6 9 10 7 8

	~~def numar_minim_operatii(n, permutare_A, permutare_B):~~		3 9 5 1 2 7 8 10 4 6

	~~# Inițializăm numărul minim de operații~~		permutariabout.txt

	~~numar_operatii = 0~~		17

	~~# Parcurgem permutarea și comparăm elementele~~		== Explicație ==
			În primul exemplu, se interschimbă 2 cu 6, apoi 2 cu 5, apoi 2 cu 4, apoi 2 cu 3 apoi 2 cu 1.

	~~for i in range~~(n ~~- 1~~):		== Rezolvare ==
			<syntaxhighlight lang="python">
			def citeste_permutari():
			nume_fisier = 'permutariabin.txt'
			with open(nume_fisier, 'r') as file:
			n = int(file.readline())
			permutare_A = list(map(int, file.readline().split()))
			permutare_B = list(map(int, file.readline().split()))
			return n, permutare_A, permutare_B

	~~# Dacă elementele nu sunt în ordinea corectă~~, ~~creștem numărul de operații~~		def numar_minim_operatii(n, permutare_A, permutare_B):
			numar_operatii = 0
	if permutare_B[i] != permutare_A[i]:		for i in range(n - 1):
			if permutare_B[i] != permutare_A[i]:
	~~# Efectuăm operațiile necesare pentru a aduce elementul în poziția corectă~~		index = permutare_B.index(permutare_A[i])
			permutare_B[i], permutare_B[index] = permutare_B[index], permutare_B[i]
	index = permutare_B.index(permutare_A[i])		numar_operatii += 1
			return numar_operatii
	permutare_B[i], permutare_B[index] = permutare_B[index], permutare_B[i]

	numar_operatii += 1



	return numar_operatii

	def main():		def main():
			numar, permutare_A, permutare_B = citeste_permutari()
			numar_operatii = numar_minim_operatii(numar, permutare_A, permutare_B)
			nume_fisier_iesire = 'permutariabout.txt'
			with open(nume_fisier_iesire, 'w') as file_out:
			file_out.write(f"{numar_operatii}\n")

	~~# Citim permutările din fișierul text~~		if '__name__' == "_main_":
			main()
	~~numar, permutareA, permutareB = citeste_permutari(~~'~~permutariab.txt')~~		</syntaxhighlight>

	~~# Determinăm numărul minim de operații~~

	~~numar_operatii = numar_minim_operatii(numar, permutareA, permutareB)~~

	~~# Scriem rezultatul în fișierul text de ieșire~~

	~~with open('rezultat_permutari.txt', 'w~~'~~) as file_out:~~

	~~file_out.write(f"Numărul minim de operații: {numar_operatii}")~~

	~~if __name__~~ == "~~__main__~~":

	~~main()~~

Andrada378: Pagină nouă: Cerinta Să se determine numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A. Date de intrare Fişierul de intrare permutariab.in conţine pe prima linie numărul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând permutarea A. Pe a treia linie se află de asemenea N numere naturale, separate prin câte un spaţiu, reprezentând permutarea B. Date de iesire Fişierul de ieşire permutariab...

2023-12-14T12:44:29Z

Pagină nouă: Cerinta Să se determine numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A. Date de intrare Fişierul de intrare permutariab.in conţine pe prima linie numărul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând permutarea A. Pe a treia linie se află de asemenea N numere naturale, separate prin câte un spaţiu, reprezentând permutarea B. Date de iesire Fişierul de ieşire permutariab...

New page

Cerinta

Să se determine numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.

Date de intrare

Fişierul de intrare permutariab.in conţine pe prima linie numărul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând permutarea A. Pe a treia linie se află de asemenea N numere naturale, separate prin câte un spaţiu, reprezentând permutarea B.

Date de iesire

Fişierul de ieşire permutariab.out conţine pe prima linie numărul natural X, reprezentând numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.

Rezolvare

<nowiki>#</nowiki> Funcție pentru citirea permutărilor din fișier text

def citeste_permutari(nume_fisier):

with open(nume_fisier, 'r') as file:

n = int(file.readline())

permutare_A = list(map(int, file.readline().split()))

permutare_B = list(map(int, file.readline().split()))

return n, permutare_A, permutare_B

<nowiki>#</nowiki> Funcție pentru determinarea numărului minim de operații

def numar_minim_operatii(n, permutare_A, permutare_B):

# Inițializăm numărul minim de operații

numar_operatii = 0

# Parcurgem permutarea și comparăm elementele

for i in range(n - 1):

# Dacă elementele nu sunt în ordinea corectă, creștem numărul de operații

if permutare_B[i] != permutare_A[i]:

# Efectuăm operațiile necesare pentru a aduce elementul în poziția corectă

index = permutare_B.index(permutare_A[i])

permutare_B[i], permutare_B[index] = permutare_B[index], permutare_B[i]

numar_operatii += 1

return numar_operatii

def main():

# Citim permutările din fișierul text

numar, permutareA, permutareB = citeste_permutari('permutariab.txt')

# Determinăm numărul minim de operații

numar_operatii = numar_minim_operatii(numar, permutareA, permutareB)

# Scriem rezultatul în fișierul text de ieșire

with open('rezultat_permutari.txt', 'w') as file_out:

file_out.write(f"Numărul minim de operații: {numar_operatii}")

if __name__ == "__main__":

main()