Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 72. feladat (2012. május)

S. 72. Egy repülőtéren a leszálló gépek utasainak csomagjait több átrakodás után végül futószalagra pakolják. A pakolás eredményeként egy adott utas több csomagja általában nem egymás mellé kerül, hanem szétszóródik. Ez azonban nem szerencsés, az utasok szívesebben veszik, ha csomagjaik egy csoportban érkeznek meg hozzájuk a szalagon. Feladatunk az, hogy minden utasnál a hozzá tartozó csomagokat egymás mellé helyezzük úgy, hogy a lehető legkevesebb legyen a csomagok mozgatásának összes távolsága.

A futószalag egyforma hosszúságú szakaszokra van bontva. Egy-egy szakaszba pontosan egy csomagot tesznek, vagy üresen hagyják. A szakaszméret úgy lett meghatározva, hogy minden csomag elférjen egy szakaszban. Egy repülőgépen legföljebb 25 utas repül, mindenki legföljebb 40 csomagot vihet magával. A futószalag egy adott repülőgép utasai számára 1000 szakaszból áll. Egy mozgatás hosszán a végső és a kiindulási szakasz sorszámának különbségét értjük, tehát a példában szereplő 9. t-jelű csomag átpakolása az 5. helyre 4 hosszúságú mozgatás.

Készítsünk programot, amely a standard bemenet első sorából beolvassa a futószalag hosszát, a következő sorából a futószalag szakaszainak tartalmát, majd a fentieknek megfelelően a lehető legkevesebb mozgatással átrendezi a szalagot. A program a standard kimenet első sorába írja a szükséges mozgatások összes hosszát, a második sorába az átrendezett futószalagot. A szalagon az üres szakaszokat kötőjelek (-), míg az egy utashoz tartozó csomagokat az angol abc kisbetűi jelzik. A be- és kimenet a szalag még csomagokkal megrakott részét tartalmazza.

Beküldendő egy tömörített s72.zip állományban a program forráskódja (s72.pas, s72.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s72.txt, s72.pdf, ...), amelytartalmazza a megoldás rövid leírását, és megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2012. június 11-én LEJÁRT.


Statisztika:

3 dolgozat érkezett.
5 pontot kapott:1 versenyző.
3 pontot kapott:1 versenyző.
2 pontot kapott:1 versenyző.

A KöMaL 2012. májusi informatika feladatai