3490 - Permutari AB: Diferență între versiuni

De la Universitas MediaWiki
(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...)
 
Fără descriere a modificării
Linia 1: Linia 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()

Versiunea de la data 2 ianuarie 2024 11:51

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.

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.

Restricții și precizări

1 ≤ N ≤ 100.000

Pentru 70% din teste, 1 ≤ N ≤ 1000

Exemplu 1

permutariabin.txt

6

2 1 3 4 5 6

1 3 4 5 6 2

permutariabout.txt

5

Exemplu 2:

permutariabin.txt

10

1 5 2 3 4 6 9 10 7 8

3 9 5 1 2 7 8 10 4 6

permutariabout.txt

17

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.

Rezolvare

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

def numar_minim_operatii(n, permutare_A, permutare_B):
    numar_operatii = 0
    for i in range(n - 1):
        if permutare_B[i] != permutare_A[i]:
            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():
    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")

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

   

Adus de la „http://wiki.universitas.ro/index.php?title=3490_-_Permutari_AB&oldid=8754”