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