Az S. 94. feladat (2014. december)

S. 94. Egy állatkísérlet során a kutatók arra lettek figyelmesek, hogy ha túl sok állat léphet egymással kapcsolatba, akkor pontatlan lesz a kísérlet. Jelenleg egy \(\displaystyle N\times N\)-es négyzet alakú mezőn (\(\displaystyle 2\le N\le 17\)) túl sok állat tartózkodik. Szeretnénk \(\displaystyle K\) darab (\(\displaystyle 1\le K\le 2N-2\)) kerítést építeni nekik, hogy el legyenek különítve. Egy kerítés párhuzamos a mező valamelyik szélével, és attól egész távolságra halad. Továbbá a teljes négyzeten keresztül kell haladnia (azaz nem lehet vége egy kerítésnek a négyzet belsejében). Ilyen feltételek mellett szeretnénk minimalizálni az összefüggő részeken lévő állatok maximális számát.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle K\)-t (\(\displaystyle 2\le N\le 17\), \(\displaystyle 1\le K\le 2N-2\)), majd a következő \(\displaystyle N\) sorból soronként \(\displaystyle N\) egész számot, melyek jelentése: az adott sorban az adott egységnégyzetben ennyi állat tartózkodik. Írjuk a standard output első és egyetlen sorába a lehető legjobb kerítésépítés mellett a legtöbb állat számát, melyek egymástól nincsenek elkerítve.

Magyarázat: Két kerítést kell építenünk, méghozzá a 2. és 3. oszlop, és a 2. és 3. sor között érdemes. Ekkor a bal felső részben \(\displaystyle 1+1+1+1=4\) állat lesz, a jobb felsőben \(\displaystyle 2+2=4\), a bal alsóban is \(\displaystyle 2+2=4\), és a jobb alsóban is 4 állat lesz, így 4-et írunk ki.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s94.zip állományban a program forráskódja (s94.pas, s94.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s94.txt, s94.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2015. január 12-én LEJÁRT.

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Gáspár Attila.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
2 pontot kapott:	3 versenyző.

A KöMaL 2014. decemberi informatika feladatai