SRM 706, D2, 500-Pointer (SellingFruits)
James S. Plank
Sun Jan 29 10:47:03 EST 2017
In case Topcoder's servers are down
Here is a summary of the problem:
- Every day, you need to eat one piece of fruit, and spend x dollars.
- You currently have f pieces of fruit, and d dollars.
- You can buy fruit at a price of p dollars per piece of fruit.
- What is the maximum number of days that you can live?
- All numbers are between 1 and 2,000,000,000.
The examples
| Example |
x |
f |
d |
p |
Answer |
| 0 |
3 |
5 |
100 |
10 |
11 |
| 1 |
2 |
17 |
20 |
1 |
10 |
| 2 |
1 |
97 |
98 |
1 |
97 |
| 3 |
16 |
4 |
8 |
2 |
0 |
| 4 |
17 |
1 |
2000000000 |
4 |
95238095 |
| 5 |
1 |
1996245611 |
1999990159 |
123 |
1996275808 |
| 6 |
15000000 |
100 |
2000000000 |
1 |
133 |
| 7 |
1 |
1000000000 |
2000000000 |
1000000000 |
1000000000 |
Testing yourself
Like the Cryptography Problem,
I have a shell script tests.sh, that you can use to test your program. When you
run tests.sh, your answer should be identical to
answers.txt
Hints
This is a typical frustrating Topcoder problem -- it seems so simple, but there are pitfalls
out there that will trip you up. I'm going to give you two pieces of advice, before I
give you some time to work this out on your own:
- 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. I know there is a huge temptation to use algebra to solve
this problem. While you might get it right, I'll put money that you'll get it wrong
multiple times before you get it right. So try something easier on the brain.
BTW, when I solve these problems, I don't use any floating point
operations.
Give this one some time on your own. If you find yourself struggling, read the
hints below.
Binary Search
There are two different binary searches you can do on this problem. I'll frame
them as procedures you can write. In each of these, I assume that you store the
method's parameters in the class:
- long long days_if_i_buy_b_fruit(long long b); This returns how many
days that you will life if you buy b pieces of fruit. This function
will increase to a maximum value and then decrease, so a binary search is plausible
here. I'd worry about about duplicate values, myself, but it's a thought.
- bool can_i_live_y_days(long long y); This returns whether or not
you can live y days. Clearly, here there will be a maximum value of y
for which this is true. You want to find that maximum. I think that this is the
easier of the two binary searches.
Is this the best solution?
Probably not. The proper way to solve this
problem, when you're not doing a programming competition, is to (ha ha) use algebra, and
get it right. That will be O(1).
However, this solution, which is O(log(f+d)) is plenty fast.