Školsko natjecanje iz informatike 2018. / Druga podskupina (3. i 4. razred) - 3. zadatak

N-permutacijom nazivamo niz od \(N\) brojeva iz skupa \({1, 2, …, N}\) od kojih se svaki u nizu javlja točno jednom.

Nad \(N\)-permutacijom možemo proizvoljan broj puta vršiti sljedeću transformaciju: odaberemo prirodan broj \(K\) iz skupa \({2, 3, …, N, N+1}\) i potom svaki element permutacije manji od \(K\) promijenimo iz \(X\) u \(K – X\). Sve promjene unutar jedne transformacije činimo istodobno. Npr. odaberemo li \(K = 6\), broj \(1\) promijenit će se u \(5\), broj \(2\) promijenit će se se u \(4\), broj \(3\) promijenit će se u \(3\) (dakle ostat će isti), broj \(4\) promijenit će se u \(2\), a broj \(5\) promijenit će se u \(1\). Napišite program koji za dvije zadane \(N\)-permutacije \(A\) i \(B\) računa najmanji broj transformacija kojima možemo niz \(A\) transformirati u niz \(B\).

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj \(N\) \((2 ≤ N ≤ 8)\).

U drugom retku nalazi se permutacija \(A\) kao niz od \(N\) prirodnih brojeva iz skupa \({1, 2, …, N}\) od kojih se svaki javlja točno jednom.

U trećem retku nalazi se permutacija \(B\) u istom formatu. Permutacije \(A\) i \(B\) neće biti jednake.

IZLAZNI PODATCI

Ispišite traženi minimalan broj transformacija.

PRIMJERI TEST PODATAKA

Ulaz

3
3 1 2
1 3 2

Izlaz

1

Pojašnjenje prvog primjera: Odabiremo \(K\) = 4.

Ulaz

4
4 3 2 1
2 1 4 3

Izlaz

3

Pojašnjenje drugog primjera: Odabiremo \(K\) = 3 i permutacija postaje (4, 3, 1, 2). Odabiremo \(K\) = 5 i permutacija postaje (1, 2, 4, 3). Odabiremo \(K\) = 3 i permutacija postaje (2, 1, 4, 3).