ClockManagement
SRM 248 · 2005-06-21 · by lars2520
Problem Statement
In the game, the two teams take turns trying to score baskets. After one team attempts to score a basket and fails, that team may get the rebound and attempt to score again. Otherwise, if a team successfully scores or fails to get the rebound, the other team gets the ball. An attempt to score always involves some set up time where players get into position and pass the ball and things like that. The amount of time that a team takes to set up influences the probability that its shot attempt will be successful. If a team attempts to score and gets its own rebound, the setup starts over. To prevent teams from simply holding the ball until the end of the game when they are winning, the team with the ball must attempt to score within a certain timeframe (this is known as the shot clock, and is reset if a team attempts to score and rebounds).
In this problem, the probabilities of team A scoring are given by percentageA. Element i of percentageA indicates the probability (as a percentage) that a shot will score after i+2 seconds of setup. Due to the shot clock, team A must shoot after a number of seconds corresponding to an element of percentageA. Also, the probabilities that team A will rebound the ball after shooting and failing to score are given by reboundA, where element i corresponds to i+2 seconds of setup. Finally, scoreA indicates team A's current score. The parameters for team B are analogous.
Given the inputs as described above, the fact that team A has just gained possession of the ball, and the assumption that A plays optimally to win, while B plays optimally to prevent A from winning, you should compute the probability that team A wins the game (ties don't count).
Notes
- In this problem, teams may not attempt to score with less than 2 seconds of setup time.
- Time is treated discretely in this problem.
- Your return must have error less than 1E-9.
Constraints
- percentageA, percentageB, reboundA, and reboundB will each contain between 1 and 50 elements, inclusive.
- percentageA, percentageB, reboundA, and reboundB will all contain the same number of elements.
- Each element of percentageA, percentageB, reboundA, and reboundB will be between 0 and 100, inclusive.
- scoreA and scoreB will be between 0 and 100, inclusive.
- time will be between 1 and 300, inclusive.
{10,20,30,40}
{10,20,30,40}
{1,2,3,4}
{1,2,3,4}
5
99
100
Returns: 0.4
Trailing by only 1 point, the best strategy is to set up as long as possible (5 seconds), and then attempt to score right at the end of a game, making two points with a probability of 40%.
{10,20,30,40}
{10,20,30,40}
{1,2,3,4}
{1,2,3,4}
5
98
100
Returns: 0.0
There is no way to win here; the best you can do is score 2 points and tie it up, after which team B will wait until the end of the game.
{10,20,30,40}
{10,20,30,40}
{1,2,3,4}
{1,2,3,4}
10
98
100
Returns: 0.011519999999999997
The best strategy here is to set up for 2 or 3 seconds (it doesn't matter which) and then attempt to score. If you succeed, team B will set up for 5 seconds and then attempt to score. Assuming that B fails to score and fails to get the rebound, you will then have 2 or 3 seconds to set up and score again. The probability of things working out like this is 0.1*0.6*0.96*0.2 = 0.01152.
{5,8,10,13,15,20,25,30,35,40,41,42,42,43,44,46,45,45,46,47,48,48,48,49}
{0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13}
{20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43}
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
180
94
100
Returns: 0.11549711731257152
{0}
{0}
{0}
{0}
120
99
98
Returns: 1.0
Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ClockManagement with a public method double winProbability(vector<int> percentageA, vector<int> percentageB, vector<int> reboundA, vector<int> reboundB, int time, int scoreA, int scoreB) · 87 test cases · 2 s / 256 MB per case