19460번 - Guess the Distribution 스페셜 저지다국어

Let $p \in (0;1)$ be a real number and $n \in [1;100]$ be a positive integer. Consider $\xi_1, \xi_2, \ldots, \xi_n$ --- independent random variables such that $P(\xi_i = 1) = p$ and $P(\xi_i = 0) = 1 - p$. Consider the random variable \[\theta_n = \frac{\xi_1 + \ldots + \xi_n + u - np}{\sqrt{np(1-p)}}\text{,}\] where $u$ is a random variable which is uniformly distributed in $[-\frac{1}{2}, \frac{1}{2}]$ independently from all $\xi_i$.

You are given $p$ and a sample from the distribution $\theta_n$ for some $n$. You need to determine $n$.

The first line of input contains one integer $T$ ($T = 30$) --- the number of samples.

The second line contains a real number $p \in (0; 1)$ with at most two digits after the decimal point.

Each of next $T$ lines contains the description of the sample. It consists of an integer $N$ ($N = 10^4$) --- the size of the sample, and $N$ space-separated real numbers $x_1, x_2, \ldots, x_N$ with at most 10 digits after decimal point, describing the sample of the distribution $\theta_n$ for some $n$.

It is guaranteed that the test case is generated as follows: we choose $p$ and seed $s$ by hand and then choose all $n$ as $T$ random integers from $[1;100]$ using a pseudo-random number generator with initial seed $s$.

In the sample test case $T = 2$ and $N = 3$ just to show the format.

For each of $T$ samples print one integer on a separate line --- the number $\mathit{ans}_i \in [1;100]$ which you think defines the distribution $\theta_n$.

Your answer for the whole test case will be considered correct, if the average absolute error does not exceed 5, so that \[\frac{1}{T}\sum\limits_{i=1}^T |n_i - \mathit{ans}_i| \le 5\text{.}\]