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/S. 34. feladat (2019. március)

I/S. 34. Adott egy \(\displaystyle N\) sorból és \(\displaystyle M\) oszlopból álló sakktábla. A táblán kezdetben elhelyeztünk \(\displaystyle K\) darab sötét bástyát. Ezután szeretnénk feltenni \(\displaystyle Q\) darab kérdést. Egy kérdésben ideiglenesen töröljük az \(\displaystyle x\). sort (vagy oszlopot). Ezután értelemszerűen kapunk egy \(\displaystyle (N-1)\cdot M\) méretű (vagy \(\displaystyle (M-1)\cdot 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 \(\displaystyle N\), \(\displaystyle M\), \(\displaystyle K\), \(\displaystyle Q\) számokat. A következő \(\displaystyle 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ő \(\displaystyle Q\) sor mindegyike tartalmaz egy \(\displaystyle p\) és egy \(\displaystyle x\) számot: ha \(\displaystyle p=1\), akkor az \(\displaystyle x\). sort, ha \(\displaystyle p=2\), akkor az \(\displaystyle 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:

Korlátok: \(\displaystyle 1\le N,M\le {10}^{17}\), \(\displaystyle 0\le K\le \min(N\cdot M,{10}^{5})\), \(\displaystyle 0<Q\le {10}^{5}\). Időlimit: 0,5 mp.

Értékelés: A pontok 20%-a kapható, ha \(\displaystyle N,M\le {10}^{5}\); további 20% kapható, ha \(\displaystyle K,Q\le {10}^{3}\); 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ó.

(10 pont)

A beküldési határidő 2019. április 10-én LEJÁRT.


Statisztika:

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


A KöMaL 2019. márciusi informatika feladatai