Problem E
Kayaking Trip

Solution to Sample Input 1, with kayaks replaced by canoes (cc by-sa NCPC 2017)
You are leading a kayaking trip with a mixed group of participants in the Stockholm archipelago, but as you are about to begin your final stretch back to the mainland you notice a storm on the horizon. You had better paddle as fast as you can to make sure you do not get trapped on one of the islands. Of course, you cannot leave anyone behind, so your speed will be determined by the slowest kayak. Time to start thinking; How should you distribute the participants among the kayaks to maximize your chance of reaching the mainland safely?

The kayaks are of different types and have different amounts of packing, so some are more easily paddled than others. This is captured by a speed factor $c$ that you have already figured out for each kayak. The final speed $v$ of a kayak, however, is also determined by the strengths $s_1$ and $s_2$ of the two people in the kayak, by the relation $v=c(s_1+s_2)$. In your group you have some beginners with a kayaking strength of $s_ b$, a number of normal participants with strength $s_ n$ and some quite experienced strong kayakers with strength $s_ e$.


The first line of input contains three non-negative integers $b$, $n$, and $e$, denoting the number of beginners, normal participants, and experienced kayakers, respectively. The total number of participants, $b+n+e$, will be even, at least $2$, and no more than $100\, 000$. This is followed by a line with three integers $s_ b$, $s_ n$, and $s_ e$, giving the strengths of the corresponding participants ($1 \leq s_ b < s_ n < s_ e \leq 1\, 000$). The third and final line contains $m = \frac{b+n+e}{2}$ integers $c_1, \ldots , c_ m$ ($1 \leq c_ i \leq 100\, 000$ for each $i$), each giving the speed factor of one kayak.


Output a single integer, the maximum speed that the slowest kayak can get by distributing the participants two in each kayak.

Sample Input 1 Sample Output 1
3 1 0
40 60 90
18 20
Sample Input 2 Sample Output 2
7 0 7
5 10 500
1 1 1 1 1 1 1

Please log in to submit a solution to this problem

Log in