Az S. 91. feladat (2014. szeptember) |
S. 91. Anna, Béla és Cili kapnak N (1≤N≤60) ajándékcsomagot. Mindegyik csomagnak tudják az értékét: az i-edik csomag értéke ai, ahol 1≤ai≤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 N-et, majd a következő N sorból az ai 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 ai≤40-re megoldást ad;
- a program N≤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. 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 D[A][B][k]=D[A−e[k]][B][k−1] vagy D[A][B−e[k]][k−1] vagy 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 A, B, és S−A−B értékek maximumának minimuma, ahol S az ajándékok összege. A megoldás lépészáma: O(n∗S2). Tovább javítható ez, ha észrevesszük, hogy elég csak azt az esetet vizsgálni, amikor 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