P10389 [Lanqiao Cup 2024 NOI Qualifier A] Score Statistics

There are $n$ students in Xiao Lan's class. After an exam, Xiao Lan wants to analyze the students' scores. The score of the $i$-th student is $a_i$. After Xiao Lan has checked the scores of the first $x$ students, he can choose any $k$ students from $1 \sim x$ and compute the variance of these $k$ scores. What is the minimum number of students' scores Xiao Lan must check so that it is possible to choose $k$ students whose variance is less than a given value $T$? Hint: The variance $\sigma^2$ of $k$ numbers $v_1, v_2, \cdots , v_k$ is defined as $\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} k$, where $\bar v$ is the average of $v_i$, $\bar v = \dfrac {\sum_{i=1}^k v_i} k$.

The first line contains three positive integers $n, k, T$, separated by one space. The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, separated by one space.

Output one line containing one integer, the answer. If the condition cannot be satisfied, output $-1$.

After checking the scores of the first three students, you can only choose $3, 2, 5$, and the variance is $1.56$. After checking the scores of the first four students, you can choose $3, 2, 2$, and the variance is $0.22 < 1$, so the answer is $4$. Constraints: For $10\%$ of the testdata, $1 \le n, k \le 10^2$. For $30\%$ of the testdata, $1 \le n, k \le 10^3$. For all testdata, $1 \le n, k \le 10^5$, $1 \le T \le 2^{31} -1$, $1 \le a_i \le n$. Translated by ChatGPT 5