Problem S. 83. (October 2013)
S. 83. A chocolate bar having N rows, M columns and consisting of identical smaller squares is to be distributed among NM children in a way that everybody gets exactly one square: the chocolate bar lying on the table should be broken into pieces. After we break the bar along a row or a column, the pieces are put back into their original position. However, there is a cost for each breaking: the cost for breaking the chocolate between column i and column i+1 is oi, while the cost for breaking between row j and row j+1 is sj. This rule applies to each individual piece on the table; breaking other separate pieces later (even along the same row or column) will again have the appropriate cost. During the breaking process, every piece stays at their original position, they should not be moved away so that the cost would be less, or should not be stacked on top of each other so that they would be broken simultaneously. Each breaking should take place parallel to the sides of the chocolate bar.
Your program should give the minimal cost for breaking the chocolate into 1x1 squares according to the above rules.
Your program should read the values of M and N (M,N500.000) from the first line of the standard input, then the oi integers from the next M-1 lines, finally, the si integers from the last N-1 lines. The minimal cost should appear in the first (and only) line of the standard output.
The example shows a sample input (``Példa bemenet'') and the corresponding output (``Példa kimenet''). Explanation: breaking the chocolate bar first along the rows then along the columns, the cost would be s1+s2+s3+4.(o1+o2+o3+o4+o5)=7+4.11=51, but this is not optimal.
Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution; 9 further points can be obtained provided that your program solves any arbitrary valid input within 1 second of running time.
Partial points can be obtained according to the following:
- your program yields a solution for M,N5,
- your program yields a solution for M,N50,
- your program yields a solution for M,N500,
- your program yields a solution for M,N1000.
The source code (s83.pas, s83.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s83.txt, s83.pdf, ...) - also describing which developer environment to use for compiling the source - should be submitted in a compressed file s83.zip.
Deadline expired on November 11, 2013.
Sorry, the solution is available only in Hungarian. Google translation
22 students sent a solution. 10 points: Juhász 326 Dániel, Kiss 666 Péter, Kovács-Deák Máté, Makk László, Németh 123 Balázs, Weisz Ambrus, Zalavári Márton. 9 points: Fonyó Viktória, Gercsó Márk, Molnár-Sáska Zoltán, Somogyvári Kristóf, Zarándy Álmos. 6 points: 3 students. 5 points: 2 students. 3 points: 1 student. 1 point: 2 students. Unfair, not evaluated: 2 solutions.