Problem S. 91. (September 2014)
S. 91. Alice, Bob and Cecil are given \(\displaystyle N\) (\(\displaystyle 1\le N\le 60\)) boxes of presents. The value of each box is known: the \(\displaystyle i\)th box is worth \(\displaystyle a_i\) with \(\displaystyle 1\le a_i\le 100\). They would like to distribute these presents in a fair way. A particular distribution of the presents among the three people is said to be fair, if the person getting the set of presents with the highest total value gets a set of presents having the smallest possible total value. For example, if the presents have values 2, 4, 5, 8, 9, 14, 15 and 20, then a fair distribution could be the following: Alice gets the presents with values 2, 9 and 15 (the total sum is 26); Bob gets the presents 4, 8 and 14 (with total sum 26); and Cecil gets the presents 5 and 20 (with total sum 25). Given the list of presents, your task is to determine the maximal sum of presents a person can get during a fair distribution (in other words, that maximal sum is to be minimized). Your program should read \(\displaystyle N\) from the first line of the standard input, then the \(\displaystyle a_i\) integers (separated by a space) from the following \(\displaystyle N\) lines. The first and only line of the standard output should contain the minimal maximum value in a fair distribution. In the example, ``Példa bemenet'' is a sample input, while ``Példa kimenet'' is the corresponding 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. Partial points can be obtained if your program yields a solution
\(\displaystyle \bullet\) for \(\displaystyle a_i\le 40\), or
\(\displaystyle \bullet\) for \(\displaystyle N\le 10\).
The source code (s91.pas, s91.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s91.txt, s91.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file s91.zip.
(10 pont)
Deadline expired on October 10, 2014.
Statistics:
22 students sent a solution. 10 points: Erdős Márton, Fuisz Gábor, Molnár-Sáska Zoltán, Németh 123 Balázs, Zalavári Márton. 9 points: Kiss Gergely. 8 points: 2 students. 7 points: 4 students. 6 points: 2 students. 5 points: 1 student. 4 points: 1 student. 3 points: 3 students. 2 points: 2 students. 0 point: 1 student.
Problems in Information Technology of KöMaL, September 2014