K. 小B的传说

    传统题 1000ms 256MiB

小B的传说

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

传说,如果你参加1000场 SyuctOJSyuctOJ 比赛,最后会有个神秘动画彩蛋 (c)

小B小 B 和 JikongJikong都喜欢参加 SyuctOJSyuctOJ 的比赛。JikongJikong 跟 小B小B 打赌,说他能参加的评级赛比 小B小B 多。起初,JikongJikong 的初始评分是 R0R_0。总共会有 nn 场比赛,每场比赛分两种类型:

——div.1——div. 1 — 所有人都算评级

——div.2——div. 2 — 只有评分严格低于 X 的选手算评级,其他人都不算。

在不算评级的比赛中,JikongJikong的评分不会变化。如果JikongJikong参加某场评级赛前的评分是R R,那么对于任意一个满足R−D≤x≤R+D R−D ≤ x ≤ R+D 的非负整数 xx,他都能采取策略让赛后评分恰好变成x x(这里 DD 是正整数)。注意,评分永远不会变成负数。

请帮JikongJikong算出,他最多能参加多少场评级赛。

输入格式

每个测试包含多个测试用例。第一行给出测试用例数量t(1≤t≤1000) t (1 \leq t \leq 1000)。接下来是各个测试用例的描述。

每个测试用例第一行包含四个整数:R0,X,D,nR_0, X, D, n (0≤R0≤1090 \leq R_0 \leq 10^9 , 1≤X≤109,1≤D,n≤20001 \leq X \leq 10^9, 1 \leq D, n \leq 2000) — JikongJikong的初始评分、分区的评分门槛、最大评分变化量、比赛场数。 第二行是一个长度为 n 的数,只包含 "1" 和 "2",分别代表 div.1div.1 和div.2 div.2 的比赛。

所有测试用例中 nn 的总和不超过 3⋅1043 \cdot 10^4。

输出格式

对每个测试用例,输出一个整数——JikongJikong最多能参加的评级赛场数。

样例

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


2026级SYUCT-ACM新生第四次训练

未参加
状态
已结束
规则
XCPC
题目
40
开始于
2026-10-30 18:30
结束于
2026-11-16 10:30
持续时间
400 小时
主持人
参赛人数
62