 Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# 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