Problem I/S. 47. (October 2020)

I/S. 47. Subscribers can reach the text of the problem after signing in. The text will be public from October 28, 2020.]

(10 pont)

Deadline expired on November 16, 2020.

Sorry, the solution is available only in Hungarian. Google translation

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)\)

Statistics:

11 students sent a solution.
10 points:	Horcsin Bálint, Varga 256 Péter.
9 points:	Kovács Alex.
5 points:	4 students.
4 points:	2 students.
1 point:	1 student.
0 point:	1 student.

Problems in Information Technology of KöMaL, October 2020