Next, I wrote a new method inside the class called:
long long days_if_i_buy_b_fruit(long long b);
This calculates the number of days that I live if I buy b fruit. For example, in example 0:
Once you have written days_if_i_buy_b_fruit(), you can simply try all potential values of b, from 0 up to the maximum that you can afford. Return the maximum number of days that you will live.
Go ahead and write this -- it will solve examples 0 through 3. It won't solve example 4, though, because the constraints are too big, and you are trying every fruit.
This is the point at which you may want to bust out some algebra, but resist that thought. Go ahead and print out each value of b and how many days that lets you live. Do this for example 0 (I'm doing it for you):
Fruit Days bought(b) you live ------ -------- 0 5 1 6 2 7 3 8 4 9 5 10 6 11 7 10 8 6 9 3 10 0You'll note that the days you live increases to a maximum, and then decreases. You can use that fact to limit the values of b that you test.
What I did was the following. I tried every value of b that was a multiple of 10,000. Sure, for examples 0 through 3, the only value of b that fits that description is 0, but for example 4, I'm trying quite a few of them. The maximum number of fruit that I'll try, given the constraints, is 2,000,000,000 / 10,000, which is 200,000. So this part of my program will run fast enough (you get roughly 10,000,000 operations on topcoder).
So, go ahead determine the best value of b that is a multiple of 10,000. Call that b10K. You know that the actual best value of b will be between (B10K-10,000) and (B10K+10,000). You can test all of those with 20,000 calls to days_if_i_buy_b_fruit(long long b). That's also fast enough.
This approach lets you solve the problem quickly enough for topcoder, and you'll note that you don't use any floating point.
If you haven't solved the problem already, go ahead and try to solve it in this manner. I will email the TA's my solution, and they can show that solution (or theirs) to you at the end of the first part of lab.
Another fun way to solve this is to write a method called:
bool can_i_live_y_days(long long y);
Then, you can do a binary search on the number of days that you can live -- start with 0 (which you know you can do), and (F+D/P+1), which you know you can't do. Then use these to do a binary search. Now your running time is O(log(F+D/P)).