CoinFlipBetting | Topcoder Archive

Problem Statement

Heather the headmaster and Tasha the tailor are going to have a fabulous coin-flipping contest. The contest is played in rounds. In each round they are going to flip a large ceremonial coin. Each time the coin comes up heads, Heather gets a point; likewise, each tail gives Tasha a point. The first to reach N points wins the contest.

The ceremonial coin they are using isn't completely fair. It has a large H and T engraved on its opposite sides, and this slight asymmetry causes the coin to come up heads with probability P percent. This property of the coin is widely known.

Your friend Tom is willing to bet you S dollars, claiming that Heather will win the entire contest. He will now give you those S dollars, and if Heather wins, you will have to pay him back some amount T. The two of you agreed on the mathematically fair value T such that both your and Tom's expected profit is zero. You took the bet.

After you took the bet, you realized that you currently have no money other than the S dollars you got from Tom. It would be a real shame if Heather won and you did not have enough money to pay him back!

Luckily, your other friend Lucy is willing to accept bets on the outcomes of the individual coin flips. For each of those you may bet an arbitrary positive real number of dollars. The payoff for each of these bets is again such that your expected profit from the bet is zero. E.g., if P = 40 and you bet 600 dollars on the coin coming up tails, you will pay Lucy the $600 before the coin flip, and then you will get $1000 back if the coin really comes up tails.

Find any betting strategy for your bets with Lucy such that you are guaranteed to have enough money to pay Tom if Heather wins the contest. Suppose you already followed that betting strategy for several rounds. The outcomes of the coin flips in these rounds are given in the String[] results. If you wish to bet X dollars on heads in the next round, return X. If you wish to bet X dollars on tails, return -X.

You may assume that at least one betting strategy with the desired property exists. If there are multiple such strategies, you may return a value consistent with any one of them. More precisely, your return value will be accepted if it is within relative or absolute error 1e-9 of any such value.

Definition

Class:: CoinFlipBetting
Method:: bet
Parameters:: int, int, int, String
Returns:: double
Method signature:: double bet(int N, int P, int S, String results)
(be sure your method is public)

Constraints

N will be between 1 and 250, inclusive.
P will be between 40 and 60, inclusive.
S will be between 1 and 1000, inclusive.
Each character in results will be 'H' or 'T'.
The number of 'H's in result will be less than N.
The number of 'T's in result will be less than N.

Examples

```
1
```
```
47
```
```
100
```
```
""
```
```
Returns: 100.0
```
There is just a single coin flip. The coin has probability 47% to come up heads and 53% to come up tails. Tom gave you $100. In this situation you just come to Lucy and bet the $100 Tom gave you on the next flip coming up heads. If the flip really comes up heads, Lucy will pay you approximately $212.766, and you will then give that whole amount to Tom. If the flip comes up tails, Lucy won't give you any money, but that's OK: in this case you don't have to pay Tom anything either.
```
5
```
```
50
```
```
100
```
```
"HHHH"
```
```
Returns: 6.25
```
It can be shown that for any strategy with the desired properties at this exact moment you must have exactly $193.75 and in the next round you must bet exactly $6.25 on the flip coming up heads.
```
4
```
```
44
```
```
444
```
```
"HTT"
```
```
Returns: 171.4419362715535
```

"TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT"

Returns: 3.4499592625734194E-53

This return value is so close to zero that zero (and also any other value within 1e-9) would also be accepted. However, note that the return value shown above is almost exactly equal to a mathematically correct bet for this test case.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.