Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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.


Statisztika:

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


A KöMaL 2018. novemberi informatika feladatai