Az I/S. 23. feladat (2018. január)

I/S. 23. Egy \(\displaystyle N\times N\)-es ,,sakktábla'' világos színű mezőin \(\displaystyle S\) számú sötét gyalogot helyezünk el. Feladatunk az, hogy egy világos futó segítségével közülük minél többet leüssünk. A futó a szokásos módon mozoghat a táblán, de irányt váltani csak akkor tud, ha olyan mezőre lép, amelyen éppen leüt egy gyalogot. A futó kezdeti helye nincs rögzítve, azt mi választhatjuk meg.

Készítsünk programot, amely megadja, hogy adott állások esetén legföljebb hány gyalogot lehet a tábláról levenni.

A program standard bemenete az \(\displaystyle N\) és \(\displaystyle S\) egészek, valamint a következő \(\displaystyle S\) sor mindegyikében egy egész számpár. A számpárok a sötét gyalogok helyzetét adják meg: a bal felső (sötét) mezőtől indulva az egyes gyalogok sorát és oszlopát. A program standard kimenete legyen a levehető gyalogok maximális száma.

Magyarázat: a 4 1, 1 4, 3 6 és 5 4 mezőkön lévő gyalogok leütése pl. ebben a sorrendben lehetséges, ha a futó a 4 1 mezőről indul, de sajnos a többi gyaloghoz a futó nem tud eljutni.

Korlátok: \(\displaystyle 4 \le N \le 100\), \(\displaystyle 4 \le S \le 2\cdot N\).

É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 kisebb \(\displaystyle N\) értékek esetén ad helyes eredményt 1 másodpercen belül.

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

(Az októberi számunkban megjelent K. 513. feladat alapján)

(10 pont)

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

A megoldások az összes eset módszeres kipróbálására épültek. A beküldött megoldásokat \(\displaystyle N \le 15\) tesztesetekkel értékeltük, így azok mindenkinél az 1s futásidőn belül maradtak.

A feladat kiírásából nem derült ki, hogy lehetséges-e egy futónak keresztülmennie egy mezőn úgy, hogy az ott lévő gyalogot nem veszi le. Kicsit szokatlan megközelítés, de volt olyan megoldó, aki így értelmezte a feladatot. Mivel a feladat lényege így nem változott, ezért ezt is elfogadtuk. Pl. az egyik mintaként közölt megoldás is ilyen, tehát a két mintamegoldás kimenetei egyes bemenetekre eltérnek.

Mintamegoldásként Ürmössy Dorottya 9. évfolyamos, budapesti versenyző C# nyelvű megoldását(is23ud.cs), valamint Zsombó István 12. évfolyamos, pécsi versenyző Visual Basicben készült munkáját (is23dokuzsi.txt,is23zsi.vb) mutatjuk be.

A tesztesetek a következő tömörített mappából tölthetők le: is23be.zip.

Statisztika:

8 dolgozat érkezett.
10 pontot kapott:	Ürmössy Dorottya, Zsombó István.
8 pontot kapott:	2 versenyző.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.

A KöMaL 2018. januári informatika feladatai