SRM 708, D2, 250-Pointer (SafeBetting)

James S. Plank

Mon Feb 20 15:23:40 EST 2017
Last revision: Thu Oct 8 03:57:22 EDT 2020

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh MD5 hash: dc3d9632cb77dbdae2b69d3ea5840cd4
answers.txt MD5 hash: 6dac14737159200036fd919d3fe849ed
Problem Given in Topcoder: February, 2017
Competitors who opened the problem: 358
Competitors who submitted a solution: 337
Number of correct solutions: 310
Accuracy (percentage correct vs those who opened): 86.6%
Average Correct Time: 11 minutes, 9 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given three integers, a, b and c.
You start with b dollars.
You can wager any amount of money. If you wager x and you win, you'll get your x back plus an additional x. If you lose, you lose x.
You start with b dollars. You want to end up with c dollars. However, you don't want to end up with less than a dollars.
Suppose you are lucky. What is the minimum number of wagers that you can make to turn b dollars into c dollars, while making sure that you never have less than a dollars if you lose.
The Topcoder constraints are that a < b < c < 1001. In my tests, that number is 1,000,001,000 rather than 1001.

Examples

#    a    b    c    answer
0   15   20   48    3 - Bet 5 and win to get 25.  Bet 10 and win to get 35.  Bet 13 and win to get 4.  In no case will you have < 15 dollars if you lose.
1   10  400  560    1
2    5    7   21    3
3    5    7   22    4
4   17   30 1000    7

Testing Yourself

If you run tests.sh, your output should be identical to answers.txt.

Hints

Try this on your own. If you get stuck, return here and read what I've written below.

The wrong way to solve this is to use math and calculate B. The right way is simply to simulate -- while b is less than c, calculate the maximum bet that you can make, and pretend that you win by adding it to b. Count the number of times that you do this. No math needed except addition and subtraction!

Where the math comes into play is calculating the running time. Note that if you bet x in round 0, then, if you win, you'll bet 2x in round 1. And if you win again, you'll bet 4x in round 2. And 8x in round 3. Do you see how the number of rounds is going to be capped at log₂(c)? Who needs math?