Problem S. 93. (November 2014)
S. 93. There are \(\displaystyle N\le 100\; 000\) athletes participating in a training program. Each athlete has to cycle round a lake, then row across the lake and back, in this order. Due to financial reasons however the sports club only has a single bicycle and a single boat. This means that only one athlete can cycle at any given moment, and the same restriction holds for the rowing. For each athlete they know how many hours it takes to cycle round the lake, and how many hours (s)he needs to row across the lake. They want to finish the training program as soon as possible, hence we are interested in the minimum total time to do this.
Your program should read \(\displaystyle N\) from the first line of the standard input, then the \(\displaystyle b_i\), \(\displaystyle e_i\) quantities from the following \(\displaystyle N\) lines - these values stand for the cycling and rowing times in hours, respectively, and they are separated by a space. In the first and only line of the standard output, your program should write the minimum time in hours so that everybody can finish the training program.
In the example, ``Példa bemenet'' is a sample input, and ``Példa kimenet'' is the corresponding output.
Explanation: the correct order is 3, 1, 2.
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 (s93.pas, s93.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s93.txt, s93.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file s93.zip.
Deadline expired on December 10, 2014.
14 students sent a solution. 10 points: Alexy Marcell. 9 points: Fuisz Gábor. 7 points: 1 student. 3 points: 4 students. 2 points: 3 students. 1 point: 4 students.