Az I/S. 47. feladat (2020. október)

I/S. 47. Adél és Bence a következő játékot játsszák: Adél rajzol egy $\displaystyle N$ szélességű és $\displaystyle N$ magasságú egységoldalú négyzetekből álló négyzethálót, majd minden mezőbe beír egy egész számot. Ezután Bence választ egy $\displaystyle K$ pozitív egész számot, és rajzol egy $\displaystyle 3\cdot 3$ db, $\displaystyle K$ oldalhosszú négyzetekből álló hálót úgy, hogy $\displaystyle 3K\le N$ legyen. Ezután a saját $\displaystyle K$ oldalú négyzetei közül kiszínez tetszőlegesen $\displaystyle X$ darabot ($\displaystyle 1\le X\le 9)$, majd a saját mintáját ráilleszti a számozott négyzetrácsra úgy, hogy szélei a rácsvonalakra illeszkedjenek és a minta ne lógjon le a négyzetrácsról. Bence pontszáma a színezett terület által lefedett mezőkben lévő számok összege. Adjuk meg, hogy legföljebb hány pontot szerezhet Bence.

Bemenet: az első sor tartalmazza az $\displaystyle N$ számot. A következő $\displaystyle N$ sor mindegyike $\displaystyle N$ számot tartalmaz, a mezőkbe írt számokat. Az $\displaystyle i$-edik sor $\displaystyle j$-edik eleme $\displaystyle A_{i,j}$.

Kimenet: az elérhető legnagyobb pontszám.

Példa:

Korlátok: $\displaystyle 3\le N\le 100$, $\displaystyle -1000\le A_{i,j}\le 1000$, Adél biztosan írt nemnegatív számot. Időkorlát: 0,5 mp.

Értékelés: a pontok 50%-a kapható, ha $\displaystyle N\le 10$.

Beküldendő egy is47.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ői környezetben futtatható.

(10 pont)

A beküldési határidő 2020. november 16-án LEJÁRT.

Minden $\displaystyle i$, $\displaystyle j$, $\displaystyle K$ számhármasra megnézzük, hogyha $\displaystyle i$ az egyik, $\displaystyle j$ a másik koordinátája a bal felső saroknak, és a kis négyzetek oldala $\displaystyle K$, akkor mi a legjobb kiválasztás. Látható, hogy a $\displaystyle 3*3$ négyzet közül azokat kell kiválasztani, melyekben az összeg pozitív. Ezek közül a számítások közül kell a maximumot megkeresni.

Egy résztáblázatban (négyzetben) lévő számok összegének számítása $\displaystyle O(N^2)$-ről $\displaystyle O(1)$-re gyorsítható, ha minden mezőre eltároljuk a tőle balra felfelé lévő mezők összegét.

Komplexitás: $\displaystyle O(N^3)$

Statisztika:

11 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Varga 256 Péter.
9 pontot kapott:	Kovács Alex.
5 pontot kapott:	4 versenyző.
4 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2020. októberi informatika feladatai