Problem N
Scorigami
In many sports, the scoreline at the end of a game is only remarkable because of its magnitude. However, in American football some scorelines are quite rare, with many scores having never happened at all. For example, a final score of $8-7$ has never happened in any professional football game since 1920. This is because of American football’s strange scoring rules, which allow for scores of $2$, $3$, $6$, $7$, $8$, with scores of $7$ and $3$ being the most common. The exact probabilities of each score are shown in the table below:
|
Score |
7 |
3 |
8 |
6 |
2 |
|
P(Score) |
20% |
10% |
5% |
2% |
1% |
In a standard game of American football, each team has a turn with the ball called a possession where they can attempt to score. After their attempt (whether it is successful or not) the ball is given to the other team, who then gets to attempt to score. For the purposes of this problem, you may assume that each team gets $2$ possessions per quarter and that there are exactly $4$ quarters per game.
When a scoreline is achieved that has never been achieved before it is called a Scorigami. Many fans of football root specifically for Scorigami, and would like to know when an ongoing game is close to ending in Scorigami without having to consult a chart constantly during the game. They have asked you to develop a tool that tells them how probable a Scorigami is.
Input
On the first line will be $4$ integers, $n$, $k$, $a$, $b$, where $n$ ($1 \leq n \leq 10^6$) is the number of scores that would count as Scorigami, $k$ ($1 \leq k \leq 4$) is the current quarter of the game and $a$ and $b$ ($0\leq a, b \leq 500$) are the scores of team A and team B at the start of quarter $k$. The next $n$ lines contain two integers $j$ and $i$ ($0 \leq i \leq j \leq 10^4$), each representing a score that counts as Scorigami. All Scorigamis are guaranteed to be unique.
Note that a score counts as Scorigami regardless of order. For example, if $10-3$ is a Scorigami, then team A scoring $10$ and team B scoring $3$ counts as Scorigami just like team A scoring $3$ and team B scoring $10$ at the end of the game.
Output
Output the probability that the game ends in a Scorigami. Your answer will be accepted if its absolute or relative error is within $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 7 3 7 3 10 3 15 3 |
0.00144691269775744196997338456064 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 1 0 0 500 500 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 4 0 0 6 0 7 0 8 0 |
0.26538976 |
