HockeyPlayoff
SRM 766 · 2019-09-09 · by misof
Problem Statement
An ice hockey playoff final is played as a sequence of matches. The winner is the first team that wins winsNeeded of those matches.
Teams A and B are facing off in such a final. The home ice alternates every two matches. That is, A plays the first two matches on their home ice, B plays matches 3 and 4 on their home ice, A plays matches 5 and 6 at home, and so on.
It is known that home and away games are completely different. In this matchup, we know the following about a single independent game between A and B:
- If A plays at home ice, they win with probability AwinHome percent.
- If B plays at home ice, they win with probability BwinHome percent.
There is a reason why we emphasized the words "single independent game" in the previous paragraph. In a playoff series there is one more factor that influences the win probability of each team: momentum. The team that keeps winning has a morale boost that makes it more likely that they will win the next match. In this problem, momentum works as follows: if a team has a streak of W won matches in a row, their win probability for the next match is increased by 5*W percent (up to a maximum of 100 percent, of course).
For example, if A won the first game of the series and B won the next three, in game five B has a 5*3 = 15 percent boost due to momentum.
You are given winsNeeded, AwinHome and BwinHome. Let P be the probability that team A will win the whole series. Let M = 2*winsNeeded-1 be the maximum number of matches in the series. It can be shown that X = P * 100^M is an integer. Compute and return the value (X modulo (10^9 + 7)).
Constraints
- winsNeeded will be between 1 and 600, inclusive.
- AwinHome will be between 0 and 100, inclusive.
- BwinHome will be between 0 and 100, inclusive.
3 0 100 Returns: 0
The first one to three wins will win the series. Team A is completely hopeless and always loses, so B will win this series 3:0.
4 100 0 Returns: 999300007
The diametrally opposite situation to Example 0. The answer is 100^7 modulo (10^9 + 7).
600 50 50 Returns: 594375906
A perfectly symmetric situation. The answer is (0.5 * 100^1199) modulo (10^9 + 7).
4 53 57 Returns: 942200194
7 93 87 Returns: 545426737
Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HockeyPlayoff with a public method int winProbability(int winsNeeded, int AwinHome, int BwinHome) · 106 test cases · 2 s / 256 MB per case