Programozás‎ > ‎Feladatok‎ > ‎

Könyvtári pakolás

Egy könyvtár polcán egy sorban N darab könyv van, de nem a kívánt sorrendben. A könyvtáros minden könyvre ráragasztott egy cetlit, amire ráírta, hogy a helyes sorrendben hányadik helyen kell majd lennie. A kívánt sorrend kialakítását párok cseréjével akarja megvalósítani. 

Feladat

Készíts programot, amely kiszámítja, hogy legkevesebb hány cserével lehet kialakítani a kívánt sorrendet!

Bemenet

A pakol.be szöveges állomány első sorában a könyvek N (2<=N<=30000) száma van. A második sor pontosan N különböző pozitív egész számot tartalmaz egy-egy szóközzel elválasztva, az i-edik szám értéke az i-edik könyv helyes sorrendbeli sorszáma.

Kimenet

A pakol.ki szöveges állomány első és egyetlen sora egy egész számot tartalmazzon, azt a legkisebb M számot, amire a bemenetben megadott könyvsorozat M számú cserével a kívánt sorrendbe rakható!

Példa

Bemenet  Kimenet
10
7 10 1 3 2 8 4 9 6 5
7


Tesztadatok

Címkék

A feladat forrása: NTOITV 2012 2. forduló, 9-10. évfolyam
Algoritmusok: 

megoldás