There is a controversial political topic and a group of \(n\) politicians.
Each politician currently has an opinion on the topic. This starting opinion of politician \(i\) is represented by the integer \(S[i]\). (If two politicians have \(S[i] = S[j]\), they share the same opinion.)
The opinions within the group will evolve as follows:
Each day, one politician (selected uniformly at random) can try to convince others that his or her current opinion is the correct one. During the day, the “active” politician will talk to exactly \(k\) other people. (Again, the \(k\)-element subset of the remaining \(n-1\) people is selected uniformly at random). Each of the people listening to the speaker will change their current opinion to the speaker’s opinion with with probability \(p\) percent. All random choices are mutually independent.
(It is possible that some of the \(k\) people selected by the speaker already share the speaker’s opinion. If that happens, they will listen to the speaker and keep their mutual opinion.)
Determine the expected number of days until everybody shares the same opinion. Return \(-1\) if that expected number is infinite.
The first line of the input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.
Each test case consists of two lines. The first line has the integers \(n\), \(k\), and \(p\). The second line has the integers \(S[0], \dots, S[n-1]\).
You may assume that in each input \(n\geq 2\), \(1\leq k\leq n-1\), \(0 < p\leq 100\), and that each \(S[i]\) is between \(0\) and \(n-1\), inclusive.
For each test case output a single line with a single real number: the expected number of days until everybody shares the same opinion, or the value \(-1\) if that expected value isn’t finite.
Make sure you output enough decimal places. Answers with an absolute or a relative error less than \(10^{-8}\) when compared to the reference answer will be accepted as correct.
Input file: P1.in
In this subproblem \(t=13\) and in each test case \(n\leq 5\), \(k=1\), and \(p=100\).
Input file: P2.in
In this subproblem \(t=30\) and each test case has \(n\leq 22\) and \(k\leq 2\).
Input file: P3.in
In this subproblem \(t=30\) and each test case has \(n\leq 1000\) and \(k\leq 20\).
Input file: P4.in
In this subproblem \(t=30\) and each test case has \(n\leq 20\,000\) and \(k\leq 50\).
In this task all subproblems are public due to real numbers being used in this problem.
The reference outputs have been calculated to a much greater precision than needed. The reference solution that uses only standard floating-point variables is more precise than required by multiple orders of magnitude. Still, we recognize that calculations with floating-point variables are inherently imprecise and some unforeseen approaches may struggle with precision issues.
For all subproblems, the grader outputs a special error message if you are within \(10^{-5}\) abs/rel error for all test cases but not within the required \(10^{-8}\).
input4 2 1 50 1 1 2 1 50 0 1 5 4 100 1 1 1 3 1 4 2 10 0 0 3 1 | output0.000000000000 2.000000000000 1.000000000000 37.982456140351 |
