Loading [MathJax]/jax/output/HTML-CSS/jax.js
Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 91. feladat (2014. szeptember)

S. 91. Anna, Béla és Cili kapnak N (1N60) ajándékcsomagot. Mindegyik csomagnak tudják az értékét: az i-edik csomag értéke ai, ahol 1ai100. 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 ai40-re megoldást ad;

- a program N10-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[Ae[k]][B][k1] vagy D[A][Be[k]][k1] vagy D[A][B][k1]. 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 SAB értékek maximumának minimuma, ahol S az ajándékok összege. A megoldás lépészáma: O(nS2). 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