- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: January, 2017 -
**Competitors who opened the problem**: 380 -
**Competitors who submitted a solution**: 325 -
**Number of correct solutions**: 189 -
**Accuracy (percentage correct vs those who opened)**: 49.7% -
**Average Correct Time**: 20 minutes, 31 seconds.

- Don't use integers for anything -- use
**long long**'s. When Topcoder puts constraints at the 2,000,000,000 mark, they're doing it so that you'll hit overflow with integers if you're not super-careful. So don't use integers. - Beware of trying to use math that will end up with floating point, when all of the equations involve integers. When I solve these problems, I don't use any floating point operations.

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:

- If I buy b=0 fruit, then I will live 5 days, because I have 5 fruits, and at least 15 dollars.
- If I buy b=1 fruit, then I will live 6 days, because I have 6 fruits, and at least 18 dollars.
- If I buy b=7 fruits, then I will live 10 days. Although I have 13 fruits, I only have 30 dollars left after buying the 7 fruits, so I live 30 days.

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

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))*.