Problem E
Draft Lottery
In professional sports, a draft is typically held each year after the end of the season. The draft allows teams to select new players from among the available prospects. The order of selection is often determined using a lottery. A team’s odds of getting a draft pick are based on how the team finished during the regular season. The worse a team’s record in the regular season, the higher their chance of landing a top pick in the lottery (and strengthening their team before the next season).
Here we describe a novel draft lottery process. Each of the bottom $N$ teams will have their team’s logo placed on a certain number of lottery balls (each ball has exactly one team’s logo); the $i$-th worst-ranked team receives $b_i$ ping pong balls in the lottery. If team $i$ had a worse record than team $j$, then $b_i \ge b_j$.
All ping pong balls are placed in a mixing container and balls are drawn sequentially. The team whose logo is on the first ping pong ball drawn gets the first draft pick. The ball drawn is discarded. A second ball is drawn and the team whose logo is on that ball gets the second draft pick, and so forth. Whenever a ball is drawn for a team that has already received a pick, it is ignored and another ball is drawn in its place.
The first 3 picks are assigned by this lottery drawing. After the top 3 picks have been assigned, the remaining teams (those that did not receive a top-3 pick from the drawing) are assigned picks in order from worst record to best.
You’ve been hired as a consultant by one team’s Vice President of Analytics and Strategy to determine the probabilities of each team getting certain picks in order to help the team assess the values of potential trading situations.
Given the counts of ping pong balls that each team will receive in the draft, you must calculate the answers to queries of the form $(t, k)$, meaning, what is the probability that team $t$ receives one of the first $k$ draft picks?
Input
The first line contains an integer $N$ $(3 \le N \le 50)$, indicating the number of teams in the draft lottery. The next $N$ lines provide the number of lottery balls that each team is allocated. Specifically, the $i$-th of these $N$ lines contains two values: an integer $b_i$ $(1 \le b_i \le 50)$ and a string $t_i$. The team name $t_i$ consists of one to ten uppercase letters. The number of lottery balls for $t_i$ is indicated by $b_i$. Team names are unique and teams are listed strictly in worst-to-best order; for team $t_i$, listed immediately before team $t_{i+1}$, it is guaranteed that $b_i \ge b_{i+1}$.
The next line contains an integer $Q$ $(1 \le Q \le 200)$, the number of probability queries. Next, $Q$ lines follow, each containing one query. Each query line consists of a team name $t_j$ and an integer $k_j$ $(1 \le k_j \le N)$. The team name in each query is guaranteed to be present in the earlier allocation list.
Output
Output $Q$ lines. Each line should contain the answer to the respective query (in the same order they appear in the input). If the $j$-th query is $t_j$ and $k_j$, then the $j$-th output line should provide the probability of team $t_j$ receiving one of the first $k_j$ draft picks. Each probability must have a relative error of less than $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 SUNS 2 NUGGETS 1 JAZZ 9 SUNS 1 SUNS 2 SUNS 3 NUGGETS 1 NUGGETS 2 NUGGETS 3 JAZZ 1 JAZZ 2 JAZZ 3 |
0.571428571 0.895238095 1.0 0.285714286 0.714285714 1.0 0.142857143 0.39047619 1.0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 13 MAMMOTH 11 KNIGHTS 7 AVALANCHE 5 FLAMES 3 OILERS 9 MAMMOTH 1 MAMMOTH 2 MAMMOTH 3 MAMMOTH 4 MAMMOTH 5 KNIGHTS 1 AVALANCHE 2 FLAMES 3 OILERS 4 |
0.333333333 0.613999767 0.825377659 1.0 1.0 0.282051282 0.381096028 0.476970929 0.306898614 |
