← 返回题目列表

Codeforces · 2208/B

B. 骑自行车的人

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

Bob喜欢在手机上玩有趣的塔防游戏。在游戏中,他必须出牌才能击败对手!

有 $$$n$$$ 牌放置在称为牌组的队列中。在任何时候,Bob 都只能打出当前放置在牌组中前 $$$k$$$ 位置的牌。在每个回合中,Bob 选择放置在第一个 $$$k$$$ 位置的卡牌,将其从牌组中取出,打出,然后将同一张牌放回牌组底部。换句话说,在每一回合中,都会从队列中的第一个 $$$k$$$ 元素中选择一个元素,并将其移动到队列的末尾,并将放置在其之后的所有元素移动到前面一个索引。

一张牌称为获胜条件,Bob 希望尽可能多地玩它。然而,每张卡牌也有玩游戏所需的成本。第 $$$i$$$ 卡(最初放置在第 $$$i$$$ 位置)每次打出时都会消耗鲍勃 $$$a_i$$$ 能量。打出的牌的总花费不得超过$$$m$$$。最初,获胜条件卡被放置在队列中的第 $$$p$$$ 位置。

你需要找出获胜条件卡可以打出的最大次数,确保总成本不超过$$$m$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。

每个测试用例的第一行包含四个整数 $$$n,k,p,m$$$ ($$$1\le k,p\le n\le 5000$$$, $$$1\le m\le 5000$$$),分别表示牌数、一次可玩的牌数、获胜条件的初始位置以及可用的总能量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le m$$$) 表示每张卡的成本。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,一行输出一个整数,表示获胜条件可以播放的最大次数。

示例

输入
复制

4
2 1 2 42
42 1
3 3 2 6
2 1 2
3 2 2 6
2 1 2
8 4 7 10
3 4 4 2 1 1 4 2

输出
复制

0
6
2
1

注意

在第一个测试用例中,我们只能打出牌组中的第一张牌,并且打出它会消耗所有能量。由于获胜条件是第二张牌,因此在能量耗尽之前我们无法打出它。因此,答案是$$$0$$$。

在第二个测试用例中,我们可以打出这副牌中的所有牌。最优策略显然是只玩获胜条件。由于玩游戏需要花费 $$$1$$$ 能量,而我们总共有 $$$6$$$ 能量,因此在能量耗尽之前我们可以玩 $$$6$$$ 次。因此,答案是$$$6$$$。

在第三个测试用例中,我们可以如下打牌:(获胜条件为红色)

初始牌组为$$$[2,\color{red}{1},2]$$$。

打出第一张牌:牌组变为 $$$[\color{red}{1},2,2]$$$。

再次打出第一张牌:牌组变为 $$$[2,2,\color{red}{1}]$$$。

再次打出第一张牌:牌组变为 $$$[2,\color{red}{1},2]$$$。

打出第二张牌:牌组变为 $$$[2,2,\color{red}{1}]$$$。

在此过程中,我们已经玩了$$$2$$$次获胜条件,总共消耗了$$$6$$$能量。可以证明,没有任何策略允许我们在能量点不超过 $$$6$$$ 的情况下玩获胜条件超过 $$$2$$$ 次;因此,答案是$$$2$$$。

在第四个测试用例中,可以证明我们只能玩一次获胜条件。这可以通过始终打出牌组中第 $$$4$$$ 的牌来实现。因此,答案是$$$1$$$。