Problem A
Genius
If someone were to make a prediction that everyone thought was doomed to failure, and it turned out to be correct, wouldn’t it be shortsighted simply to dismiss this as a stroke of luck? What if the person could do so over and over again? Instead of explaining away those capable of such prognostications, society has labelled them ‘geniuses’, and has accepted that mere mortals are simply unable to comprehend their godlike level of reasoning, reasoning that transcends common sense.
Jimmy is not a genius, but he would like to fool people into thinking he is one so that he can use this rarefied title on his resume and land his dream job. He has come up with a strategy that he claims will correctly predict at least $K$ winners out of the next $T$ tournaments of a certain game, but nobody seems to believe in his arbitrary-sounding strategy. However, if Jimmy’s claim turns out to be correct, the doubters will quickly change their minds, and he will earn the genius label that he so deeply desires.
A tournament involves $4$ players, and is based on a two-round, single-elimination system. In the first round, players $0$ and $1$ play each other, and players $2$ and $3$ play each other. In the second round, the two first-round winners play each other, and the resulting winner is crowned the champion of the entire tournament. Each player has a strategy with positive weight $W$. If a player with a strategy of weight $A$ competes against a player with a strategy of weight $B$, then the first player wins with probability $\frac{A}{A+B}$ (and therefore the second player wins with probability $\frac{B}{A+B}$). The outcome of each game is independent of all other games.
Jimmy’s strategy for determining tournament winners is taken from an exercise in a number theory book he idly flipped through in the library one day. First he chooses distinct prime numbers $P$ and $Q$, and then he uses them to generate a sequence of nonnegative integers $X_1, X_2, X_3, \ldots , X_ T$ as follows: (a) He randomly picks $X_1$ satisfying $1 \leq X_1 < Q$. (b) He applies the formula $X_ t = (X_{t-1} \cdot P)$ mod $Q$ for $2 \leq t \leq T$ to compute the remaining terms in the sequence. (c) He performs a mod 4 operation on every term so that his sequence now consists only of the integers $0, 1, 2, 3$. Finally, when the tournaments begin, Jimmy predicts that the winner of tournament $1$ is player $X_1$, the winner of tournament $2$ is player $X_2$, and so on.
Input
The first line of input contains five space-separated integers, $K$, $T$, $P$, $Q$, and $X_1$, as described above, where $1 \leq K \leq T \leq 100$, $1 < P < Q < 1\, 000$, and $1 \leq X_1 < Q$. Each of the next $T$ lines contains four space-separated integers $W_0$, $W_1$, $W_2$ and $W_3$, the weights of the strategies of players $0$ to $3$, respectively, where the $t^{\mathrm{th}}$ line contains this weight information for the $t^{\mathrm{th}}$ tournament ($1 \leq t \leq T$). Each weight is between $1$ and $100$, inclusive.
Output
Output a single floating-point number: the probability that Jimmy is perceived as a genius by the general public and therefore be able to get his dream job — in other words, the probability that Jimmy’s strategy correctly predicts the winner of at least $K$ out of the $T$ tournaments. Your answer must have an absolute or relative error of at most $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 4 7 13 5 1 2 3 4 4 3 2 1 2 2 2 2 4 6 3 5 |
0.2473950797 |
