Homecoming (Codeforces 1315B)
Tags: Greedy, strings

After a long party Petya decided to return home, but he turned out to be at the opposite end of the town from his home. There are $$$n$$$ crossroads in the line in the town, and there is either the bus or the tram station at each crossroad.The crossroads are represented as a string $$$s$$$ of length $$$n$$$, where $$$s_i = \texttt{A}$$$, if there is a bus station at $$$i$$$-th crossroad, and $$$s_i = \texttt{B}$$$, if there is a tram station at $$$i$$$-th crossroad. Currently Petya is at the first crossroad (which corresponds to $$$s_1$$$) and his goal is to get to the last crossroad (which corresponds to $$$s_n$$$).If for two crossroads $$$i$$$ and $$$j$$$ for all crossroads $$$i, i+1, \ldots, j-1$$$ there is a bus station, one can pay $$$a$$$ roubles for the bus ticket, and go from $$$i$$$-th crossroad to the $$$j$$$-th crossroad by the bus (it is not necessary to have a bus station at the $$$j$$$-th crossroad). Formally, paying $$$a$$$ roubles Petya can go from $$$i$$$ to $$$j$$$ if $$$s_t = \texttt{A}$$$ for all $$$i \le t < j$$$. If for two crossroads $$$i$$$ and $$$j$$$ for all crossroads $$$i, i+1, \ldots, j-1$$$ there is a tram station, one can pay $$$b$$$ roubles for the tram ticket, and go from $$$i$$$-th crossroad to the $$$j$$$-th crossroad by the tram (it is not necessary to have a tram station at the $$$j$$$-th crossroad). Formally, paying $$$b$$$ roubles Petya can go from $$$i$$$ to $$$j$$$ if $$$s_t = \texttt{B}$$$ for all $$$i \le t < j$$$.For example, if $$$s$$$="AABBBAB", $$$a=4$$$ and $$$b=3$$$ then Petya needs:  buy one bus ticket to get from $$$1$$$ to $$$3$$$,  buy one tram ticket to get from $$$3$$$ to $$$6$$$,  buy one bus ticket to get from $$$6$$$ to $$$7$$$. Thus, in total he needs to spend $$$4+3+4=11$$$ roubles. Please note that the type of the stop at the last crossroad (i.e. the character $$$s_n$$$) does not affect the final expense.Now Petya is at the first crossroad, and he wants to get to the $$$n$$$-th crossroad. After the party he has left with $$$p$$$ roubles. He's decided to go to some station on foot, and then go to home using only public transport.Help him to choose the closest crossroad $$$i$$$ to go on foot the first, so he has enough money to get from the $$$i$$$-th crossroad to the $$$n$$$-th, using only tram and bus tickets.

Input: Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$).The first line of each test case consists of three integers $$$a, b, p$$$ ($$$1 \le a, b, p \le 10^5$$$) — the cost of bus ticket, the cost of tram ticket and the amount of money Petya has.The second line of each test case consists of one string $$$s$$$, where $$$s_i = \texttt{A}$$$, if there is a bus station at $$$i$$$-th crossroad, and $$$s_i = \texttt{B}$$$, if there is a tram station at $$$i$$$-th crossroad ($$$2 \le |s| \le 10^5$$$).It is guaranteed, that the sum of the length of strings $$$s$$$ by all test cases in one test doesn't exceed $$$10^5$$$.

Output: For each test case print one number — the minimal index $$$i$$$ of a crossroad Petya should go on foot. The rest of the path (i.e. from $$$i$$$ to $$$n$$$ he should use public transport).


Sample Inputs:
5
2 2 1
BB
1 1 1
AB
3 2 8
AABBBBAABB
5 3 4
BBBBB
2 1 1
ABABAB

Sample Outputs:
2
1
3
1
6

Solution (Python):
def minimal_index(test_cases):
    results = []
    for case in test_cases:
        (a, b, p, s) = case
        i = len(s) - 2
        while i > -1:
            if s[i] == 'A' and p < a:
                break
            if s[i] == 'B' and p < b:
                break
            if s[i] == 'A':
                p -= a
            if s[i] == 'B':
                p -= b
            while i > 0 and s[i] == s[i - 1]:
                i -= 1
            i -= 1
        results.append(i + 2)
    return results
t = int(input())
test_cases = []
for _ in range(t):
    (a, b, p) = map(int, input().split())
    s = input()
    test_cases.append((a, b, p, s))
for res in minimal_index(test_cases):
    print(res)

Solution (Python):
if __name__ == '__main__':
    result = []
    t = int(input())
    for _ in range(t):
        (a, b, c) = map(int, input().split())
        s = input()
        ch = 'r'
        pos = 1
        for i in range(len(s) - 2, -1, -1):
            if s[i] != ch:
                if s[i] == 'A' and c >= a:
                    c -= a
                elif s[i] == 'B' and c >= b:
                    c -= b
                else:
                    pos = i + 2
                    break
                ch = s[i]
        result.append(pos)
    for x in result:
        print(x)

Solution (Python):
tests = int(input())
for t in range(tests):
    (a, b, p) = map(int, input().split())
    s = input()
    ans = 1
    c = '*'
    i = len(s) - 2
    while i >= 0:
        if s[i] != c:
            if s[i] == 'A' and p >= a:
                p -= a
            elif s[i] == 'B' and p >= b:
                p -= b
            else:
                ans = i + 2
                break
            c = s[i]
        i -= 1
    print(ans)