Az I/S. 22. feladat (2017. december)

I/S. 22. Egy \(\displaystyle N\) hosszúságú, egységnégyzetekből álló szalagon korongok helyezkednek el. Minden korong egy-egy négyzetben van, ugyanakkor egy négyzetben legföljebb egy korong található, vagy a négyzet üres. A szalag első \(\displaystyle P\) négyzetében piros korongok találhatók, míg utolsó \(\displaystyle K\) négyzetében kékek. Célunk az, hogy a piros, valamint a kék korongokat a szalag tőlük távolabbi végéhez sorakoztassuk föl. Akkor teljesítettük a feladatunkat, ha a szalag első \(\displaystyle K\) számú négyzetében kék, az utolsó \(\displaystyle P\) számú négyzetében piros korong található.

A korongokkal kétféle mozgatást tudunk végezni bármelyik irányba. Az egyik lehetőség, hogy egy koronggal a szomszédos üres négyzetre lépünk. A másik lehetőség, hogy egy koronggal a szomszédos korongon át a következő szomszédos, üres mezőre ugrunk. Több korongot vagy üres négyzetet nem lehet átugrani, de bármelyik korong átugorhatja bármelyik másikat függetlenül a színétől.

Készítsünk programot, amely megadja, hogy legkevesebb hány mozgással teljesíthetjük a célt, amely mindig teljesíthető. A program standard bemenete az \(\displaystyle N\), \(\displaystyle K\) és \(\displaystyle P\) egészek. A program standard kimenete egy sorban a szükséges legkevesebb mozgások, majd azon belül az ugrások és a lépések száma.

Példák:

Korlátok: \(\displaystyle 1 \le P < P+K < N \le 1000\).

Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak \(\displaystyle N\le 10\), \(\displaystyle N\le 30\), \(\displaystyle N\le 100\) értékek esetén ad helyes eredményt 1 másodpercen belül.

Beküldendő egy is22.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.

(10 pont)

A beküldési határidő 2018. január 10-én LEJÁRT.

A feladat megoldása az esetek módszeres kipróbálásával, pl. gárfkereséssel az \(\displaystyle N \le 15\) bemenetekre volt lehetséges.

Mintaként Gáspár Attila miskolci, 12. évfolyamos tanuló munkáját (is22ga.cpp), illetve Ürmössy Dorottya 9. osztályos budapesti versenyző megoldását (is22dokuud, is22ud.cs) adjuk közre.

A helyes kimeneti állomány: is22ki.txt.

Statisztika:

6 dolgozat érkezett.
10 pontot kapott:	Gáspár Attila, Horcsin Bálint, Ürmössy Dorottya.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2017. decemberi informatika feladatai