SimplifiedDarts
SRM 318 · 2006-08-29 · by Andrew_Lazarev
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.
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.
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%.
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%.
30 384 3 1 Returns: 18.344490479047746
You are a bad shooter, but you have many attempts.
999 333 0 100 Returns: 100.0
You are an excellent 3-point shooter. The victory is yours.
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.
Submissions are judged against all 89 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SimplifiedDarts with a public method double tryToWin(int W, int N, int P1, int P2) · 89 test cases · 2 s / 256 MB per case