Az I. 466. feladat (2018. november)

I. 466. A mérgezett csoki egy nagyon egyszerűen leírható kétszemélyes játék. A játékosok felváltva ,,törnek'' a táblából és az veszít, akinek a végén csak a mérgezett kocka marad. Ismert, hogy a kezdőnek van nyerő stratégiája, de az csak az $\displaystyle N\times N$ és a $\displaystyle 2\times N$ méretű tábla esetén fogalmazható meg egyszerűen, más méretű táblát használva a játék valós izgalmat hordoz.

A játékról bővebben például a http://web.cs.elte.hu/szakdolg/ghorvath.pdf címen elérhető diplomamunkában olvashatunk.

Ebben a feladatban a következő formában játszunk:

$\displaystyle \bullet$ a csokoládétábla $\displaystyle N$ sorból és $\displaystyle M$ oszlopból áll;

$\displaystyle \bullet$ az egyes csokoládékockákat két egész számmal azonosítjuk;

$\displaystyle \bullet$ a mérgezett csokoládékocka az $\displaystyle (M, N)$ számpárral adható meg;

$\displaystyle \bullet$ a táblából minden lépésben legalább egy kockát törünk le. A törést minden esetben a teljes csokoládétábla $\displaystyle (1,1)$ sarkával ,,szemközti'' $\displaystyle (i,j)$ számpárral adjuk meg. Ekkor minden, még meglévő $\displaystyle (x,y)$ csokoládékockát elveszünk, amelyre $\displaystyle x\le i$ és $\displaystyle y\le j$.

A játékosok dokumentálni szerették volna a játékot, ezért a soron következő lépést egy kártyalapra írták, majd a másik játékos előző lépését tartalmazó lapra helyezték. Ez a módszer sajnos nem volt jó, mert egy ajtónyitáskor keletkező huzat a kártyákat lesodorta az asztalról és azok összekeveredtek. Készítsünk programot, amely a kártyákat egy lehetséges törési sorrendbe állítja és megadja, hogy a meghatározott sorrend esetén az egyes versenyzőkhöz hány csokoládékocka került.

A program standard bemenetének első sorában a csokoládétábla mérete, az oszlopok és a sorok száma, azaz $\displaystyle M$ és $\displaystyle N$, valamint a kártyalapok K száma található. A következő $\displaystyle K$ sorban az egyes kártyákon szereplő oszlop, sor értékpárok szerepelnek. A kimenet első sorában $\displaystyle K$ egész szám szerepel: a töréseket leíró kártyák egy lehetséges sorrendje. A második sorban ezen sorrend esetén az első, illetve a második játékos által letört kockák száma. Az elválasztó karakter minden esetben a szóköz. A bemenetben egyetlen szám értéke sem nagyobb 1000-nél.

Beküldendő egy i466.zip tömörített állományban a program forráskódja és a működéséhez szükséges egyéb fájlok, továbbá a hozzá kapcsolódó dokumentáció. Utóbbi világítson rá a problémamegoldás lényeges elemeire, valamint tartalmazza, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

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

A feladatra 5 különböző nyelven érkezett megoldás. A legnépszerűbb a C# volt, 4 megoldó használta. Érkezett C, C++, VB és Java nyelvű megoldás is.

Meglepően kevés tökéletes megoldás született. Két algoritmussal lehetett nagyobb méretű tesztesetekre működő megoldást megadni. Ha csak a helyes törési sorrend kialakítását vesszük alapul, akkor az egyik elgondolás szerint rendezni kell az egyik, azon belül pedig a másik koordináta szerint. Időigénye a törési pontok számától és a rendezési algoritmustól függ. Egy másik módszer a táblán bejelöli a törési pontokat, majd megkeresi azokat. Ennek időigénye a legrosszabb esetben csokoládétábla méretével arányos.

Az egyik hibátlan megoldást beadó versenyző, Ürmössy Dorottya utóbbi elven dolgozott, leírása szerint:

1. Az adatokból egy N*M-es matrixot állítok elő, ahol minden elem 1 értékű, kivétel azokat a pontokat, ahol törés volt. Ezeken a pontokon a törés száma lesz az érték, negatív előjellel.

2. Az 1,1 pontból indulva a sorokon illetve oszlopokon végigpáztázva keresem a 0-nál kissebb elemeket. Ha ilyet találok, akkor annak értékét (pozitív előjellel) kiírom, illetve a tőle kisebb sor és oszlopszámú elemek értékeit összegzem, és közben 0-ra állítom. Az összegeket az első vagy második játékos által gyűjtött értékekhez adom, attól függően, hogy páros vagy páratlan sorszámú a találat.

3. A 2-es pontot addig ismétlem, amíg az összes töréspontot meg nem találom.

Megoldása: i466urmossy.cs

A program teszteléséhez 8 tesztesetet használtunk, 1-1 pontot érően. (Csak a teljesen hibátlan kimenetért járt pont.) Az alábbiakban: 1: a mintaként megadott, 2: egyetlen törést tartalmazó, 3: bármely törési sorrend jó, 4: 2xN méretű a csoki, 5: a teljes csokoládé elfogy, 6: közepes méretű, nagyságrendileg az oldalhosszal egyező töréssel, 7: maximális méretű tábla, mérethez képest kevés töréssel, 8: maximális méretű tábla, a feladatban megengedett maximális számú töréssel.

A tesztesetek: i466bemenet.zip

Statisztika:

9 dolgozat érkezett.
10 pontot kapott:	Nagy 793 Márton, Ürmössy Dorottya.
9 pontot kapott:	Papp Marcell Miklós, Zámborszky Balázs.
6 pontot kapott:	2 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.

A KöMaL 2018. novemberi informatika feladatai