PrimeSoccer
SRM 422 · 2008-10-18 · by mateuszek
SRM 422 · 2008-10-18 · by mateuszek · Dynamic Programming, Math
Problem Statement
Problem Statement
You are watching a soccer match, and you wonder what the probability is that at least one of the two teams will score a prime number of goals. The game lasts 90 minutes, and to simplify the analysis, we will split the match into five-minute intervals. The first interval is the first five minutes, the second interval is the next five minutes, and so on. During each interval, there is a skillOfTeamA percent probability that team A will score a goal, and a skillOfTeamB percent probability that teamB will score a goal. Assume that each team will score at most one goal within each interval. Return the probability that at least one team will have a prime number as its final score.
Notes
- The returned value must be accurate to within a relative or absolute value of 1E-9.
- A prime number is a number that has exactly two divisors, 1 and itself. Note that 0 and 1 are not prime.
Constraints
- skillOfTeamA will be between 0 and 100, inclusive.
- skillOfTeamB will be between 0 and 100, inclusive.
Examples
0)
50 50 Returns: 0.5265618908306351
1)
100 100 Returns: 0.0
Both teams will score a goal in each interval, so the final result will be 18 to 18.
2)
12 89 Returns: 0.6772047168840167
3)
43 12 Returns: 0.6967817545210753
4)
55 100 Returns: 0.32120857144574655
Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PrimeSoccer with a public method double getProbability(int skillOfTeamA, int skillOfTeamB) · 43 test cases · 2 s / 256 MB per case