 |
Az S. 57. feladat (2010. november) |
S. 57. Egy sakktáblát szeretnénk lefedni (hézagmentesen és átfedések nélkül) dominókkal úgy, hogy a tábla bizonyos mezőit kizártuk (a kizárt mezőkre nem kerülhet dominó).
Készítsünk programot, amely a standard bemenetről beolvassa a tábla méretét, valamint a kizárt mezőket, és kiszámít egy megfelelő lefedést, amennyiben létezik.
A bemenet szerkezete a következő: Az első sorban két, szóközzel elválasztott egész szám, a tábla mérete (1
N100), és a kizárt mezők (0MN.N) száma található. A következő M sor mindegyikében, szóközzel elválasztva, egy-egy kizárt mező sor és oszlop koordinátái szerepelnek (1I,JN).
Ha létezik megfelelő lefedés, akkor a standard kimenetre írjunk ki N sort, amelyek mindegyikében N szám található. Az i. sor j. száma a sakktábla i. sorának j. mezőjét lefedő dominó sorszáma, ha az adott mező nem kizárt, egyébként 0. A dominók sorszámozása tetszőleges (különböző dominók különböző sorszámot kell, hogy kapjanak). Ha nem létezik megfelelő lefedés, akkor a ,,nem fedhető le'' szöveget írjuk ki. A futási időlimit tesztesetenként 10 másodperc.
Beküldendő a feladat megoldását tartalmazó forrás és projektállományok (az .exe és más a fordító által generált kiegészítő állományok nélkül), valamint a megoldás menetét röviden bemutató dokumentáció egy s57.zip tömörített mappában.
Értékelés: 8 pont szerezhető az olyan programmal, ami bármilyen (a fenti feltételeknek megfelelő) tesztesetet képes megoldani (ha a futásidő túllépi a 10 mp-t, akkor úgy tekintjük, hogy nem tudta megoldani az adott tesztesetet). A legföljebb 10×10-es táblákat megoldó program 5 pontot ér. További 2 pont szerezhető a dokumentációval.
Tesztesetek és kimeneteik a feladathoz: s57teszt.zip
(10 pont)
A beküldési határidő 2010. december 10-én LEJÁRT.
A bemenetet felfoghatjuk egy gráfnak, ahol a csúcsok a sakktábla nem kizárt mezői, és a szomszédos mezőknek megfelelő csúcsok vannak éllel összekötve. Jól látható, hogy páros gráfot kaptunk, hiszen csak ellentétes színű mezőket kötöttünk össze. Egy dominó megfelel a gráf egy élének, egy dominóhalmaz pedig megfelel egy párosításnak a gráfban, mert az a feltétel, hogy nem lehet a párosításban két olyan él, aminek van közös pontja, megfelel annak a feltételnek, hogy nem fedhetnek át a dominók. Egy hézagmentes lefedés megfelel egy teljes párosításnak. Teljes párosítást kereshetünk pl. a Magyar Módszer nevű algoritmussal. Ennek a megoldásnak a bemutatására Nagy Róbert 10. osztályos budapesti tanuló megoldását tesszük közzé.
Többen backtrack-kel próbálták megoldani a feladatot. Ezek a megoldások nagy tesztesetekre nem mindig futottak le időben. Ennek ellenére, ügyes optimalizációkkal 9 pontot is el lehetett így érni. Ez a megoldás Nagy Miklós 12. osztályos győri versenyzőnek sikerült a legjobban.
Statisztika:
7 dolgozat érkezett. 10 pontot kapott: Jules Pondard, Nagy Róbert. 9 pontot kapott: Barta 111 János, Borsos 607 Zalán, Nagy 111 Miklós. 5 pontot kapott: 1 versenyző. 4 pontot kapott: 1 versenyző.
A KöMaL 2010. novemberi informatika feladatai