← 返回比赛

已结束 ZZSR普及赛#2

← 上一题下一题 →

A7336 | $颗秒$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

--- 题目描述 小W 来到了无畏契约的「试炼大厅」，「试炼大厅」里面有一个靶场。 靶场可以看作一个圆，这个圆被均分为 $c$ 份，对应了 $c$ 个方向，按照顺序编号为 $0\sim c-1$。小W 站在这个靶场的中心，他不会移动，只会转动方向。 初始时（第 $0$ 秒），小W 面向 $0$ 号方向，每次训练 小W 会打 $n$ 个靶子。第 $i$ 个靶子会在第 $i$ 秒出现在第 $a_i$ 个方向$(1\le i \le n)$。 由于需要模拟实战效果，很显然的，只有在靶子出现的那一瞬间小W 击中了靶子，才能够认为 小W 击中了靶子。 小W 用的是笨重的大狙，所以他每秒钟最多只能转动 $s$ 个方向，也即往左边转至多 $s$ 个方向，或者往右边转至多 $s$ 个方向，或者选择不转动。 现在 小W 想问你，在最优的情况下，他最多能击中多少个靶子，小W是神枪手，所以他只要面向靶子就一定可以击中。

输入格式

本题一个测试点内有多组测试数据。 第一行输入一个正整数 $T$，表示测试数据组数。 对于每组测试数据： - 第一行输入三个正整数 $n,c,s$，含义见上。 - 第二行输入 $n$ 个整数 $a_i$，含义见上。

输出格式

输出共 $T$ 行，对于每组测试数据，输出一行一个整数表示最多能击中的靶子数量。

输入输出样例

输入 #1

2
5 6 1
0 4 3 0 4
11 45 14
13 40 30 1 32 5 22 39 4 19 35

输出 #1

3
6

对于第一组测试数据，以下是一种可能的转动方案： - 第 $0$ 秒，此时没有靶子，转动到 $5$ 方向。 - 第 $1$ 秒，靶子在方向 $0$，小W 在方向 $5$，未命中。转动到 $4$ 方向。 - 第 $2$ 秒，靶子在方向 $4$，小W 在方向 $4$，命中。转动到 $3$ 方向。 - 第 $3$ 秒，靶子在方向 $3$，小W 在方向 $3$，命中。转动到 $4$ 方向。 - 第 $4$ 秒，靶子在方向 $0$，小W 在方向 $4$，未命中。不转动。 - 第 $5$ 秒，靶子在方向 $4$，小W 在方向 $4$，命中。结束。 最终击中了 $3$ 个靶子，你也可以选择在第 $3$ 秒不转动，在第 $4$ 秒转动到 $4$ 方向。可以证明这是最优的打靶方式。 数据范围 对于 $100\%$ 的数据，$1\le T \le 10,1\le n \le 2\times 10^3,1\le s<c\le 10^9,0\le a_i <c$。 测试点编号特殊性质$1\sim 3$$\tt{A}$$4\sim 10$$\tt{-}$ 特殊性质 $\tt{A}:$ $n\le 10,s=1$。

C++ 编辑器

输入

输出