Az S. 157. feladat (2021. december)

S. 157. Álmos és Sára kaptak egy nagy tábla mogyorós csokoládét karácsonyra. A csokoládé \(\displaystyle N\times N\) db négyzet alakú mezőből áll. Egyes mezőkben van mogyoró, más mezőkben nincs. Úgy szeretnék elosztani a csokoládét, hogy a kapott mogyorós részek számának különbsége minél kisebb legyen. Nem szeretnék azonban túl sok részre vágni a csokoládét, így először \(\displaystyle N\) hosszú és egy mező széles sávokra vágják, majd minden sávot középen kettévágnak és az egyik felét Álmos, a másikat Sára kapja (\(\displaystyle N\) páros szám). Azt, hogy ki melyik részt kapja, minden sávra külön-külön eldönthetjük. A sávokra vágást soronként és oszloponként is el lehet végezni, így mindkét lehetőséget meg kell vizsgálni.

Készítsünk programot, amely egy tábla mogyorós csokoládéra megadja, mennyi a legkisebb különbség, ami Álmos és Sára mogyorót tartalmazó mezőinek száma között lehet. Azt is adjuk meg, hogy ehhez soronként vagy oszloponként kell-e felvágni a csokoládét.

Bemenet: az első sor tartalmazza a méretet megadó \(\displaystyle N\) számot. A következő \(\displaystyle N\) sor mindegyike \(\displaystyle N\) számot tartalmaz. Ezek mindegyike 0, ha nincs mogyoró a mezőn és 1, ha van.

Kimenet: az első sorba egy S karakter írjunk, ha a legkisebb különbséget soronkénti felvágással is el lehet érni, különben pedig egy O karaktert. A második sorba az elérhető legkisebb különbség kerüljön.

Példa:

Magyarázat: A csokoládé mindkét felvágással igazságosan elosztható.

Korlátok: \(\displaystyle 2\le N\le 500\), \(\displaystyle N\) páros. Időlimit: 1 mp.

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

Beküldendő egy s157.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ő 2022. január 17-én LEJÁRT.

Statisztika:

8 dolgozat érkezett.
10 pontot kapott:	Sándor Péter, Tóth 057 Bálint.
9 pontot kapott:	Kovács Alex.
3 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2021. decemberi informatika feladatai