3490 - Permutari AB

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

# 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

# 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()