Feladat: I/S.34 Korcsoport: - Nehézségi fok: -
Füzet: 2019/március, 167 - 168. 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.

Adott egy N sorból és M oszlopból álló sakktábla. A táblán kezdetben elhelyeztünk K darab sötét bástyát. Ezután szeretnénk feltenni Q darab kérdést. Egy kérdésben ideiglenesen töröljük az x. sort (vagy oszlopot). Ezután értelemszerűen kapunk egy (N-1)⋅M méretű (vagy (M-1)⋅N méretű) táblát. Adjuk meg, hogy ezen a kisebb táblán legfeljebb hány világos bástyát lehet elhelyezni úgy, hogy a világosak ne üssék egymást, valamint sötét se üssön világosat (a sötét bástyák üthetik egymást). Két bástya üti egymást, ha azonos sorban vagy oszlopban vannak. Két bástya nem foglalhat el azonos mezőt a táblán. Egy kérdés után a sakktábla visszaáll eredeti állapotába, vagyis a törlés csak ideiglenes. Az oszlopokat és sorokat is 0-tól indexeljük.
Bemenet: az első sor tartalmazza az N, M, K, Q számokat. A következő K sorban a sötét bástyák helyzete van megadva, minden sorban az első szám a sorindexet, a második az oszlopindexet határozza meg. A következő Q sor mindegyike tartalmaz egy p és egy x számot: ha p=1, akkor az x. sort, ha p=2, akkor az x. oszlopot töröljük.
Kimenet: adjuk meg minden kérdésre, hogy legfeljebb hány világos bástyát lehet elhelyezni. A kimenet elemeit szóközzel tagoljuk és sorvége jellel zárjuk.
Példa:

 
Bemenet  (a /  jel sortörést helyettesít)Kimenet   10 10 13 55 4 4 4 4   1 1 / 1 8 / 1 2 / 4 4 / 3 4 / 5 1 / 5 8 / 5 98 2 / 8 4 / 8 9 / 8 6 / 9 42 4 / 2 8 / 1 1 / 1 8 / 1 2
 

Korlátok: 1≤N,M≤1017, 0≤K≤min(N⋅M,105), 0<Q≤105. Időlimit: 0,5 mp.
Értékelés: A pontok 20%-a kapható, ha N,M≤105; további 20% kapható, ha K,Q≤103; további 60% kapható az eredeti korlátokra.
Beküldendő egy is34.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztő környezetben futtatható.