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)).
Definition
- Class:
- HockeyPlayoff
- Method:
- winProbability
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int winProbability(int winsNeeded, int AwinHome, int BwinHome)
- (be sure your method is public)
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.
Examples
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
361
55
70
Returns: 76373350
532
65
49
Returns: 365848879
402
53
84
Returns: 631219872
25
0
33
Returns: 45144642
494
40
72
Returns: 577479278
438
30
66
Returns: 287922758
556
30
4
Returns: 581365816
591
88
45
Returns: 55868740
351
30
100
Returns: 676383354
37
42
12
Returns: 649356180
565
69
32
Returns: 737804427
100
89
42
Returns: 227120490
595
14
98
Returns: 313374739
586
36
98
Returns: 770769662
545
68
72
Returns: 403504245
539
72
99
Returns: 901322681
593
66
28
Returns: 916982913
117
48
62
Returns: 124617722
260
56
1
Returns: 896131203
175
9
34
Returns: 658005131
600
55
46
Returns: 839481590
582
77
66
Returns: 232581684
502
73
31
Returns: 780940982
555
88
23
Returns: 379891664
525
16
12
Returns: 937829555
567
50
13
Returns: 501642234
500
83
15
Returns: 866496555
425
47
2
Returns: 463711250
271
17
23
Returns: 266544335
525
100
98
Returns: 378732724
572
72
1
Returns: 845774187
76
19
69
Returns: 120205712
347
79
30
Returns: 292097646
515
2
11
Returns: 408153870
310
70
39
Returns: 142195647
245
70
74
Returns: 924638934
280
72
62
Returns: 829014865
351
14
52
Returns: 709892805
538
72
97
Returns: 798233444
501
8
65
Returns: 330976262
583
100
58
Returns: 914965594
572
66
97
Returns: 956312605
600
90
62
Returns: 731785138
515
96
31
Returns: 44657498
521
59
2
Returns: 453814091
558
35
81
Returns: 958104572
558
71
24
Returns: 949502982
294
98
33
Returns: 97961944
549
8
92
Returns: 513193358
568
95
46
Returns: 359259718
552
98
87
Returns: 816552887
210
13
65
Returns: 12078515
542
68
46
Returns: 571280707
112
79
95
Returns: 257480851
506
44
74
Returns: 419288850
581
34
32
Returns: 595404476
526
59
84
Returns: 421312578
599
56
40
Returns: 121251168
57
74
61
Returns: 702019135
1
54
58
Returns: 54
578
32
37
Returns: 768472133
515
21
54
Returns: 289600395
554
30
64
Returns: 762529832
540
71
2
Returns: 864242068
578
71
22
Returns: 263258698
387
23
78
Returns: 615827077
186
62
52
Returns: 905299674
62
59
22
Returns: 87757879
408
79
17
Returns: 591153598
500
49
63
Returns: 88540998
593
15
65
Returns: 860108875
411
11
53
Returns: 876206046
422
79
22
Returns: 843390828
556
76
11
Returns: 403396682
555
95
25
Returns: 546442807
509
16
91
Returns: 894113574
583
83
13
Returns: 451646251
511
45
3
Returns: 165797256
405
76
28
Returns: 103510179
529
64
32
Returns: 938518098
314
71
7
Returns: 974807709
294
62
89
Returns: 90870138
578
60
0
Returns: 647315212
410
80
70
Returns: 762532062
384
43
8
Returns: 418077371
161
30
23
Returns: 761558015
82
65
21
Returns: 331856605
170
11
16
Returns: 699981881
515
53
37
Returns: 719155837
563
86
44
Returns: 476782507
513
4
25
Returns: 603978052
573
42
11
Returns: 9900420
564
69
73
Returns: 739982769
581
56
55
Returns: 892784994
502
24
41
Returns: 549688626
512
56
98
Returns: 122355611
597
12
42
Returns: 651402321
448
42
100
Returns: 902576102
560
94
66
Returns: 250169245
487
29
25
Returns: 467069104
600
51
52
Returns: 355333564