P10455 Genius Acm

Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturers in the world. Every day, the company produces $n$ CPUs and sells them all over the world. ACM's quality inspection department tests the produced CPUs in groups. The testing method for one group (several CPUs) is as follows: 1. Randomly select $m$ pairs of CPUs (i.e., $2m$ CPUs) from the group. If the total number is less than $2m$, select as many pairs as possible. 2. For each pair of CPUs, measure their Relative Performance Difference (RPD), and denote the RPD of the $i$-th pair as $D_i$. The definition of RPD is given later. 3. The Squared Performance Difference (SPD) of this group of CPUs is given by: $SPD=\sum _i D^2_i$ 4. This group of CPUs passes the quality inspection if and only if $SPD \le k,$ where $k$ is a given constant. The CPUs produced by ACM have very good performance, but the standards made by the quality inspection department are even too strict. Usually, they test all $n$ CPUs as one single group, which causes some good CPUs to fail the test, and the production department complains about it. As the leader of the quality inspection department, Xiao S came up with an idea without changing the testing process: if the $n$ CPUs can be properly divided into several consecutive segments, and every segment can pass the group test, then the current problem can be solved. Now, Xiao S already knows the performance values $P_1,\cdots ,P_n$ of the $n$ CPUs. The RPD of two CPUs is defined as the absolute value of the difference between their performance values. Please help compute the minimum number of segments to divide these CPUs into, so that every segment can pass the group test.

Each test point contains multiple test cases. The first line contains an integer $T$, the number of test cases. For each test case, the first line contains three integers $n,m,k$. The second line contains $n$ integers $P_1,\cdots ,P_n$.

For each test case, output one integer representing the answer.

For $20\%$ of the testdata, $1 \leq n \leq 10^2$。 For $40\%$ of the testdata, $1 \leq n \leq 10^3$。 For another $10\%$ of the testdata, $k=0$。 For another $10\%$ of the testdata, $0 \leq k \leq 1$。 For another $10\%$ of the testdata, $m=1$。 For another $10\%$ of the testdata, $1 \leq m \leq 2$。 For $90\%$ of the testdata, $0 \leq k \leq 10^{12}$。 For $100\%$ of the testdata, $T \leq 12,1 \leq n, m \leq 5 \cdot 10^5, 0 \leq k \leq 10^{18}, 0 \leq P_i \leq 2^{20}$。 Translated by ChatGPT 5