TopCoder problem "SimplifiedDarts" used in SRM 318 (Division II Level Three)



Problem Statement

    

You are playing a simplified version of darts. For each throw, you choose one of two distances from the target and throw the dart. If you hit the target from the short distance, you get 2 points, and if you hit it from the long distance, you get 3 points. You get no points for missing the target.

You get N throws, and you must get at least W points to win. You hit the target with probability P1 percent from the short distance, and with probability P2 percent from the long distance. Return the expected probability (as a percentage between 0 and 100) that you will win.

 

Definition

    
Class:SimplifiedDarts
Method:tryToWin
Parameters:int, int, int, int
Returns:double
Method signature:double tryToWin(int W, int N, int P1, int P2)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-W will be between 1 and 1000, inclusive.
-N will be between 1 and 1000, inclusive.
-P1 will be between 0 and 100, inclusive.
-P2 will be between 0 and 100, inclusive.
 

Examples

0)
    
5
2
50
25
Returns: 12.5
You should make one throw from the short distance and one throw from the long. Both throws must be successful to win. The expected probability of winning is 0.5*0.25 = 12.5%.
1)
    
6
3
90
20
Returns: 73.30000000000001
You are a good short distance shooter. Make your first throw from the short distance. If you hit the target, make your next two throws from the short distance as well. If you miss the first throw, you need to make the next two throws from the long distance. The expected probability of winning is 0.9*(0.9*0.9) + 0.1*(0.2*0.2) = 73.3%.
2)
    
30
384
3
1
Returns: 18.344490479047746
You are a bad shooter, but you have many attempts.
3)
    
999
333
0
100
Returns: 100.0
You are an excellent 3-point shooter. The victory is yours.
4)
    
1000
333
0
100
Returns: 0.0
You are an excellent 3-point shooter, but it is impossible to get 1000 points with just 333 throws.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6685

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9998&pm=6685

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Dynamic Programming