Image by Elisa Riva (
Pixabay),
Public Domain
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
arbitrarysounding 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
tworound, singleelimination 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 firstround 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_{t1} \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 spaceseparated
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
spaceseparated 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 floatingpoint 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
