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>