ACM 1997

döntő



Táblázat követése ("G" probléma)
A táblázat adatait cellákban tároljuk, amelyeket sor-(r) és oszlopszámuk (c) azonosít. Néhány művelet egyetlen cellát (r,c) érint, míg mások egész sorokat és oszlopokat. Jellemző művelet sorok és oszlopok beszúrása, törlése, cellák tartalmának cseréje.

Néhány táblázatban lehetővé teszik a felhasználóknak, hogy sorok vagy oszlopok csoportját megjelöljék törlésre, majd a műveletet egyszerre hajtják végre. A szokatlan táblázatokban mód van arra, hogy megjelöljük, mely sorok, illetve oszlopok elé szúrunk be újabbat. Tegyük fel például, hogy a felhasználó a táblázat 1. és 5. sorát jelöli ki törlésre. A táblázat ekkor összezsugorodik.
 

Ha a felhasználó ezután törlésre jelöli a 3., 6., 7. és 9. oszlopokat, az alábbinak megfelelően változik a táblázat.
 

A felhasználó megjelöli a 2., 3. és 5. sorokat a beszúrásra, melynek hatására a táblázat megnő. Ha megjelöli a 3. oszlop beszúrását, a táblázat tovább növekszik. Végül felcseréljük az (1,2) és a (6,5) cellák értékét. Az alábbiakban rendre ezen változtatások hatása látszik.
 

Írj, a táblázat változásait nyomonkövető programot, amely megadja a sor és oszlopműveletek, cserék eredményeként létrejött táblázatot.
 

Be- és kimenet:

A bemenet tartalmazza a táblázatot, az azon végzett műveleteket, és a rá vonatkozó kérdéseket. Minden táblázatdefiníció a sorok (r) és oszlopok (c) számát megadó számpárral kezdődik, ezt követően pedig egy egész szám (n) megadja a rajta végrehajtott műveletek számát. A sorok és oszlopok számozása 1-től kezdődik.

Két cella, az (r1,c1) és az (r2.c2) cellák tartalmának cseréje:

EX r1 c1 r2 c2
A négy beszúró és törlő parancs a következő: DR (sortörlés), DC (oszloptörlés), IR (sorbeszúrás), IC (oszlopbeszúrás):
<command>: A x1 x2 ... xA
Ahol a <command> a fenti négy parancs egyike, A pozitív egész, 10-nél kisebb, x1 x2 ... xA a beszúrásra vagy törlésre kerülő sorok, illetve oszlopok számai.A törlésre vagy beszúrásra kerülő sorok sorrendje nem számít. Adott törlő vagy beszúró utasításon belül a számok nem ismétlődnek. A bemeneti állomány a táblázat méretét megadó helyen álló 0 0 értékpárral zárul.

A végrehajtásra kerülő műveleteket a táblázatra vonatkozó kérdések száma követi. Minden kérdés két egész számot, a sor (r) és az oszlop (c) számát tartalmazza az eredeti táblázatban. Minden kérdésre a megadott cell végállapotbeli helyét kell megadni, vagy a GONE szót, ha a cella törlésre került. Több táblázatot tartalmazó bemenet esetén a kimenetben az egyes táblázatokat üres sorral kell elválasztani.

Példa:
 
INPUT.TXT OUTPUT.TXT
7 9
5
DR   2  1 5
DC  4  3 6 7 9
IC  1  3
IR  2  2 4
EX 1 2 6 5
4
4 8
5 5
7 8
6 5
0 0
Spreadsheet #1
Cell data in (4,8) moved to (4,6)
Cell data in (5,5) GONE
Cell data in (7,8) moved to (7,6)
Cell data in (6,5) moved to (1,2)