Fişierul intrare/ieşire:permutariab.in, permutariab.outSursăFMI No Stress 9
AutorBogdan Ioan PopaAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.25 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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.inpermutariab.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?