Az S. 96. feladat (2015. február)

S. 96. Egy $\displaystyle D$ ($\displaystyle 1\le D\le 10^{15}$) hosszú rudat szeretnénk szétvágni $\displaystyle N$ ($\displaystyle 1\le N \le 500\;000$) db kisebb rúdra. Tudjuk a kisebb rudak hosszát: az $\displaystyle i$-edik hossza $\displaystyle r_i$ ($\displaystyle 1\le r_i\le 10^{15}$) és azt is tudjuk, hogy a kisebb rudak összhossza $\displaystyle D$. Egy $\displaystyle L$ hosszú rúd szétvágása tetszőleges hosszúságú két részre $\displaystyle L$ forint. Egy vágással egyszerre csak egy rudat szabad kettévágni. Daraboljuk föl a lehető legolcsóbban a teljes $\displaystyle D$ hosszú rudat a megadott $\displaystyle r_i$ hosszú részekre.

A program olvassa be a standard input első sorából $\displaystyle N$-et és $\displaystyle D$-t, majd a következő $\displaystyle N$ sorból az $\displaystyle r_i$ egészeket, majd írja a standard output első sorába a minimális pénzt, amennyivel megoldható a szétdarabolás.

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 s96.zip állományban a program forráskódja (s96.pas, s96.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 (s96.txt, s96.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. március 10-én LEJÁRT.

Statisztika:

12 dolgozat érkezett.
10 pontot kapott:	Csenger Géza, Juhász 326 Dániel, Weisz Ambrus, Zalavári Márton, Zarándy Álmos.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2015. februári informatika feladatai