2014 Canadian Computing Competition, Stage 2
Day 2, Problem 1: Where's That Fuel?
The heroic Team Star Fox is on a mission to collect as much fuel as possible from various planets across the Lylat System. There are N (1 ≤ N ≤ 105) planets, and the i-th one contains Ai fuel cells - but travelling there from any other planet uses up Bi fuel cells (1 ≤ Ai, Bi ≤ 104). Unfortunately, fuel cells are not a sustainable resource, so if a planet is visited for a second time, there will be no new fuel to collect.
Team Star Fox starts on planet P (1 ≤ P ≤ N) - as such, they may collect its fuel cells immediately. They may then travel to as many different planets as they'd like to, in any order, as long as they have sufficient fuel to spend on each flight (that is, their fuel cell count remains non-negative). Finally, they may choose to stop at any point (possibly even before leaving planet P), with the goal of maximizing the number of fuel cells they end up with. If this can be done in multiple ways, they'd like to maximize the number of different planets they visit as a secondary objective. Can you help our heroes?
The first line contains two integers: N (1 ≤ N ≤ 105), followed by a space, followed by P (1 ≤ P ≤ N), which represents the number of planets followed by the starting planet number. The next N lines contain Ai, followed by a space, followed by Bi (1 ≤ Ai, Bi ≤ 104).
You can assume that for test cases worth 20% of the marks, N ≤ 10.
The output consists of two lines, with each line containing one positive integer. The ﬁrst line contains the largest number of fuel cells that Team Star Fox can possess once they decide to stop. The second line contains the largest number of planets that Team Star Fox can visit, such that they still end up with this maximal number of fuel cells.
5 2 12 12 10 100 8 3 4 5 25 15
Team Star Fox starts on planet 2, on which they collect 10 fuel cells to start off. They should proceed by travelling to planet 3, costing them 3 fuel cells but then increasing their fuel cell count to 15. Next, they can fly to planet 1, lowering their fuel cell count to 3 but then promptly restoring it to 15. Finally, they have just enough fuel to reach planet 5, at which point they can collect its fuel cells to end up with 25. They should then choose to stop without ever visiting planet 4.
Point Value: 7 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 17, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3