Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?
A régi honlapot akarom!!! :-)

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:

BemenetKimenet
3 1 13 1 2
6 2 210 6 4

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.


Statisztika:

Az I/S. 22. feladat értékelése még nem fejeződött be.


A KöMaL 2017. decemberi informatika feladatai