← 返回题目列表

Codeforces · 1238/B

B. 杀死他们全部

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

Ivan 玩一款名为 Heretic 的旧动作游戏。他被困在游戏的最后一关,所以他需要一些帮助来杀死怪物。

关卡的主要部分是一条大走廊(又大又窄,可以表示为无限的坐标线)。走廊分为两部分;我们假设点 $$$x = 0$$$ 是这些部分的交汇处。

走廊的右侧充满了$$$n$$$怪物——对于每个怪物,其初始坐标为$$$x_i$$$(并且由于所有怪物都在右侧部分,因此每个$$$x_i$$$都是正数)。

走廊的左侧布满了破碎机陷阱。如果某个怪物进入走廊的左侧部分或原点(因此,其当前坐标变得小于或等于$$$0$$$),它会立即被陷阱杀死。

伊万用来杀死怪物的主要武器是凤凰杖。它可以发射一枚导弹,撞击后爆炸,消灭爆炸中的每一个怪物,并将所有其他怪物抛离震中。正式地,假设 Ivan 发射了一枚导弹,使其在 $$$c$$$ 点爆炸。然后每个怪物要么被爆炸杀死,要么被推开。设某怪物当前坐标为$$$y$$$,则:

- 如果$$$c = y$$$,则怪物被杀死;
- 如果 $$$y < c$$$,则怪物被向左推 $$$r$$$ 个单位,因此其当前坐标变为 $$$y - r$$$;
- 如果 $$$y > c$$$,则怪物被向右推 $$$r$$$ 个单位,因此其当前坐标变为 $$$y + r$$$。

Ivan将按照如下方式杀死怪物:选择某个整数点$$$d$$$并向该点发射一枚导弹,然后等到它爆炸,所有被推到走廊左侧的怪物都被粉碎机陷阱杀死,然后,如果至少有一个怪物还活着,则选择另一个整数点(可能是已经使用过的那个)并在那里发射一枚导弹,以此类推。

伊万必须发射多少枚导弹才能杀死所有怪物?您可能会认为,每次伊万发射凤凰棒时,他都会选择最佳的撞击点。

您必须回答 $$$q$$$ 独立查询。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。

每个查询的第一行包含两个整数 $$$n$$$ 和 $$$r$$$ ($$$1 \le n, r \le 10^5$$$) - 敌人的数量以及敌人距离爆炸中心的距离。

每个查询的第二行包含 $$$n$$$ 整数 $$$x_i$$$ ($$$1 \le x_i \le 10^5$$$) — 怪物的初始位置。

保证所有查询的所有 $$$n$$$ 之和不超过 $$$10^5$$$。

输出

对于每个查询,打印一个整数 - 杀死所有怪物所需的凤凰棒的最小射击次数。

示例

输入 #1

2
3 2
1 3 5
4 1
5 2 3 5

输出 #1

2
2

注意

在第一个测试用例中,Ivan 的行为如下:

- 选择$$$3$$$点,第一个怪物在$$$-1$$$处被压碎陷阱死亡,第二个怪物因爆炸死亡,第三个怪物被推到$$$7$$$点;
- 选择点$$$7$$$,第三个怪物因爆炸而死亡。

在第二个测试用例中,Ivan 的行为如下:

- 选择点$$$5$$$,第一只和第四只怪物爆炸死亡,第二只怪物被推到点$$$1$$$,第三只怪物被推到点$$$2$$$;
- 选择点$$$2$$$,第一个怪物在$$$0$$$处死于破碎机陷阱,第二个怪物死于爆炸。