← 返回题目列表

Codeforces · 1315/B

B. 归来

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

经过一场长时间的聚会后,Petya 决定回家,但结果发现他已经在小镇的另一端了。镇上的线路有$$$n$$$十字路口,每个十字路口要么有公交车站,要么有电车站。

十字路口表示为长度为 $$$n$$$ 的字符串 $$$s$$$,其中 $$$s_i = \texttt{A}$$$(如果第 $$$i$$$ 个十字路口有公交车站),以及 $$$s_i = \texttt{B}$$$(如果第 $$$i$$$ 个十字路口有电车车站)。目前Petya位于第一个十字路口(对应于$$$s_1$$$),他的目标是到达最后一个十字路口(对应于$$$s_n$$$)。

如果两个十字路口 $$$i$$$ 和 $$$j$$$ 对于所有十字路口 $$$i, i+1, \ldots, j-1$$$ 都有一个公交车站,可以支付 $$$a$$$ 卢布购买公交车票,然后从第 $$$i$$$ 个十字路口乘坐公交车前往第 $$$j$$$ 个十字路口(不必有公交车站)第 $$$j$$$ 个十字路口的公交车站)。正式来说,如果 $$$s_t = \texttt{A}$$$ 对于所有 $$$i \le t < j$$$,则支付 $$$a$$$ 卢布 Petya 可以从 $$$i$$$ 变为 $$$j$$$。

如果两个十字路口 $$$i$$$ 和 $$$j$$$ 对于所有十字路口 $$$i, i+1, \ldots, j-1$$$ 都有一个有轨电车车站,可以支付 $$$b$$$ 卢布购买电车票,然后从第 $$$i$$$ 个十字路口乘坐电车前往第 $$$j$$$ 个十字路口(不必有电车)第 $$$j$$$ 个十字路口的电车站)。正式来说,如果 $$$s_t = \texttt{B}$$$ 对于所有 $$$i \le t < j$$$,则支付 $$$b$$$ 卢布 Petya 可以从 $$$i$$$ 变为 $$$j$$$。

例如,如果 $$$s$$$="AABBBBAB"、$$$a=4$$$ 和 $$$b=3$$$ 则 Petya 需要:

- 购买一张从 $$$1$$$ 到 $$$3$$$ 的巴士票,
- 购买一张电车票,从 $$$3$$$ 到 $$$6$$$,
- 购买一张从 $$$6$$$ 到 $$$7$$$ 的巴士票。

因此,他总共需要花费 $$$4+3+4=11$$$ 卢布。请注意,最后一个十字路口的停靠站类型(即字符$$$s_n$$$)不会影响最终费用。

现在Petya正处于第一个十字路口,他想要到达第$$$n$$$个十字路口。聚会结束后,他带着$$$p$$$卢布离开了。他决定步行去某个车站,然后只乘坐公共交通工具回家。

帮助他选择最近的十字路口$$$i$$$先步行,这样他就有足够的钱从第$$$i$$$个十字路口到达第$$$n$$$个十字路口,只使用电车和公共汽车票。

输入

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。

每个测试用例的第一行由三个整数 $$$a, b, p$$$ ($$$1 \le a, b, p \le 10^5$$$) 组成 - 公交车票费用、电车票费用和 Petya 的金额。

每个测试用例的第二行由一个字符串 $$$s$$$ 组成,其中 $$$s_i = \texttt{A}$$$,如果在第 $$$i$$$ 个十字路口有一个公交车站,并且 $$$s_i = \texttt{B}$$$,如果在第 $$$i$$$ 个十字路口有一个电车站 ($$$2 \le |s| \le 10^5$$$)。

保证一次测试中所有测试用例的字符串$$$s$$$的长度总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印一个数字 - 十字路口 Petya 的最小索引 $$$i$$$ 应该步行。路径的其余部分(即从 $$$i$$$ 到 $$$n$$$ 他应该使用公共交通工具)。

示例

输入 #1

5
2 2 1
BB
1 1 1
AB
3 2 8
AABBBBAABB
5 3 4
BBBBB
2 1 1
ABABAB

输出 #1

2
1
3
1
6