Problem S. 96. (February 2015)
S. 96. A beam of length \(\displaystyle D\) (\(\displaystyle 1\le D\le 10^{15}\)) should be cut into \(\displaystyle N\) pieces (\(\displaystyle 1\le N \le 500\;000\)). The length of the \(\displaystyle i\)th piece should be \(\displaystyle r_i\) (\(\displaystyle 1\le r_i\le 10^{15}\)), and the sum of these \(\displaystyle r_i\) numbers is \(\displaystyle D\). The cost of cutting any beam of length \(\displaystyle L\) into two arbitrary pieces is \(\displaystyle L\) units of money. We always cut one piece into two smaller pieces at a time. Your task is to cut the original beam of length \(\displaystyle D\) into smaller pieces with length \(\displaystyle r_i\) so that the total cost is minimal.
Your program reads the values of \(\displaystyle N\) and \(\displaystyle D\) from the first line of the standard input, then the \(\displaystyle r_i\) integers from the following \(\displaystyle N\) lines. The first line of the standard output should contain the minimum sum necessary to complete the cutting process.
In the ``Példa bemenet'' sample input the \(\displaystyle r_i\) integers are listed in one line, and the minimum cost is given in the ``Példa kimenet'' sample output.
Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any arbitrary valid input within 1 second of running time.
The source code (s96.pas, s96.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s96.txt, s96.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file s96.zip.
(10 pont)
Deadline expired on March 10, 2015.
Statistics:
12 students sent a solution. 10 points: Csenger Géza, Juhász 326 Dániel, Weisz Ambrus, Zalavári Márton, Zarándy Álmos. 4 points: 1 student. 3 points: 3 students. 2 points: 1 student. 1 point: 1 student. 0 point: 1 student.
Problems in Information Technology of KöMaL, February 2015