← 返回题目列表

Codeforces · 1468/D

D. 鞭炮

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

考虑一条长走廊,它可以分为 $$$n$$$ 大小为 $$$1 \times 1$$$ 的方形单元格。这些单元格从左到右编号为 $$$1$$$ 到 $$$n$$$。

这条走廊里有两个人,一个流氓和一个保安。最初,流氓位于第 $$$a$$$ 单元格,警卫位于第 $$$b$$$ 单元格 ($$$a \ne b$$$)。

可能的情况之一。走廊由$$$7$$$牢房组成,流氓在第$$$3$$$牢房,警卫在第$$$6$$$牢房($$$n = 7$$$,$$$a = 3$$$,$$$b = 6$$$)。

流氓口袋里有$$$m$$$鞭炮,第$$$i$$$鞭炮在点燃后$$$s_i$$$秒内爆炸。

每秒发生以下事件(按顺序,完全按照以下顺序):

1. 首先,流氓要么移动到相邻的牢房(从$$$i$$$牢房,他可以移动到$$$(i + 1)$$$牢房或$$$(i - 1)$$$牢房,并且他不能离开走廊),要么留在他当前所在的牢房。如果流氓不动,他可以点燃一根鞭炮并将其扔掉。流氓不能进入警卫所在的牢房;
2. 其次,一些已经扔下的鞭炮可能会爆炸。形式上,如果鞭炮 $$$j$$$ 在第 $$$T$$$ 秒掉落,那么它将在第 $$$(T + s_j)$$$ 秒爆炸(例如,如果 $$$s_j = 2$$$ 的鞭炮在第 $$$4$$$ 秒掉落,它将在第 $$$6$$$ 秒爆炸);
3. 最后,警卫将一间牢房移至离流氓更近的地方。如果警卫移动到流氓所在的牢房,流氓就会被抓住。

显然,由于走廊是有限的,流氓迟早会被抓住。他的目标是在他被抓住之前看到最多数量的鞭炮爆炸;也就是说,他会采取行动,以在他被抓住之前最大化爆炸的鞭炮数量。

如果流氓行为最佳,你的任务是计算此类鞭炮的数量。

输入

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

每个测试用例由两行组成。第一行包含四个整数 $$$n$$$、$$$m$$$、$$$a$$$ 和 $$$b$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le m \le 2 \cdot 10^5$$$; $$$1 \le a, b \le n$$$; $$$a \ne b$$$) — 走廊的大小,走廊的数量鞭炮,分别是流氓的初始位置和警卫的初始位置。

第二行包含 $$$m$$$ 整数 $$$s_1$$$, $$$s_2$$$, ..., $$$s_m$$$ ($$$1 \le s_i \le 10^9$$$),其中 $$$s_i$$$ 是第 $$$i$$$ 个鞭炮点燃后爆炸所需的时间。

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

输出

对于每个测试用例,打印一个整数——流氓在被抓住之前可以爆炸的最大鞭炮数量。

示例

输入 #1

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

输出 #1

2
1
1

注意

在第一个测试用例中,流氓应该采取如下行动:

- 第二个1:放下第二个鞭炮,所以它会在第$$$5$$$秒爆炸。警卫移动到牢房$$$5$$$;
- 第二个 2:移至单元格 $$$2$$$。警卫移动到牢房$$$4$$$;
- 第二个3:放下第一个鞭炮,所以它会在第$$$4$$$秒爆炸。警卫移动到牢房$$$3$$$;
- 第二个 4:移至单元格 $$$1$$$。第一声​​鞭炮爆炸了。警卫移动到牢房$$$2$$$;
- 第二个 5:留在单元格 $$$1$$$ 中。第二声鞭炮爆炸了。警卫移动到牢房 $$$1$$$ 并抓住了流氓。