Az S. 91. feladat (2014. szeptember)

S. 91. Anna, Béla és Cili kapnak \(\displaystyle N\) (\(\displaystyle 1\le N\le 60\)) ajándékcsomagot. Mindegyik csomagnak tudják az értékét: az \(\displaystyle i\)-edik csomag értéke \(\displaystyle a_i\), ahol \(\displaystyle 1\le a_i\le 100\). El szeretnék osztani egymás között az ajándékokat a lehető legigazságosabban. A legigazságosabb elosztás akkor valósul meg, ha a legnagyobb összértékű csomagokat kapó testvér a lehető legkisebb összértéket kapja. Például, ha a következő csomagokat kapták: 2 4 5 8 9 14 15 20, akkor egy ilyen legigazságosabb szétosztás a következő lehet: Anna: 2 9 15, összesen 26; Béla: 4 8 14, összesen 26; Cili: 5 20, összesen 25. Adjuk meg egy legigazságosabb elosztásban szereplő legnagyobb összértéket (aminek tehát a lehető legkisebbnek kell lennie).

A program olvassa be a standard input első sorából \(\displaystyle N\)-et, majd a következő \(\displaystyle N\) sorból az \(\displaystyle a_i\) szóközzel elválasztott egészeket. Írja a standard output első és egyetlen sorába a szétosztásban a legnagyobb értéket.

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 \(\displaystyle a_i\le 40\)-re megoldást ad;

- a program \(\displaystyle N\le 10\)-re megoldást ad.

Beküldendő egy tömörített s91.zip állományban a program forráskódja (s91.pas, s91.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 (s91.txt, s91.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ő 2014. október 10-én LEJÁRT.

A feladatot dinamikus programozással oldhatjuk meg. \(\displaystyle D[A][B][k]\) legyen true, ha el tudjuk osztani úgy az első, második, .., k. ajándékokat, úgy, hogy az első Anna A értékűt kap, Béla B értékűt, és Cili a maradékot. Legyen false, ha nem lehet. Ezt meg tudjuk határozni, hiszen \(\displaystyle D[A][B][k]=D[A-e[k]][B][k-1]\) vagy \(\displaystyle D[A][B-e[k]][k-1]\) vagy \(\displaystyle D[A][B][k-1]\). Attól függően, hogy az utolsó ajándékot kinek adjuk. Innen persze a true értékek közül kell kiválasztani a legjobbat, ami az \(\displaystyle A\), \(\displaystyle B\), és \(\displaystyle S-A-B\) értékek maximumának minimuma, ahol \(\displaystyle S\) az ajándékok összege. A megoldás lépészáma: \(\displaystyle O(n*S^2)\). Tovább javítható ez, ha észrevesszük, hogy elég csak azt az esetet vizsgálni, amikor \(\displaystyle A<=B<=C\).

Statisztika:

22 dolgozat érkezett.
10 pontot kapott:	Erdős Márton, Fuisz Gábor, Molnár-Sáska Zoltán, Németh 123 Balázs, Zalavári Márton.
9 pontot kapott:	Kiss Gergely.
8 pontot kapott:	2 versenyző.
7 pontot kapott:	4 versenyző.
6 pontot kapott:	2 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2014. szeptemberi informatika feladatai