Konténer
Egy konténer raktárban N db konténer van egy sorban tárolva. A konténereket el akarják szállítani, ezért mindegyikre rá van írva, hogy melyik városba kell szállítani. A városokat 1-től 3-ig sorszámozzák. A konténereket át kell rendezni úgy, hogy balról jobbra először az 1-essel, majd a 2-essel, végül a 3-assal jelölt konténerek álljanak. A raktár majdnem tele van, csak az utolsó konténer után van egy konténer számára szabad hely. A rendezést a konténerek fölött mozgatható robottal végezhetjük, amely egy lépésben kiemel a helyéről egy konténert és átteszi azt a szabad helyre, ezzel az átmozgatott konténer helye lesz szabad.
Feladat
Írj programot, amely kiszámítja, hogy legkevesebb hány lépésben lehet rendezni a konténersort, majd megadja a rendezést! A rendezés végén a szabad helynek a sor végén kell lennie!
Bemenet
A KONTENER.BE állomány első sorában a konténerek N száma van
$(1\le {\tt N}\le 10000)$. A második sor N egész számot tartalmaz egy-egy szóközzel elválasztva. Az i-edik szám annak a városnak a sorszáma (1 és 3 közötti érték), ahova az i-edik konténert szállítani kell.
Kimenet
A KONTENER.KI állomány első sorába a rendezés végrehajtásához minimálisan szükséges lépések M számát kell írni! A következő M sor tartalmazza a sorrendben végrehajtandó mozgatásokat, soronként egy-egy mozgatást! Minden sorban két egész szám legyen egy szóközzel elválasztva; i és j, ami azt jelenti, hogy a lépés során az i-edik helyen lévő konténert a j-edik helyre kell átmozgatni! A kezdetben üres hely sorszáma N+1.
Példa
|
KONTENER.BE
|
KONTENER.KI
|
12
2 1 2 3 1 3 2 3 2 3 1 2
|
10
9 13
4 9
1 4
5 1
3 5
11 3
6 11
12 6
8 12
13 8
|
Tesztadatok
