Editing 3490 - Permutari AB

== 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 ==
<syntaxhighlight lang="python">
def citeste_permutari():
    nume_fisier = 'permutariabin.txt'
    with open(nume_fisier, 'r') as file:
        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_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()

</syntaxhighlight>