Genius Acm

Luogu

IDLGP10455

Time1000ms

Memory512MB

DifficultyP5

贪心倍增

Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturers in the world. 每天，该公司生产 $n$ 台 CPU 并销售到世界各地。 ACM 公司的质检部门会对生产出的 CPU 进行成组测试，对一组（若干个）CPU 进行测试的方法如下： 1. 随机从该组 CPU 中选取 $m$ 对（即 $2m$ 台），若总数不足 $2m$ 台，则选取尽量多对。 2. 对于每一对 CPU，测量它们之间的 Relative Performance Difference (RPD)，并把第 $i$ 对的 RPD 记为 $D_i$。RPD 的计算方法在后面给出。 3. 该组 CPU 的 Sqared Performance Difference (SPD）由以下公式给出： $SPD=\sum _i D^2_i$ 4. 该组 CPU 通过质检，当且仅当 $SPD \le k,$ 其中 $k$ 是给定常数。 ACM 公司生产的 CPU 性能很好，而质检部门制定的标准更是过于严格。通常他们把 $n$ 台 CPU 作为一整组进行测试，这导致一些性能良好的 CPU 无法通过测试，生产部门对此颇有微词。作为质检部门的领导，小 S 在不更改质检测试流程的前提下，想出了这样一个主意：如果能够把 $n$ 台 CPU 恰当地分成连续的若干段，使得每段 CPU 都能够通过成组测试，就可以解决当下的问题。现在，小 S 已经知道了 $n$ 台各自的性能表现 $P_1,\cdots ,P_n$，两台 CPU 的 RPD 被定义为它们性能表现的差的绝对值。请你帮忙计算一下，至少把这些 CPU 分成多少段，才能使得每一段都能通过成组测试。 ## Input 每个测试点包含多组数据，第一行整数 $T$ 给出数据组数。对于每组数据，第一行三个整数 $n,m,k$，第二行 $n$ 个整数 $P_1,\cdots ,P_n$。 ## Output 对于每组数据，输出一个整数表示答案。 [samples] ## Note 对于 $20 \%$ 的数据，$1 \leq n \leq 10^2$ 。对于 $40 \%$ 的数据， $1 \leq n \leq 10^3$ 。对于另外 $10 \%$ 的数据，$k=0$ 。对于另外 $10 \%$ 的数据，$0 \leq k \leq 1$ 。对于另外 $10 \%$ 的数据， $m=1$ 。对于另外 $10 \%$ 的数据，$1 \leq m \leq 2$ 。对于 $90 \%$ 的数据，$0 \leq k \leq 10^{12}$ 。对于 $100 \%$ 的数据，$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}$ 。

Samples

Input #1

Output #1

2
1

API Response (JSON)

{
  "problem": {
    "name": "Genius Acm",
    "description": {
      "content": "Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturers in the world. 每天，该公司生产 $n$ 台 CPU 并销售到世界各地。 ACM 公司的质检部门会对生产出的 CPU 进行成组测试，对一组（若干个）CPU 进行测试的方法如下： 1. 随机从该组 CPU 中选取 $m$ 对（即 $2m$ 台），若",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10455"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturers in the world. 每天，该公司生产 $n$ 台 CPU 并销售到世界各地。\n\nACM 公司的质检部门会对生产出的 CPU 进行成组测试，对一组（若干个）CPU 进行测试的方法如下：\n\n1. 随机从该组 CPU 中选取 $m$ 对（即 $2m$ 台），若...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments