← 返回题目列表

Codeforces · 2161/A

A. 往返

中文机器翻译题面 查看原题
他们说,如果你进行 1000 轮,最后会出现一个秘密漫画 (c)

Petya 和 Vasya 喜欢参加 Codeforces 竞赛。瓦夏 (Vasya) 与佩蒂亚 (Petya) 打赌,他将参加比他更多的额定比赛。最初,Vasya 的评级为 $$$R_0$$$。总共将进行 $$$n$$$ 轮,每轮为以下两种类型之一:

  • 分区。 1 — 对所有参与者评分
  • 分区。 2 — 对评级严格低于 $$$X$$$ 的参与者进行评级,对所有其他参与者未评级,

在未评级的回合中,Vasya 无法更改他的评级。如果 Vasya 在评级轮之前的评级为 $$$R$$$,那么对于任何 非负 $$$R-D$$$ 和 $$$R+D$$$(含)之间的整数 $$$x$$$ Vasya 可以采取一种策略,使他的评分之后恰好变为 $$$x$$$(这里 $$$D$$$ 是正整数)。请注意,评级可能永远不会变为负面。

帮助 Vasya 确定他可以参加的最大额定轮数。

输入

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

每个测试用例的第一行包含四个整数: $$$R_0, X, D, n$$$ ($$$0 \leq R_0 \leq 10^9$$$, $$$1 \leq X \leq 10^9$$$, $$$1 \leq D, n \leq 1000$$$) — Vasya 的初始评级,之间的评级阈值分区、最大评级增量和轮数。

每个测试用例的第二行包含一个大小为 $$$n$$$ 的字符串。该字符串仅包含字符“1“和”2”,代表div。 1 和分区。分别进行2轮。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^4$$$。

输出

对于每个测试用例,打印一个整数 - Vasya 可以参与的最大评级轮数。

示例

输入
复制

4
2100 2100 5 3
222
2098 2100 5 6
111211
2115 2100 226 7
2211121
0 10 4 8
22111121

输出
复制

0
6
5
8

注意

在第一个示例中,由于 $$$R_0 \geq X$$$,每个 div. 2轮是 未评级 Vasya,所以他的评级永远不会改变。因此,他不能为自己进行任何一轮评级,答案是$$$0$$$。

在第二个示例中,每轮后的最佳评级序列之一是: $$$2098 \rightarrow 2103 \rightarrow 2101 \rightarrow 2099 \rightarrow 2097 \rightarrow 2097 \rightarrow 2092$$$。