| Fişierul intrare/ieşire: | permutariab.in, permutariab.out | Sursă | FMI No Stress 9 |
| Autor | Bogdan Ioan Popa | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
PermutariAB
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). 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 ieşire
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
- 1 ≤ N ≤ 100.000
- Pentru 70% din punctaj, 1 ≤ N ≤ 1000
Exemplu
| permutariab.in | permutariab.out |
|---|---|
| 6 2 1 3 4 5 6 1 3 4 5 6 2 | 5 |
| 10 1 5 2 3 4 6 9 10 7 8 3 9 5 1 2 7 8 10 4 6 | 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.
