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 |