← 返回题目列表

Codeforces · 1858/B

B. 走道

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

夏季信息学学校主走道附近有 $$$n$$$ 长凳。这些长凳按顺序按从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。人行道附近还有 $$$m$$$ 饼干卖家。第 $$$i$$$ ($$$1 \le i \le m$$$) 饼干卖家位于第 $$$s_i$$$ 长凳附近。

Petya 站在走道的起点。他将经过从第 $$$1$$$-st 长凳到第 $$$n$$$-th 长凳的所有长凳附近。 Petya 在 $$$1$$$ 分钟内穿过两个连续长凳之间的距离。他有一个背包,里面装着无限量的饼干。佩蒂亚将从背包里吃饼干,并在散步时从饼干小贩那里购买。

Petya 根据以下规则仅在长凳附近吃饼干:当且仅当至少满足以下条件之一时,他才会在第 $$$i$$$ ($$$1 \le i \le n$$$) 长凳附近吃饼干:

- 第 $$$i$$$ 长凳附近有一个饼干卖家。然后Petya会从饼干卖家那里买一块饼干并立即吃掉。
- Petya 还没有吃饼干。然后Petya会从背包里拿出一块饼干并立即吃掉。
- 自从 Petya 吃下上一块饼干以来,至少过去了 $$$d$$$ 分钟。换句话说,Petya 没有吃过长凳 $$$i-1, i-2, \ldots, \max(i-d+1, 1)$$$ 附近的饼干。然后Petya会从背包里拿出一块饼干并立即吃掉。

你可能会认为 Petya 会立即吃掉饼干。 Petya 不会在同一个长凳附近吃两块或更多饼干。

您希望尽量减少 Petya 在散步时吃的饼干数量。为此,您将要求暑期信息学学校的管理人员在 Petya 开始步行之前从人行道上移除一名饼干销售商​​。

请确定在移除一名 cookie 卖家后 Petya 可以吃的最少 cookie 数量。还要确定饼干销售商​​的数量,这样,如果您删除其中一个,Petya 就会吃掉尽可能少的饼干。

输入

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

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$d$$$ ($$$2 \le d \le n \le 10^9$$$, $$$2 \le m \le \min(10^{5}, n)$$$) — 长凳数量、cookie 卖家数量和参数值分别来自语句 $$$d$$$。

每个测试用例的第二行包含 $$$m$$$ 整数 $$$s_1, s_2, \ldots, s_m$$$ ($$$1 \le s_i \le n$$$) — cookie 卖家的位置。对于所有 $$$1 \leq i \leq m - 1$$$,保证 $$$s_{i} < s_{i+1}$$$。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印两个整数 - 如果正好删除一个 cookie 卖家,Petya 可以吃掉的 cookie 的最小数量,以及 cookie 卖家的数量,如果其中一个被删除,Petya 将吃掉尽可能少的 cookie。

示例

输入 #1

8
6 2 2
2 5
8 3 2
3 5 8
10 4 9
2 8 9 10
30 5 8
6 8 15 24 29
30 5 8
6 8 12 20 27
8 8 3
1 2 3 4 5 6 7 8
2 2 2
1 2
1000000000 3 20000000
57008429 66778899 837653445

输出 #1

3 1
4 1
4 4
6 4
5 2
7 7
1 1
51 1

注意

在第一个测试用例中 $$$n=6$$$、$$$m=2$$$、$$$d=2$$$ 和 $$$s=[2, 5]$$$。如果没有删除 cookie 卖家,那么 Petya 将在行走过程中吃掉 $$$4$$$ 饼干(请注意,您必须恰好删除一个 cookie 卖家;解释这种情况只是为了显示 Petya 如何决定是否吃 cookie):

- Petya 会在 $$$1$$$-st 长凳附近吃一块饼干,因为他还没有吃一块饼干。
- Petya 会在第 $$$2$$$-nd 长凳附近吃一块饼干,因为这个长凳附近有一个饼干卖家。
- Petya 不会在 $$$3$$$-rd 长凳附近吃饼干,因为自从他吃饼干后仅过了 $$$1<d$$$ 分钟。
- Petya 会在第 $$$4$$$ 长凳附近吃一块饼干,因为他吃了一块饼干已经过了 $$$2\ge d$$$ 分钟。
- Petya 会在第 $$$5$$$ 长凳附近吃一块饼干,因为这个长凳附近有一个饼干卖家。
- Petya 不会在第 $$$6$$$ 长凳附近吃饼干,因为自从他吃饼干后仅过了 $$$1<d$$$ 分钟。

如果 $$$1$$$-st 饼干卖家被移除,Petya 将吃掉 $$$3$$$ 饼干(靠近长凳 $$$1$$$、$$$3$$$ 和 $$$5$$$)。如果 $$$2$$$-nd 饼干卖家被移除,Petya 将吃掉 $$$4$$$ 饼干(靠近长凳 $$$1$$$、$$$2$$$、$$$4$$$ 和 $$$6$$$)。

因此,Petya 最少吃的饼干数量是 $$$3$$$;只有一个饼干销售商​​,因此将其删除会导致 Petya 吃的饼干数量最小化。

在第二个测试用例中

- 移除$$$1$$$-st或$$$2$$$-nd饼干卖家导致Petya在长凳$$$1$$$、$$$3$$$、$$$5$$$、$$$7$$$、$$$8$$$附近吃了$$$5$$$饼干;
- 移除$$$3$$$-rd饼干卖家导致Petya在长凳$$$1$$$、$$$3$$$、$$$5$$$、$$$7$$$附近吃了$$$4$$$饼干。

请注意,您应该输出的第二个整数是 cookie 卖家的数量(即金额),而不是要删除的 cookie 卖家的索引。因此,第二个测试用例的答案是 4 1,因为只有一个饼干销售商​​,因此删除它会导致 Petya 吃掉四块饼干,这是可能的最小值。

在第三个测试用例中,无论哪个 cookie 卖家被删除,Petya 都会吃掉 $$$4$$$ 饼干。

请注意,Petya 对减少他吃的饼干数量不感兴趣,因此根据声明中的规则,只要有可能,他就会吃饼干。