Az S. 83. feladat (2013. október)

S. 83. Van egy N×M-es tábla csokink (N sor, M oszlop), amit szét szeretnénk osztani N×M gyereknek. Mivel ezt igazságosan szeretnénk megtenni, így mindenkinek pontosan egy ,,kocka'' csokit fogunk adni. Ehhez fel kell tördelnünk a tábla csokit. Ezt úgy végezzük, hogy kezdetben letesszük az asztalra, majd egy-egy törés után minden darabot az eredeti helyére teszünk vissza. Minden törésnek van valami költsége: az i-edik és az i+1-edik oszlop közti törés költsége o_i, a j-edik és j+1-edik sor közti törés költsége s_j. Ez azt jelenti, hogy ha van egy csokidarab az asztalon, akkor annak a törése kerül ennyibe. Ezzel az asztalon lévő többi különálló csokidarabon nem törtünk. A törések során minden csokidarab a helyén marad, nem helyezhetjük át oda, ahol olcsóbb lenne törni, egymásra sem tehetjük őket, hogy ,,egyszerre'' törjük. Csak a tábla oldalaival párhuzamos vonal mentén törhetjük a csokit.

A szabályoknak megfelelően minél olcsóbban szeretnénk 1×1-es ,,kockákra'' osztani a csokit. Adja meg a program, hogy mi ez a minimális költség.

A program olvassa be a standard input első sorából M-et és N-et (), majd a következő M-1 sorból az o_i egészeket, végül a következő N-1 sorból az s_i egészeket, és írja a standard output első, és egyetlen sorába a minimális törési összköltséget.

Magyarázat: Ha először a sorok, majd az oszlopok mentén törünk, akkor

s₁+s₂+s₃+4^.(o₁+o₂+o₃+o₄+o₅)=7+4^.11=51

lenne a törési költség. Ennél lehet olcsóbban is.

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.

Részpontszámok a következőkre kaphatóak:

- a program N,M5-re megoldást ad;

- a program N,M50-re megoldást ad;

- a program N,M500-ra megoldást ad;

- a program N,M1000-re megoldást ad.

Beküldendő egy tömörített s83.zip állományban a program forráskódja (s83.pas, s83.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 (s83.txt, s78.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ő 2013. november 11-én LEJÁRT.

Mintamegoldásnak Weisz Ambrus megoldását tesszük közzé. S83main.cpp Illetve a dokumentáció: S83megoldas.txt

Statisztika:

22 dolgozat érkezett.
10 pontot kapott:	Juhász 326 Dániel, Kiss 666 Péter, Kovács-Deák Máté, Makk László, Németh 123 Balázs, Weisz Ambrus, Zalavári Márton.
9 pontot kapott:	Fonyó Viktória, Gercsó Márk, Molnár-Sáska Zoltán, Somogyvári Kristóf, Zarándy Álmos.
6 pontot kapott:	3 versenyző.
5 pontot kapott:	2 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2013. októberi informatika feladatai