Feladat: I.466 Korcsoport: - Nehézségi fok: -
Füzet: 2018/november, 483 - 484. oldal  PDF  |  MathML 

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

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 N×N és a 2×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

címen elérhető diplomamunkában olvashatunk.
Ebben a feladatban a következő formában játszunk:
•a csokoládétábla N sorból és M oszlopból áll;
•az egyes csokoládékockákat két egész számmal azonosítjuk;
•a mérgezett csokoládékocka az (M,N) számpárral adható meg;
•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 (1,1) sarkával ,,szemközti'' (i,j) számpárral adjuk meg. Ekkor minden, még meglévő (x,y) csokoládékockát elveszünk, amelyre x≤i és y≤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 M és N, valamint a kártyalapok K száma található. A következő K sorban az egyes kártyákon szereplő oszlop, sor értékpárok szerepelnek. A kimenet első sorában 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.
 
Példa bemenet  (a /  jel sortörést helyettesít)Példa kimenet   10 12 3   2 3 1   7 10 / 5 4 / 3 858 12   
 

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ó.