A16690 · Round Trip · GESP考级

题目描述

他们说如果你打了 1000 场，就能看到最后的隐藏动画片（c）。 Petya 和 Vasya 都喜欢参加 Codeforces 比赛。Vasya 和 Petya 打赌，他能比 Petya 参加更多场计分轮。最初，Vasya 的 rating 为 $R_0$。一共会举办 $n$ 场比赛，每场比赛属于以下两种类型之一： - div. 1 —— 对所有参赛者计分； - div. 2 —— 仅对 rating 严格小于 $X$ 的选手计分，对其他人不计分。 在一场不计分的比赛中，Vasya 的 rating 不会发生变化。如果 Vasya 在某场计分轮前的 rating 是 $R$，那么对于任意非负整数 $x$，且 $x$ 满足 $R-D \leq x \leq R+D$（其中 $D$ 为正整数），Vasya 可以采用某种策略，使得他在该轮之后的 rating 恰好变为 $x$。注意，rating 永远不会变为负数。 请帮助 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 的初始 rating，分区的 rating 阈值，rating 的最大变化量，以及比赛的总轮数。 每个测试用例的第二行包含一个长度为 $n$ 的字符串，只包含字符 ‘1’ 和 ‘2’，分别表示该场比赛为 div. 1 輪 和 div. 2 輪。 所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^4$。

对于每个测试用例，输出一个整数，表示 Vasya 最多可以参加多少场计分轮。

输入 #1

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

输出 #1