← 返回题目列表

Codeforces · 1851/A

A. 自动扶梯对话

中文机器翻译题面 查看原题

有一天,Vlad 开始好奇他可以在地铁的自动扶梯上与谁交谈。总共有 $$$n$$$ 乘客。自动扶梯总共有 $$$m$$$ 梯级,所有梯级索引从 $$$1$$$ 到 $$$m$$$,第 $$$i$$$ 梯级的高度为 $$$i \cdot k$$$。

Vlad 的身高是 $$$H$$$ 厘米。身高为 $$$a$$$ 和 $$$b$$$ 的两个人,如果站在不同的台阶上,并且他们之间的高度差等于台阶之间的高度差,则可以在自动扶梯上进行对话。

例如,如果两个人的身高分别为 $$$170$$$ 和 $$$180$$$ 厘米,并且 $$$m = 10,k = 5$$$,那么他们可以站在编号为 $$$7$$$ 和 $$$5$$$ 的台阶上,其中台阶之间的高度差等于两个人之间的高度差: $$$k \cdot 2 = 5 \cdot 2 = 10 = 180 - 170$$$。还有其他可能的方法。

给定一个大小为 $$$n$$$ 的数组 $$$h$$$,其中 $$$h_i$$$ 表示第 $$$i$$$ 个人的身高。弗拉德感兴趣的是他可以在自动扶梯上单独与多少人交谈。

例如,如果$$$n = 5,m = 3,k = 3,H = 11$$$,并且$$$h = [5, 4, 14, 18, 2]$$$,Vlad可以与身高$$$5$$$的人进行对话(Vlad将站在台阶$$$1$$$上,另一个人将站在台阶上$$$3$$$)和身高为$$$14$$$的人(例如,Vlad可以站在台阶$$$3$$$上,而另一个人将站在台阶$$$2$$$上)。 Vlad 无法与身高 $$$2$$$ 的人进行对话,因为即使他们站在自动扶梯的最极端的台阶上,他们之间的身高差也会是 $$$6$$$,而他们的身高差是 $$$9$$$。 Vlad 无法与自动扶梯上的其他人交谈,因此此示例的答案是 $$$2$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是测试用例的描述。

每个测试用例的第一行包含整数:$$$n, m, k, H$$$ ($$$1 \le n,m \le 50$$$, $$$1 \le k,H \le 10^6$$$)。这里,$$$n$$$是人数,$$$m$$$是步数,$$$k$$$是相邻步之间的高度差,$$$H$$$是Vlad的身高。

第二行包含 $$$n$$$ 整数:$$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^6$$$)。这里,$$$h_i$$$表示第$$$i$$$个人的身高。

输出

对于每个测试用例,输出一个整数 - Vlad 可以在自动扶梯上单独交谈的人数。

示例

输入 #1

7
5 3 3 11
5 4 14 18 2
2 9 5 6
11 9
10 50 3 11
43 44 74 98 62 60 99 4 11 73
4 8 8 49
68 58 82 73
7 1 4 66
18 66 39 83 48 99 79
9 1 1 13
26 23 84 6 60 87 40 41 25
6 13 3 28
30 70 85 13 1 55

输出 #1

2
1
4
1
0
0
3

注意

第一个示例在问题陈述中进行了解释。

在第二个示例中,Vlad 可以与身高 $$$11$$$ 的人进行对话。

在第三个示例中,Vlad 可以与身高为 $$$44, 74, 98, 62$$$ 的人进行对话。因此,答案是$$$4$$$。

在第四个示例中,Vlad 可以与身高 $$$73$$$ 的人进行对话。