Programozás‎ > ‎Feladatok‎ > ‎

Párosítás

Egy raktárból N boltba kell kiszállítani ládákba csomagolt árut. Minden boltba pontosan két ládát kell vinni. A ládák az előkészítés időrendi sorrendjében egymás mellett egy sorban vannak, mindegyikre ráragasztva annak a boltnak a sorszáma, ahova szállítani kell. A raktárosnak át kell rendezni a ládák sorrendjét, hogy az egy boltba kerülő ládák egymás mellett legyenek. Az átrendezés során egy lépésben két láda helyét cserélheti meg.

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 parosit.be szöveges állomány első sorában a boltok N (2<=N<=20000) száma van. A második sor pontosan 2N pozitív egész számot tartalmaz egy-egy szóközzel elválasztva, az 1,…,N számok mindegyike pontosan kétszer fordul elő a sorban.

Kimenet

A parosit.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 ládasor M számú cserével a kívánt sorrendbe rakható!

Példa

Bemenet  Kimenet
4
1 3 2 1 3 4 4 2
3

4
3 2 1 4 2 3 1 4
2

Tesztadatok

Címkék

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

megoldás